の整数
1次不定方程式と互除法
健康法の計算を逆にたどると、1次不定方程式の整数解の1つを見つ
けることができる。
たとえば, 26x+11y=1 の係数 26と11に互除法を適用すると,次
のようになる。
26=11・2+4
11=42+3
4=3・1+1
3=1・3
←変形すると 426-112
←変形すると 311-4-2
←変形すると 1=4-3-1
余りに着目して,この計算を逆にたどると
1=4-3・1=4-(11-4・2)・1
←26と11の最大公約数は1
= 4・3-11・1=(26-11・2) ・3-11・1
CAS 26.3-11.7
よって
第3章 整数の性質
26・3+11・(-7)=1
したがって, 26x+11y=1 の整数解の1つとして x=3, y=-7 が
得られる。
互いに素な2つの整数に互除法を適用すると、余りが0になる直前の
割り算の余りは必ず1になる。 そして、上のように互除法の計算を逆に
たどることができるので、次のことが成り立つ。
20
互いに素である整数の性質
整数a, b が互いに素であるとき, ax+by=1 を満たす整数x,
y が必ず存在する。
練習
26
(2) 24x+19y=1
次の方程式の整数解の1つを求めよ。