ユークリッドの互除法で、一次不定方程式８x＋５ｙ＝１の整数解を求めたいです。どうすればいいのか教えてください。 - 一般化してax+by... - Yahoo!知恵袋

一般化して 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 及び 正負の整数として 、下記の

[kiyo_hiko]

にゅっ