拡張ユークリッド互除法による乗法逆元の求め方

こんにちは。
タイトルの通りの質問なのですが、過去ログを参考にしても特別分からないところがあったため、質問させて下さい。

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の条件が取り入れられてないのが原因だと思いますが、どう使えばいいかわからないです。
どなたか正しい解法を教えてください。
よろしくお願いします。

No.1 ベストアンサー 回答者： alice_44 回答日時： 2013/05/24 21:29

それでいいじゃん。

x ≡ -14 ≡ 17 (mod 31)

この回答へのお礼

た、確かに。
よくみたらなりますね…。

なんにせよ助かりました、ありがとうございます！モヤモヤが解消されました！

お礼日時：2013/05/25 16:08