1島根大学 2020年 数学 第1問解答・解説

自然数 $m,n$ に対し，$m$ と $n$ の最大公約数を $\gcd(m,n)$ で表す。以下はユークリッドの互除法を用いた最大公約数の求め方である。

ユークリッドの互除法

$m,n$ を $m>n$ をみたす自然数とし，$r_{1}=m,\ r_{2}=n$ とおく。$r_{1}$ を $r_{2}$ で割った商を $q_{2}$，余りを $r_{3}\ (0\leq r_{3}<r_{2})$ とする。もし $r_{3}\neq 0$ ならば $r_{2}$ を $r_{3}$ で割った商を $q_{3}$，余りを $r_{4}\ (0\leq r_{4}<r_{3})$ とする。この手順を $k-1$ 回繰り返したとき，余り $r_{k+1}$ が $0$ になれば，次の関係式が成り立つ。$$\begin{aligned}r_{1}&=m,\\r_{2}&=n,\\r_{1}&=r_{2}q_{2}+r_{3}&& (0<r_{3}<r_{2}),\\r_{2}&=r_{3}q_{3}+r_{4}&& (0<r_{4}<r_{3}),\\&\vdots\\r_{k-2}&=r_{k-1}q_{k-1}+r_{k}&& (0<r_{k}<r_{k-1}),\\r_{k-1}&=r_{k}q_{k}.\end{aligned}$$このとき，$m$ と $n$ の最大公約数について，$$\gcd(m,n)=\gcd(r_{1},r_{2})=\gcd(r_{2},r_{3})=\cdots=\gcd(r_{k-1},r_{k})=r_{k}$$が成り立つ。

自然数 $n$ に対し，すべての位の数字が $1$ である $n$ 桁の自然数を $a_{n}$ とおく。例えば，$a_{1}=1,\ a_{2}=11,\ a_{3}=111$ であり，すべての $n$ に対して$$\displaystyle a_{n}=1+10+10^{2}+\cdots+10^{n-1}=\sum\limits _{k=0}^{n-1}10^{k}$$である。次の問いに答えよ。

(1) ユークリッドの互除法を用いて，$12345$ と $54321$ の最大公約数を求めよ。

(2) $m>n$ をみたす自然数 $m$ と $n$ に対し，等式 $a_{m}-a_{n}=10^{n}a_{m-n}$ が成り立つことを示せ。

(3) すべての自然数 $n$ に対し，$a_{n}$ と $10$ は互いに素である。このことと (2) の結果を用いて，$m>n$ をみたす自然数 $m$ と $n$ に対し，$\gcd(a_{m},a_{n})=\gcd(a_{n},a_{m-n})$ が成り立つことを示せ。

(4) $m>n$ をみたす自然数 $m$ と $n$ の最大公約数を $d$ とすると，$a_{m}$ と $a_{n}$ の最大公約数は $a_{d}$ であることを示せ。ただし，必要であれば，枠で囲まれたユークリッドの互除法の説明文で使用されている記号を用いてもよい。

(5) (1) と (4) を用いて，$a_{12345}$ と $a_{54321}$ の最大公約数を求めよ。