数学A 整数問題 問題 108 解説

方針・初手

最大公約数 $d$ は $x,y$ の整数係数の一次結合も割る。したがって、$x=8m+n,\ y=5m+2n$ から $m,n$ を含む形の式を作り、$d$ がどの数を割るかを調べる。

解法1

$d$ は $x,y$ の最大公約数であるから、

$$ d\mid x,\qquad d\mid y $$

である。したがって、$x,y$ の整数係数の一次結合も $d$ で割り切れる。

まず、

$$ 2x-y=2(8m+n)-(5m+2n)=11m $$

より、

$$ d\mid 11m $$

である。

また、

$$ 8y-5x=8(5m+2n)-5(8m+n)=11n $$

より、

$$ d\mid 11n $$

である。

ここで、$m,n$ が互いに素であるとする。すると、

$$ \gcd(11m,11n)=11\gcd(m,n)=11 $$

である。

$d$ は $11m$ と $11n$ の両方を割るので、

$$ d\mid \gcd(11m,11n)=11 $$

となる。よって、$d$ は正の約数として

$$ d=1\quad \text{または}\quad d=11 $$

である。

次に、$m=2$ の場合を考える。このとき、

$$ x=8\cdot 2+n=n+16 $$

$$ y=5\cdot 2+2n=2n+10 $$

である。

したがって、

$$ d=\gcd(n+16,2n+10) $$

である。ここで、

$$ 2(n+16)-(2n+10)=22 $$

より、$d$ は $22$ を割る。したがって、$d$ が $11$ になるためには、まず $11$ が $n+16$ と $2n+10$ の両方を割る必要がある。

$$ 11\mid n+16 $$

より、

$$ n\equiv -16\equiv -5\equiv 6 \pmod{11} $$

である。この条件のもとでは、

$$ 2n+10\equiv 2\cdot 6+10=22\equiv 0 \pmod{11} $$

となるので、$11$ は確かに両方を割る。

ただし、$d$ が $22$ になってはいけない。$2n+10$ は常に偶数であるから、$d$ が $22$ になるのは $n+16$ も偶数のとき、すなわち $n$ が偶数のときである。

よって、必要な条件は

$$ n\equiv 6 \pmod{11} $$

かつ $n$ が奇数であること。

$n\equiv 6 \pmod{11}$ を満たす自然数を小さい順に並べると、

$$ 6,\ 17,\ 28,\ \cdots $$

である。$n=6$ のときは偶数なので、

$$ x=22,\qquad y=22 $$

となり、

$$ d=22 $$

であるから条件を満たさない。

次に $n=17$ のとき、

$$ x=17+16=33 $$

$$ y=2\cdot 17+10=44 $$

であり、

$$ \gcd(33,44)=11 $$

である。

したがって、求める最小の自然数は

$$ n=17 $$

である。

解説

最大公約数の問題では、与えられた式を直接に比べるよりも、整数係数の一次結合を作るのが基本である。

この問題では、

$$ 2x-y=11m,\qquad 8y-5x=11n $$

という形を作れることが核心である。特に、$m,n$ が互いに素なら、$11m$ と $11n$ の共通因数は $11$ までしか残らない。

また、(2)では $m=2$ を代入したあと、

$$ \gcd(n+16,2n+10) $$

を考え、差を取って $22$ の約数に絞るのが自然である。$11$ で割り切れる条件だけでなく、$22$ にならない条件、つまり偶奇の確認を落とさないことが重要である。

答え

(1)

$$ d=1\quad \text{または}\quad d=11 $$

(2)

$$ n=17 $$