491.(ユークリッドの互除法】 ユークリッドの互除法を用いて次の2数の最大出
492. [ユークリッドの互除法の利用】 次の分数を既約分数にせよ。 また,既約州
らが互いに素である自然数で,整数x,yについて
·正の整数a, bの最大公約数をdとすると, ax+by=d
yはaの他。
=by が成り立つならば, x はらの倍数でありて
を満た
しい。
互除法
考え方
ニ元ー次
不定方程式
である。
整数x, yが存在する。
A
解
*(3) 9797 9991
数を求めよ。
(2) 2952 1368
L
*1) 102 595
であれば,そのまま答えよ。
247
323
357
329
343
417
493.ニ元一次不定方程式】 次の不定方程式の整数解をすべて求め上
(2) 5(x+1)=3y
*3) 2x+7y-7=0
*1) 3x-4y=0
494. [ニ元一次不定方程式】 次の不定方程式は整数解をもつか。
(2) 3x-8=15y
(1) 4x-2y=1
495
B
例題 77 ユークリッドの互除法の利用
496
ユークリッドの互除法を利用して, 不定方程式 7x+17y=1 を満たす整数
x, yの組を1つ求めよ。
え方 7と17について, ユークリッドの互除法の手順を逆にたどって考える。
解
17=7×2+3 0
のより, 1=7-3×2
Oより, 3=17-7×2
これを③に代入すると,
1=7-(17-7×2)×2
7=3×2+1 ……②
49
C
*49
=7-17×2+7×4
=7×5-17×2
よって, 7×5+17x(-2)=D1 より,
(x, y)=(5, -2)
49