14 ユークリッドの互除法, 1次不定方程式
[1] 3x+5y=2を満たすすべての整数の組(x,y) を求めよ.
[2] (1) 15768の最大公約数を求めよ.
(2) 157x-68y=3 を満たすすべての整数の組(x, y) を求めよ.
解答
[1]
3x+5y=2
x=-1, y=1は ①を満たすから,
3(-1)+5・1=2
が成り立つ ①②より,
EL-
3(x+1)+5(y-1)=0
3(x+1)=5(−y+1)
...3
③の右辺は5の倍数なので左辺も5の倍
数であり, 3と5は互いに素であるから、
x+1=5k(kは整数)
x=5k-1
(大阪府立大/早稲田大)
DE:88-81-1
・・・ ① (Step 1) ① を満たす整数の解を1つ見つけ
る.この解を「特殊解」という
(Step 2) 問題の式①と,特殊解を代入した
式②を準備して, ①-② を計算
して,③のような形にする
(Step 3) 互いに素であることに注目して,
x (あるいはy) を整数kを用い
て表す
21