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

方針・初手

最大公約数は、ユークリッドの互除法と「共通の約数は差も割り切る」という性質を使う。特に、文字式の場合は整数係数の一次結合を作って定数を得るのが有効である。

解法1

(1) について、ユークリッドの互除法を用いる。

$$ 909667=607117+302550 $$

$$ 607117=302550\cdot 2+2017 $$

また、

$$ 302550=2017\cdot 150 $$

であるから、

$$ \gcd(909667,607117)=2017 $$

となる。

(2) について、$n+9$ と $2n+17$ の最大公約数を $d$ とする。すると $d$ は $n+9$ と $2n+17$ の両方を割り切る。

したがって、整数係数の一次結合

$$ 2(n+9)-(2n+17)=1 $$

も $d$ で割り切れる。よって $d$ は $1$ の正の約数であるから、

$$ d=1 $$

である。

したがって、

$$ \gcd(n+9,2n+17)=1 $$

となる。

(3) について、$2^{100}-1$ と $2^{20}-1$ を考える。一般に、$m$ が $n$ の倍数であるとき、$a^m-1$ は $a^n-1$ で割り切れる。

ここで $100=20\cdot 5$ であるから、

$$ 2^{100}-1=(2^{20})^5-1 $$

である。$x^5-1$ は $x-1$ で割り切れるので、$2^{100}-1$ は $2^{20}-1$ で割り切れる。

したがって、$2^{20}-1$ は両方の数の共通約数であり、かつ $2^{20}-1$ 自身が小さい方の数であるから、最大公約数は

$$ 2^{20}-1 $$

である。

計算すると、

$$ 2^{20}-1=1048576-1=1048575 $$

である。

解説

(1) は典型的なユークリッドの互除法である。大きな数でも、割り算を繰り返して余りを小さくしていけば最大公約数が求まる。

(2) は、共通の約数が整数係数の一次結合も割り切ることを使う問題である。$2(n+9)-(2n+17)=1$ と定数 $1$ が作れるため、最大公約数は必ず $1$ になる。

(3) は、$a^m-1$ 型の最大公約数である。$20$ が $100$ を割り切るので、$2^{20}-1$ がそのまま最大公約数になる。

答え

(1)

ア：$2017$

(2)

イ：$1$

(3)

ウ：$1048575$