数学A ユークリッドの互除法 問題 5 解説

方針・初手

（1） は、分数の関係式を整数の等式に直して、共通の約数が何を割り切るかを見る。

（2） は、（1） を使える形に変形する。特に $28n+5$ と $21n+4$ の差に注目する。

解法1

(1)

条件

$$ \frac{b}{a}=\frac{c}{a}+d $$

の両辺に $a$ をかけると、

$$ b=c+ad $$

である。

ここで、$a$ と $b$ の任意の公約数を $m$ とする。つまり、

$$ m \mid a,\qquad m \mid b $$

である。

このとき $m \mid a$ より $m \mid ad$ であり、また $m \mid b$ であるから、

$$ m \mid b-ad $$

が成り立つ。ところが $b=c+ad$ なので、

$$ b-ad=c $$

である。したがって、

$$ m \mid c $$

も成り立つ。

よって $m$ は $a$ と $c$ の公約数である。ところが、仮定より $a$ と $c$ は互いに素であるから、

$$ m=1 $$

でなければならない。

したがって、$a$ と $b$ の公約数は $1$ のみである。ゆえに、$a$ と $b$ は互いに素である。

(2)

任意の自然数 $n$ に対して、

$$ a=21n+4,\qquad b=28n+5,\qquad c=7n+1,\qquad d=1 $$

とおく。

このとき、

$$ b=28n+5=(7n+1)+(21n+4)=c+a $$

であるから、

$$ \frac{b}{a}=\frac{c}{a}+1 $$

が成り立つ。

あとは $a$ と $c$ が互いに素であることを示せば、（1） より $a$ と $b$ が互いに素であると分かる。

ここで、

$$ a=21n+4=3(7n+1)+1=3c+1 $$

である。

$c$ と $a$ の公約数を $m$ とすると、$m \mid c$ かつ $m \mid a$ である。したがって、

$$ m \mid a-3c $$

が成り立つ。ところが、

$$ a-3c=1 $$

なので、

$$ m \mid 1 $$

である。よって $m=1$ である。

したがって、$a$ と $c$ は互いに素である。

ゆえに （1） より、$a$ と $b$、すなわち

$$ 21n+4 $$

と

$$ 28n+5 $$

は互いに素である。

したがって、任意の自然数 $n$ に対して、$28n+5$ と $21n+4$ は互いに素である。

解法2

（2） は、ユークリッドの互除法を用いて直接示すこともできる。

$28n+5$ と $21n+4$ の最大公約数を $g$ とする。

$$ g=\gcd(28n+5,21n+4) $$

とおく。

すると $g$ はこれらの整数係数の差も割り切る。まず、

$$ (28n+5)-(21n+4)=7n+1 $$

より、

$$ g \mid 7n+1 $$

である。

また、

$$ 21n+4=3(7n+1)+1 $$

であるから、$g \mid 21n+4$ かつ $g \mid 7n+1$ より、

$$ g \mid (21n+4)-3(7n+1) $$

が成り立つ。

右辺は

$$ (21n+4)-3(7n+1)=1 $$

であるから、

$$ g \mid 1 $$

である。よって、

$$ g=1 $$

である。

したがって、

$$ \gcd(28n+5,21n+4)=1 $$

であり、$28n+5$ と $21n+4$ は互いに素である。

解説

（1） は、互いに素であることを示す典型的な方法である。「共通の約数を任意に取り、それが $1$ しかありえないことを示す」という流れを使う。

（2） では、$28n+5$ と $21n+4$ の差が

$$ 7n+1 $$

になることが重要である。さらに、

$$ 21n+4=3(7n+1)+1 $$

となるため、共通の約数は最終的に $1$ を割り切ることになる。

（1） を使う場合は、

$$ 28n+5=(7n+1)+(21n+4) $$

と見て、$a=21n+4,\ c=7n+1,\ d=1$ と置くのが自然である。

答え

(1)

$a$ と $b$ は互いに素である。

(2)

任意の自然数 $n$ に対して、$28n+5$ と $21n+4$ は互いに素である。