(1)
63x+29y=1
x=6, y=-13 は ① の整数解の1つである。
よって
①-② から
すなわち
①
63.6+29(-13)=1
63(x-6)+29(y+13) = 0
63(x-6)=-29(y+13)
③
63 29 は互いに素であるから, x-6は29の倍数である。
よって, k を整数として, x-6=29k と表される。
これと③から
y+13=-63k
したがって, 求める整数解は
x=29k+6,y=-63k-13 (k は整数)
参考 63と29に互除法の計算を行うと, 次のようになる。
63=29.2+5
移項すると 563-29.2
29=5.5 +4
移項すると
429-55
5=4・1+1
移項すると1=5-4・1
よって
1=5-4・1=5-(29-5・5)・1=5・6+29・(−1)
=(63-29.2)・6+29・(-1)=636+29 (13)