目次
1.そもそもモジュラ逆数とは？
2.モジュラ逆数の計算
3.拡張ユークリッドの互除法
4.本題のモジュラ逆数
5.おわり
そもそもモジュラ逆数とは？
\displaylines{
10 + 4 \equiv 2 \pmod 3 \\
9 - 4 \equiv 1 \pmod 2 \\
11 \times 5 \equiv 6 \pmod 7
}
以上の計算はとても簡単に終わらせられる。
7 \div 5 \equiv ? \pmod 3
こちらはどうだろうか。$ \frac{7}{5} $を$3$で割った余り？どういうことだろうか。
そもそも、余りの計算は整数に適用されるものだから、$1.4$には適用できないはずだ。
ここで考えるべきが逆数である。
$7\div5$を計算するとき、ほとんどの人が無意識的に$7\times\frac{1}{5}$へと変換する。
つまり、割る数を逆数に変換する。
しかし、「実数$x$の逆数は$\frac{1}{x}$である」というのは、一般的な場合である。
一方で、今回は余りの計算という特別な場合であるため、これは適用できない。
そこで、特別な逆数を考えるため一般的な逆数に注目してみる。
$x$の逆数を$x^{-1}$とすると、このように表せる。
x\times x^{-1}=1
特別な逆数もこれと似たように表せばいい。
x\times x^{-1} \equiv 1 \pmod m
このときの$x^{-1}$がモジュラ逆数となる。
モジュラ逆数の計算
x\times x^{-1} \equiv 1 \pmod m
このとき、$x^{-1}$がモジュラ逆数となることは先に述べた。
では、どのようにこれを求めればよいのだろうか。
まず、弄繰り回せるようにこれを方程式で表してみる。（$x$を区別するため$x^{-1}を$$I$で表す）
x \times I =m\times p + 1
これを変形する。
\displaylines{
x\times I - m \times p = 1 \\
x\times I + m \times (-p) = 1
}
すると、$ax+by=c$の形になった。
この一次不定方程式の性質はよく知られている。
一次不定方程式の重要な定理
(1) 「$x,yに関する不定方程式ax+by=cが整数解を持つ\Leftrightarrow cはgcd(a,b)の倍数$」
(2) 「$ax+by=1が整数解を持つ\Leftrightarrow aとbは互いに素$」
(2)より、$x\times I + m \times (-p) = 1$が整数解を持つには、
$x$と$m$が互いに素でなければならない。
逆に、$x$と$m$が互いに素ならば、整数解を持つことになる。
そして、この一次不定方程式の整数解を求められる非常に強力なアルゴリズムがある。
それが 「拡張ユークリッドの互除法」 である。
拡張ユークリッドの互除法
$ax+by=gcd(a,b)$の整数解を求めるアルゴリズム
ユークリッドの互除法のステップを逆順にたどり、式を構成することで整数解を求める。
例えば、$a=9,b=7$のとき、次のようなステップを踏む。
(9,7) \Rightarrow (7,2) \Rightarrow (2,1) \Rightarrow (1,0)
これらの間で行われる計算を式で表すと次のようになる。
\displaylines{
\color{dodgerblue}{9}=\color{green}{7}\times1+\color{orange}{2}\\
\color{green}{7}=\color{orange}{2}\times3+\color{deeppink}{1}\\
2=1\times2+0\\
1=0\times1+1
}
上から順に見てみよう。
最初に、$\color{dodgerblue}{9}$を$\color{green}{7}$で割った余り$\color{orange}{2}$を算出する。
次に、$\color{green}{7}$を$\color{orange}{2}$で割った余り$\color{deeppink}{1}$を算出する。
これを繰り返し、$0$が出てくればそこで終了する。
ここで、さらに考えるために式を整理してみよう。
具体的に、余りを左辺に移動させ、それ以外を右辺に移動させる。
\color{orange}{2}=\color{dodgerblue}{9}-\color{green}{7}\times1\tag{1}
\color{deeppink}{1}=\color{green}{7}-\color{orange}{2}\times3\tag{2}
\color{darkmagenta}{0}=\color{orange}{2}-\color{deeppink}{1}\times2\tag{3}
1=\color{deeppink}{1}-\color{darkmagenta}{0}\times0\tag{4}
どうだろうか。
$(9,7),(7,2),(2,1),(1,0)$がパッと分かるようになったのではないだろうか。
ここで、「式(4)の$\color{darkmagenta}{0}$」と「式(3)の$\color{darkmagenta}{0}$」はどちらも「2を1で割った余り」を表す。
これを代入してみる。
1=\color{deeppink}{1}-(\color{orange}{2}-\color{deeppink}{1}\times2)\times0\\
さらに、変形する。
1=\color{orange}{2}\times0+\color{deeppink}{1}\times1
(2,1)が現れた。
同様に、$\color{deeppink}{1}$を式(2)で置き換える。
\displaylines{
\begin{align}
1&=\color{orange}{2}\times0+(\color{green}{7}-\color{orange}{2}\times3)\times1\\
1&=\color{green}{7}\times1+\color{orange}{2}\times(-3)
\end{align}
}
(7,2)が現れた。
同様に…
\displaylines{
\begin{align}
1&=\color{green}{7}\times1+(\color{dodgerblue}{9}-\color{green}{7}\times1)\times(-3)\\
1&=\color{dodgerblue}{9}\times(-3)+\color{green}{7}\times4
\end{align}
}
この時点で、$9x+7y=1$の整数解が求められた。
$(x,y)=(-3,4)$である。
このようにユークリッドの互除法のステップを逆順していくと
$ax+by=c$の整数解が求められる。
式(4)以外は、再帰的に$ax+by=c$の式が与えられており、その$b$に自身の式の右辺を代入している。
式(4)は、$gcd(a,b)=gcd(a,b)\times1+0$が確定している。
すなわち、整数解が$(x,y)=(1,0)$だと決まっている。
また、以下の式を例にとると$\color{dodgerblue}{9}$は$-3$とかけられているだけである。
一方で、$\color{green}{7}$は$(-\color{green}{7})\times1\times(-3)+1=\color{green}{7}\times4$となり、先より少し複雑な計算が行われている。
\displaylines{
\begin{align}
1&=\color{green}{7}\times1+(\color{dodgerblue}{9}-\color{green}{7}\times1)\times(-3)\\
1&=\color{dodgerblue}{9}\times(-3)+\color{green}{7}\times4
\end{align}
}
これらを表現するために、関数exeuclid(a,b)を考える。（$a\gt b$）
exeuclid(a,b)は$ax+by=gcd(a,b)$を満たす整数解を返す。
もし、式(4)のような場合…つまり$b$が$0$のとき、既にユークリッドの互除法のステップが尽きているため、$(1,0)$を返せばよい。
そうでない場合は、少々複雑な計算をしなければならない。
ステップをさかのぼるとき、先のステップでの整数解を$(x,y)$とする。
今まで計算してきた結果から分かる通り、yは現在のステップのひとつの解としてそのまま返す。
もう一方の解は、式を展開し共通因数でくくることを考えると
-\frac{a}{b}\times y + x
と表せる。
これらをC++でコードに著したものが以下である。
#include<bits/stdc++.h>
using namespace std;
pair<int,int> exeuclid(int a, int b) {
if(b == 0) {
return make_pair(1, 0);
}
else {
auto [x,y] = exeuclid(b, a%b);
return make_pair(y, -(a/b) * y + x);
}
}
int main() {
int m, n;
cin >> m >> n;
auto [x,y] = exeuclid(m,n);
cout << x << "," << y << endl;
return 0;
}
ここでひとまず、拡張ユークリッドの互除法の説明が終わった。
次は、モジュラ逆数に取り掛かっていく。
本題のモジュラ逆数
x\times x^{-1} \equiv 1 \pmod m
これは、pを整数として、以下のように表せることをはじめに説明した。
x\times x^{-1} + m \times (-p) = 1
このときの$x^{-1}$がモジュラ逆数である。
そして、これを拡張ユークリッドの互除法を用いて求める。
コードは以下である。
#include<bits/stdc++.h>
using namespace std;
pair<int,int> exeuclid(int a, int b) {
if(b == 0) {
return make_pair(1, 0);
}
else {
auto [x,y] = exeuclid(b, a%b);
return make_pair(y, -(a/b) * y + x);
}
}
int modinv(int x, int m) {
auto [i,p] = exeuclid(x, m);
return i < 0 ? i + m : i;
}
int main() {
int x,m;
cin >> x >> m;
cout << modinv(x, m) << endl;
return 0;
}
おわり
ここまで読んでくださりありがとうございます。
最近始めた競プロで、モジュラ逆数というものを知りました。それについて調べている間に、記事にでもしてみれば理解が深まると思ったので、このような形で書いてみました。少しでも、だれかの役にたてていたら幸いです。