整数の性質｜ユークリッドの互除法について
今回はユークリッドの互除法について学習しましょう。ユークリッドの互除法も頻出の単元です。本来の使い方よりも応用的な使い方の方が出題されます。十分に演習をこなしておきましょう。
割り算と最大公約数、ユークリッドの互除法
この単元では、以下のような事柄を学習します。
- 割り算と最大公約数
- ユークリッドの互除法
新しい用語や定理が出てきます。まずは文言通りに正しく覚えることが大切です。
割り算と最大公約数の関係
割り算したときの商や余りを用いて、もとの整数を表せることはすでに学習しました。この単元では最大公約数との関係について学習します。
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$ の形に書き表された式に対して、定理が成り立つと考えて良いということです。
\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*}
以上のことから、わり算と最大公約数の関係について以下のことが成り立ちます。
(i) $r \neq 0$ のとき、( $a$ と $b$ の最大公約数) = ( $b$ と $r$ の最大公約数)
(ii) $r=0$ のとき、( $a$ と $b$ の最大公約数) = $b$
2つの自然数の最大公約数を求めるとき、2つの自然数が大きければ大きいほど、最大公約数を求めるのは大変になります。しかし、この定理から、もとの自然数よりも小さな2数の最大公約数を考えれば良いことが分かります。
次はユークリッドの互除法についてです。