【1】 自然数に対し,との最大公約数をで表す.以下はユークリッドの互除法を用いた最大公約数の求め方である.
ユークリッドの互除法
ををみたす自然数とし,とおく.をで割った商を余りをとする.もしならばをで割った商を余りをとする.この手順を回繰り返したとき,余りがになれば,次の関係式が成り立つ.
このとき,との最大公約数について,
が成り立つ.
自然数に対し,すべての位の数字がである桁の自然数をとおく.例えば,であり,すべてのに対して
である.次の問いに答えよ.
(1) ユークリッドの互除法を用いて,との最大公約数を求めよ.
(2) をみたす自然数とに対し,等式が成り立つことを示せ.
(3) すべての自然数に対し,とは互いに素である.このことと(2)の結果を用いて,をみたす自然数とに対し,が成り立つことを示せ.
(4) をみたす自然数との最大公約数をとすると,との最大公約数はであることを示せ.ただし,必要であれば,枠で囲まれたユークリッドの互除法の説明文で使用されている記号を用いてもよい.
(5) (1)と(4)を用いて,との最大公約数を求めよ.