整数の性質|ユークリッドの互除法について

12/05/2018数学A余り,最大公約数,除数,整数の性質,ユークリッドの互除法

今回はユークリッドの互除法について学習しましょう。ユークリッドの互除法も頻出の単元です。本来の使い方よりも応用的な使い方の方が出題されます。十分に演習をこなしておきましょう。

割り算と最大公約数、ユークリッドの互除法

この単元では、以下のような事柄を学習します。

  • 割り算と最大公約数
  • ユークリッドの互除法

新しい用語や定理が出てきます。まずは文言通りに正しく覚えることが大切です。

割り算と最大公約数の関係

割り算したときの商や余りを用いて、もとの整数を表せることはすでに学習しました。この単元では最大公約数との関係について学習します。

2数の最大公約数

割り算と最大公約数の間には、一般に、以下の定理が成り立ちます。

割り算と最大公約数
2つの自然数 $a \ , \ b \ (a \gt b)$ について、$a$ を $b$ で割った商を $q$、余りを $r$ とすると、
$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい。

この定理の証明は以下のようになります。$a$ と $b$ の最大公約数 $g$ が $b$ と $r$ の公約数になり、なおかつ $b$ と $r$ の最大公約数 $g’$ が $a$ と $b$ の公約数になることを示しています。

割り算と最大公約数の定理の証明
\begin{align*}
&\text{自然数 $a$ を自然数 $b$ で割った商 $q$ と余り $r$ を用いると、} \\[ 5pt ]
&\quad a = bq+r \quad \text{…①} \\[ 5pt ]
&\text{これを変形すると、} \\[ 5pt ]
&\quad r = a – bq \quad \text{…②} \\[ 5pt ]
&\text{ここで、$a$ と $b$ の最大公約数を $g$ とし、$b$ と $r$ の最大公約数を $g’$ とすると、} \\[ 5pt ]
&\quad a = \alpha g \quad \text{…③} \\[ 5pt ]
&\quad b = \beta g = \beta’ g’ \quad \text{…④} \\[ 5pt ]
&\quad r = \gamma g’ \quad \text{…⑤} \\[ 5pt ]
&\text{ただし、$\alpha$ と $\beta$、$\beta’$ と $\gamma$ はそれぞれ互いに素} \\[ 10pt ]
&\text{② , ③ , ④より} \\[ 5pt ]
&\quad r = \alpha g – \beta g q = g(\alpha – \beta q) \\[ 5pt ]
&\text{となるので、$g$ は $r$ の約数である。} \\[ 5pt ]
&\text{これより、$g$ は $b$ と $r$ の公約数となるので、} \\[ 5pt ]
&\quad g \leqq g’ \quad \text{…⑥} \\[ 10pt ]
&\text{また、① , ④ , ⑤より} \\[ 5pt ]
&\quad a = \beta’ g’q + \gamma g’ = g'(\beta’ q + \gamma) \\[ 5pt ]
&\text{となるので、$g’$ は $a$ の約数である。} \\[ 5pt ]
&\text{これより、$g’$ は $a$ と $b$ の公約数となるので、} \\[ 5pt ]
&\quad g’ \leqq g \quad \text{…⑦} \\[ 10pt ]
&\text{⑥ , ⑦より $g = g’$ が成り立つ。} \\[ 5pt ]
&\text{したがって、$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい。}
\end{align*}

証明において、$g \leqq g’$ や $g’ \leqq g$ となるのは、公約数になることは確かでも、それが最大公約数になるとは言い切れないからです。また、2つの不等式を同時に満たすのは、等号が成立するときだけであることから、 $g = g’$ を導出しています。

なお、割り算で成り立つ等式 $a = bq + r$ では、$0 \leqq r \lt b$ を満たす整数 $q \ , \ r$ がただ1つに定まりましたが、この定理を適応するときは、必ずしも $0 \leqq r \lt b$ である必要はありません。つまり、単に、$a = bq + r$ の形に書き表された式に対して、定理が成り立つと考えて良いということです。

必ずしも $0 \leqq r \lt b$ である必要はない例
\begin{align*}
&\text{30と4の最大公約数を求めるとする。} \\[ 5pt ]
&\quad 30 = 4 \cdot 7 + 2 \\[ 5pt ]
&\text{について、4と2の最大公約数は2より、30と4の最大公約数は2。} \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 30 = 4 \cdot 6 + 6 \\[ 5pt ]
&\text{について、4と6の最大公約数は2より、30と4の最大公約数は2。} \\[ 5pt ]
&\text{したがって、定理が成り立つのに必ずしも $0 \leqq r \lt b$ である必要はない。}
\end{align*}

以上のことから、わり算と最大公約数の関係について以下のことが成り立ちます。

2つの自然数 $a \ , \ b \ (a \gt b)$ について、$a$ を $b$ で割った商を $q$、余りを $r$ とする。
(i) $r \neq 0$ のとき、( $a$ と $b$ の最大公約数) = ( $b$ と $r$ の最大公約数)
(ii) $r=0$ のとき、( $a$ と $b$ の最大公約数) = $b$

2つの自然数の最大公約数を求めるとき、2つの自然数が大きければ大きいほど、最大公約数を求めるのは大変になります。しかし、この定理から、もとの自然数よりも小さな2数の最大公約数を考えれば良いことが分かります。

2数の最大公約数を求める方法には、素因数分解が基本だが、この定理を利用して求めることができることは知っておこう。

次はユークリッドの互除法についてです。