第2節 ユークリッドの互除法
137
例(1) 等式 24x+17y=1 を満たす整数 x, yの組を1つ求める。
8
24と 17 に互除法の計算を行う。
24 = 17·1+7
移項すると
7=24-17·1
17 =7·2+3
移項すると
3= 17-7·2
7=3·2+1
移項すると
1=7-3·2
よって 1=7-3·2
=7-(17-7·2).2
-3=17-7·2 を代入。
=7·5+17·(-2)
17, 7について整理。
= (24-17·1)·5+17·(-2)
-7=24-17·1 を代入。
= 24·5+17·(-7)
24, 17について整理。
ニ
24-5+17·(-7) =1
したがって, 求める整数 x, yの組の1つは x=5, y=-7
すなわち
の
位
世
Lまな 。