逆元の計算方法

質問

逆元を計算するのにユークリッドの互除法というのでできると聞きました。
でも、ユークリッドの互除法っていうのは最大公約数を求めるのに使うのですよね？どうやって逆元を求めるんですか？たとえば、13を法としたとき5の逆元はどうやって求めるのですか？

回答No.1

zabuzaburo · ベストアンサー

ここで言う逆元とは、おそらく「乗法の」逆元のことですね？
ご質問で出された例で言えば、
5y ≡ 1(mod 13)となるyを求めよ、という意味だと思います。
この場合なら逆元は8で、
5×8 = 40 = 13×3 + 1 ≡ 1(mod 13)となっています。
すなわち、13p + 5q = 1となる整数p,qを
一組求めれば、そこから逆元は求まります。

いま、便宜的に「13×● + 5×▲」の形を
「基準形」と呼ぶことにします。
目標は「『1』を基準形に書き直す」ことになりますね。

これを行なうにあたってEuclid互除法がどのように役立つのか？
まず13と5に対し互除法を実行してみます。
13 ÷ 5 = 2 余り 3
5 ÷ 3 = 1 余り 2
3 ÷ 2 = 1 余り 1
というふうに、13と5は互いに素ですから、
「余りが1になる」まで行き着きます。

さて、上の式たちを「余り = ……」の形に書き換えると
(a) 3 = 13 - 5×2
(b) 2 = 5 - 3×1
(c) 1 = 3 - 2×1
となります。(a)を見ると、
「『3』が基準形に書き直されたもの」
と見ることができます。
すると、これを(b)に代入すれば
(b')2 = 5 - (13 - 5×2)×1 = 13×(-1) + 5×3
と、『2』も基準形に書き直されました。
さらに(a)と(b')を(c)に代入すれば
1 = (13 - 5×2) - [13×(-1) + 5×3]×1
= 13×2 + 5×(-5)
と、ついに『1』が基準形で表されたことになります。

以上より、5×(-5) ≡ 1(mod 13)
したがって「y = -5 + 13n」の形をしたものはすべて
5y ≡ 1(mod 13) を満たします。
n = 1とすれば逆元8が求まります。

もう1つだけ例題をやってみましょう。
「31を法とする12の乗法の逆元は？」
▼印は基準形で書かれた箇所です。
(解)互除法にて
31 = 12×2 + 7
12 = 7×1　+ 5
7 = 5×1 + 2
5 = 2×2 + 1
すなわち
(a)7 = 31 - 12×2▼
(b)5 = 12 - 7×1
(c)2 = 7 - 5×1
(d)1 = 5 - 2×2
(a)を(b)に代入して
(b')5 = 12 - (31 - 12×2) = 31×(-1) + 12×3▼
(a)(b')を(c)に代入して
(c')2 = (31 - 12×2) - [31×(-1) + 12×3]×1 = 31×2 + 12×(-5)▼
(b')(c')を(d)に代入して
1 = [31×(-1) + 12×3] - [31×2 + 12×(-5)]×2 = 31×(-5) + 12×13▼
したがって12×13 ≡ 1(mod 31)すなわち逆元は13となります。

参考URL：

http://www.nara-edu.ac.jp/~asait/c_program/sample/euclid.htm

補足

丁寧な回答ありがとうございます。
ですが、僕の勉強不足でわからないところが多々ありますのでよろしければ教えてください。
まず、13p+5q=1となるものを求めれば、なぜ逆元が求まるのですか？
それと、2=5-(13-5*2)*1=13*(-1)+5*3の真ん中から右の式へはどのように考えるのですか？

回答No.4

zabuzaburo

自動処理については、機能的にはできると思いますが
私はよく知りません(ごめん(^^;)実はVBをあまり使ったことがないのです)。

「Do while(1)」と書くと「Loop」までを無限に繰り返します。
このプログラムでは
途中の「If ... Then GoTo Ext」で「:Ext」の位置に飛ぶことで
ループを抜け出しています。

Int(x)は「xを超えない最大の整数」です。
例えばInt(3.14) = 3、Int(-4,2) = -5となります。

お礼

何回もありがとうございました。
自動処理についてはまた質問してみます。

回答No.3

zabuzaburo

ExcelのVBAのプログラムを示します。
セルA1に値を、B1に法を入れて走らせれば
C1に最大公約数が、D1に逆元が表示されます。
不当な値を入れた場合の処理は
盛り込んでいないので注意してください。

Sub Euclid()

a = Cells(1, 1): b = Cells(1, 2)
x = a: y = b: z = 1: w = 0

Do While (1)
q = Int(x / y)
r = x - q * y
If r = 0 Then GoTo Ext
x = y
y = r
tmp = z
z = w
w = tmp - q * w
Loop

Ext:
w = w - (Int(w / b)) * b
If w < 0 Then w = w + b

Cells(1, 3) = y
If y = 1 Then Cells(1, 4) = w Else Cells(1, 4) = "逆元なし"

End Sub

補足

Do while (1)とIntは、どういう意味なんですか？
あと、数値とか法の数とかを変えたときに勝手にマクロを実行するようにできますか？

回答No.2

zabuzaburo

「補足」を拝見しました。
分からないところがあれば何度でも聞いてください。

>13p+5q=1となるものを求めれば、なぜ逆元が求まるのですか？

逆元の定義はＯＫですか？
「自分と演算したら単位元になる相手」でしたね。
んでもって単位元とは
「誰と演算しても相手を変化させないヤツ」です。
modの世界では加法の単位元は0、乗法の単位元は1です。
したがって、「5の(mod 13)における乗法の逆元」といえば、
5×● ≡ 1(mod 13)、すなわち
[5×●] ÷ 13 = ■ 余り 1
となる●を求めればよい。

例えば、あてずっぽうに「●は7かな？」と試すと、
5 × 7 = 35
35 ÷ 13 = 2 余り 9
となって、余りが1にならないのでダメ(逆元でない)です。
これに対し「●は8だろうか」と試せば
5 × 8 = 40
40 ÷ 13 = 3 余り 1
となり、「ビンゴ！」です。
上の2式をまとめて書き直すと、
5×8 = 13×3 + 1
という形をしています。「13×3」を移項すれば
13×(-3) + 5×8 = 1
となり、右辺の「1」を左辺の「13p + 5q」の形に
書き換えたことになります。
だから、「1」を「基準形」に変形することが目標となるわけです。

>2=5-(13-5*2)*1=13*(-1)+5*3の真ん中から右の式へはどのように考えるのですか？

これは文字で書けば一目瞭然です。
数字のままだとどうしても計算してしまいたくなってしまいますよね(^^;)
そこをグッとこらえて、13と5は崩さずに変形しているのです。
なにせ「2」というシンプルな数を
わざわざ「13p + 5q」の形にしたいわけですから。
いま、13をs、5をtと書くことにして、
同じことをやり直してみます。
(a)3 = s - 2t
(b)2 = t - 3×1
(a)の「3」を(b)に代入すると
(b')2 = t - (s - 2t)×1 = -s + 3t
これを数字に戻すと
(b')2 = 13×(-1) + 5×3
となります。

補足

ありがとうございます。
わかりやすい説明で、すぐに理解することができました。
参考URLにC言語によるプログラムがあったんですけど、VBではないですか？
あと、EXCELでこれをするにはどうしたらいいですか？