不定方程式の整数解を求めるには、ユークリッドの互除法を利用します。
(1) 50x+23y=1 まず、50と23に対してユークリッドの互除法を行います。
50=23⋅2+4 23=4⋅5+3 4=3⋅1+1 3=1⋅3+0 したがって、gcd(50,23)=1です。 次に、互除法の式を逆にたどります。
1=4−3⋅1 1=4−(23−4⋅5)⋅1=4⋅6−23⋅1 1=(50−23⋅2)⋅6−23⋅1=50⋅6−23⋅12−23⋅1=50⋅6−23⋅13 よって、50⋅6+23⋅(−13)=1 したがって、x=6,y=−13が解の1つです。 (2) 90x+37y=2 90と37に対してユークリッドの互除法を行います。
90=37⋅2+16 37=16⋅2+5 16=5⋅3+1 5=1⋅5+0 したがって、gcd(90,37)=1です。 次に、互除法の式を逆にたどります。
1=16−5⋅3 1=16−(37−16⋅2)⋅3=16⋅7−37⋅3 1=(90−37⋅2)⋅7−37⋅3=90⋅7−37⋅14−37⋅3=90⋅7−37⋅17 よって、90⋅7+37⋅(−17)=1 したがって、90⋅7+37⋅(−17)=1の両辺に2をかけると 90⋅14+37⋅(−34)=2 したがって、x=14,y=−34が解の1つです。 (3) 62x−23y=5 62x+(−23)y=5 62と23に対してユークリッドの互除法を行います。
62=23⋅2+16 23=16⋅1+7 16=7⋅2+2 7=2⋅3+1 2=1⋅2+0 したがって、gcd(62,23)=1です。 次に、互除法の式を逆にたどります。
1=7−2⋅3 1=7−(16−7⋅2)⋅3=7⋅7−16⋅3 1=(23−16⋅1)⋅7−16⋅3=23⋅7−16⋅10 1=23⋅7−(62−23⋅2)⋅10=23⋅27−62⋅10 よって、62⋅(−10)+23⋅(27)=1 したがって、62⋅(−10)+(−23)⋅(−27)=1の両辺に5をかけると 62⋅(−50)+(−23)⋅(−135)=5 62⋅(−50)−23⋅(−135)=5 したがって、x=−50,y=−135が解の1つです。 (4) 103x−38y=10 103x+(−38)y=10 103と38に対してユークリッドの互除法を行います。
103=38⋅2+27 38=27⋅1+11 27=11⋅2+5 11=5⋅2+1 5=1⋅5+0 したがって、gcd(103,38)=1です。 次に、互除法の式を逆にたどります。
1=11−5⋅2 1=11−(27−11⋅2)⋅2=11⋅5−27⋅2 1=(38−27⋅1)⋅5−27⋅2=38⋅5−27⋅7 1=38⋅5−(103−38⋅2)⋅7=38⋅19−103⋅7 よって、103⋅(−7)+38⋅(19)=1 したがって、103⋅(−7)+(−38)⋅(−19)=1の両辺に10をかけると 103⋅(−70)+(−38)⋅(−190)=10 103⋅(−70)−38⋅(−190)=10 したがって、x=−70,y=−190が解の1つです。 