数Ａ ユークリッドの互助法の問題、解き方

質問

63Ｘ + 44 Ｙ = ２　を満たすＸとＹの組を１つ求める。

計算の式がわかりません。解き方の流れをくわしくお願いします。

回答No.1

f272 · ベストアンサー

63=44*1+19
44=19*2+6
19=6*3+1
ここまでが互助法です。上の式を（余り=...の形に直した上で）逆順に代入していきます。
1=19-6*3
1=19-(44-19*2)*3
1=19*7-44*3
1=(63-44*1)*7-44*3
1=63*7-44*10
だから
2=63*14+44*(-20)

回答No.2

178-tall

>63Ｘ + 44 Ｙ = ２
　　　↓
　19X + 44(Y+X) =
　19X + 44A = 2　:　A=Y+X
　　　↓
　19(X+2A) + 6A =
　19B + 6A = 2　:　B=X+2A
　　　↓
　B + 6(A+3B) =
　B + 6C = 2　:　C=A+3B　　(1)

… と、左辺 2 項の一方が 1 になるまで「互除」。

(1) から、一つの解ペア
　B=2, C=0
を得る。

あとは、X, Y まで逆向戻り。
　C=0=A+3*2 → A=-3*2=-6
　B=2=X+2A=X-2*6 → X=2+2*6=14
　A=-6=Y+X=Y+14 → Y=-6-14=-20
まで戻り、一つの解ペア
　X=14, Y=-20
を得る。

[参考]　一般解は、
　X=14-44k
　Y=-20+63k
(k は整数)