は141 の倍数,すなわち, x-7= 58k, y-17= 141k (k:整数)となる。
最大公約数が1であることを,ユークリッドの互除法で求めるんだね。
ヒントリのをみたす1組の整数解 (xi, yi) を求めるためには, 141 と 58の
不定方程式とユークリッドの互除法(I)
講義
*2
難易度
対階記問題 60
数であれば、
CHECK3
次不定方程式の整数解(x,y) の組をすべて求めよ。
0(x,y:整数)
CHECK ||
CHECK2
CHECK
こよいものと
141x-58y= 1
(関西大*)
してSの式を
講義
表現できるは
解答&解説
Hと 58の最大公約数gを,右の
ようにユークリッドの互除法で求め
た結果,g=1となった。
ここで,2, 3, ④を変形して,
141 = 58×2+25
58= 25×2+8
講義
25 = 8×3+1
8= 1×8
(141と58
は互いに素
(141-2×58 =D 25
2
最大公約数
58 -2×25 = 8
25 -3× 8=
1
ミので,まず,
ここで,3'をの'に代入して, 25-3·(58-2×25) = 1
7-25 -3·58 = 1
の'
さらに2'をの"に代入して, まとめると
切れることを
w.
1(141 -2× 58) -3·58=1,141×7-58×17=1
5
t
((x1, yi) = (7, 17) が, ①の1組の解だ。
べる。
よって,O-6より,141(x-7)-58(y-17)=0
141(x-7) = 58(y -17)
.6 となる。
(58k
141k(k:整数)
き,
*で, 141 と 58 は互いに素より,⑥から,r-7は 58の倍数, y-17
き,
は3の倍数
割り切れる
割り切れる。
……(終)
195
CO
O○
場合の数と確率
敷整数の性質
図形の性質