一般化して ax + by = 1 を解こう。 互除法の結果 a = b・ q1 + r1 (1) b = r1・ q2 + r2 (2) r1 = r2・ q3 + 1 (3)で終わったとしよう。 ここで、(3) から逆に見れば 1 = r1 - r2・ q3 (1)や (2) から r1 と r2 を代入し直しせば = (a - b・ q1) -(b - r1・ q2 )・ q3 = a - b・(q1+1) + (a - b・ q1)・ q2 = a・ (1 + q2) - b・ ( 1 + q1 + q1・ q2) ここで x = (1+q2), y= -(1 + q1 + q1・ q2) と置けば それが、解である。 質問者の例では、簡単に q1 =q2 =q3 = 1 であったから、解は x = 2, y = - 3 である。 勿論 t = 0 及び 正負の整数として 、下記の
![ユークリッドの互除法で、一次不定方程式8x+5y=1の整数解を求めたいです。どうすればいいのか教えてください。 - 一般化してax+by... - Yahoo!知恵袋](https://cdn-ak-scissors.b.st-hatena.com/image/square/1d07bee2b75b182ba712690f3a3464c29972e28b/height=288;version=1;width=512/https%3A%2F%2Fs.yimg.jp%2Fimages%2Fks%2Fclap%2Fimage%2Fogp%2Fogp.png)