数学的帰納法によって解ける整数問題・考察(3)を示します。
考察(3)
58x+17y = 1 となる整数x,yをユークリッド互除法を用いて
求めることができる。
ヒント:58と17は互いに素である。
58と17の大公約数を求めるユークリッド互除法を用いる。
58 = 17×3+7 --- (1)
17 = 7×2+3 --- (2)
7 = 3×2+1 --- (3)
3 = 1×3 --- (4)
1 = 7-3×2 (3)を変形する。
= 7-(17-7×2)×2 (2)を用いて3を展開する。
= 7×5-17×2 整理する。
= (58-17×3)×5-17×2 (1)を用いて7を展開する。
= 58×5-17×17
したがって、x = 5,y = -17 を得る。