拡張ユークリッド互除法による乗法逆元の求め方
こんにちは。
タイトルの通りの質問なのですが、過去ログを参考にしても特別分からないところがあったため、質問させて下さい。
11^-1 ≡ x(mod 31)
このxを求めたいのですが、11x * 31y = gcd(11, 31)として解いたら、
-14 * 11 + 5 * 31 = 1
となってしまい、うまくいきません。
以下、自分なりの解法です。
-----------------------------------------------------
11^-1 ≡ x(mod 31)より、11x ≡ 1(mod31)
これは、11x + 31y = 1を示す。
gcd(11, 31) 11 = a, 31 = b とする
= gcd(31, 11) → b = 2a + 9 → 9 = -2a + b
= gcd(11, 9) → a = (-2a + b) + 2 → 2 = 3a - b
= gcd(9, 2) → -2a + b = 4(3a - b) + 1 ―(1)
= gcd(2, 1)
= gcd(1, 0) = 1
(1)の式より、-14a + 5b = 1
先ほどの式と照らし合わせて、(x, y) = (-14, 5)
したがって、11^-1 ≡ -14(mod 31)
-----------------------------------------------------
おそらく、11x > 31yの条件が取り入れられてないのが原因だと思いますが、どう使えばいいかわからないです。
どなたか正しい解法を教えてください。
よろしくお願いします。
お礼
ありがとうございます！助かりました。