合同算術と中国剰余定理

合同

合同（Congruence Modulo）は整数の間の関係（同値関係）の一つです。二つの整数 $a$ と $b$ を同じ正の整数 $n$（法）で割ったとき、余りが同じであれば、$a$ と $b$ は $n$ を法として合同であるといい、次のように書きます。

$a \equiv b \ (\text{mod } n)$

例えば

$11 \equiv 5 \ (\text{mod } 3)$

$38 \equiv 14 \ (\text{mod } 12)$

負の数にも使えます。例えば

$-8 \equiv 7 \ (\text{mod } 5)$

数学や暗号学では、「巨大な数」を扱わなければならない場面がよくあります。

• 素因数分解
• 公開鍵暗号
• グラハム数、TREE(3)

見たこともない巨大な数を前にすると、つい身構えてしまい、どう扱えばいいのか分からなくなります。合同を使えば、大きな数をグループに分類できます。例えば $\text{mod } 7$ なら、すべての自然数を $7$ つのグループに分けられます。

余り	数
1	1、8、15、...
2	2、9、16、...
3	3、10、17、...
4	4、11、18、...
5	5、12、19、...
6	6、13、20、...
0	7、14、21、...

$131231312313131$ という数を見ると馴染みがないと感じますが、$7$ で割ると $2$ 余る、つまり $131231312313131 \equiv 2 \ (\text{mod } 7)$ だと分かれば、この数は「$2$、$9$、$16$ などと同じグループ」だと分かり、少なくとも基本的なイメージは持てます。

加法の性質

もし

$a \equiv b \ (\text{mod } n)$

$c \equiv d \ (\text{mod } n)$

ならば

$a + c \equiv b + d \ (\text{mod } n)$

乗法の性質

もし

$a \equiv b \ (\text{mod } n)$

$c \equiv d \ (\text{mod } n)$

ならば

$a \times c \equiv b \times d \ (\text{mod } n)$

ここからさらに、$a \equiv b \ (\text{mod } n)$ ならば次のことが導けます。

$a^k \equiv b^k \ (\text{mod } n)$

$ma \equiv mb \ (\text{mod } n)$

例題

1. $4096 \equiv \ ? \ (\text{mod } 13)$
2. $2^{100} + 2^{50} \equiv \ ? \ (\text{mod } 13)$

Ans.

1.

$4096 = 13 \times 315 + 1 \equiv 1 \ (\text{mod } 13)$

2.

$2^{12} = 4096 \equiv 1 \ (\text{mod } 13)$

$2^{100} = \left(2^{12}\right)^8 \times 2^4 \equiv 1^8 \times 16 = 16 \equiv 3 \ (\text{mod } 13)$

$2^{50} = \left(2^{12}\right)^4 \times 2^2 \equiv 1^4 \times 4 = 4 \ (\text{mod } 13)$

$2^{100} + 2^{50} \equiv 3 + 4 = 7 \ (\text{mod } 13)$

逆元

もし

$ab \equiv 1 \ (\text{mod } n)$

ならば、$b$ を $n$ を法とする $a$ の逆元（Modular multiplicative inverse）と呼び、次のようにも書けます。

$a^{-1} \equiv b \ (\text{mod } n)$

例えば $\text{mod } 11$ のもとで、$3$ の逆元は $\{\, 4 + 11z \mid z \in \mathbb{Z} \,\}$、つまり $\{\ldots, -18, -7, 4, 15, 26, \ldots\}$ です。$3 \times 4 = 12 \equiv 1 \ (\text{mod } 11)$ だからです。

$a$ が $n$ を法とする逆元を持つ $\iff$ $a$ と $n$ が互いに素。逆元は拡張ユークリッドの互除法（Extended Euclidean）、または後述するフェルマーの小定理で求められます。

$a^{p-2} \equiv a^{-1} \ (\text{mod } p)$

フェルマーの小定理

フェルマーには有名な定理が二つあります。こちらは mod に関するもので、もう一つはフェルマーの最終定理です（「証明を書くには余白が狭すぎる」と言ったあれです）。

$p$ が素数で、$a$ が $p$ の倍数でないとき

$a^{p-1} \equiv 1 \ (\text{mod } p)$

または、別の形で書くと

$a^p \equiv a \ (\text{mod } p)$

上の例題の $2^{12} \equiv 1 \ (\text{mod } 13)$ は、まさに $a = 2$、$p = 13$ の場合です。

---

次の現象から、フェルマーの小定理の意味を感じ取ってみましょう。$2$ のべき乗を順に $13$ で割ると

$2^1, 2^2, \ldots, 2^{12} \equiv 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, \mathbf{1} \ (\text{mod } 13)$

$2^{13}, 2^{14}, \ldots, 2^{24} \equiv \htmlClass{math-highlight}{2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, \mathbf{1}} \ (\text{mod } 13)$

$2^{25}, 2^{26}, \ldots, 2^{36} \equiv \htmlClass{math-highlight}{2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, \mathbf{1}} \ (\text{mod } 13)$

$12$ 乗で $1$ に戻ったあと、もう一度 $2$ を掛けると $2$ に戻り、余りの列がまた最初から始まります。フェルマーの小定理が言っているのは、べき乗を素数 $p$ で割った余りは時計のように循環し、$p - 1$ 回ごとに一周するということです。

そのため $a^k \ (\text{mod } p)$ を計算するときは、$k$ を $p - 1$ で割った余りだけを見ればよく、時計が時間を $12$ で割った余りだけを見るのと同じです。例えば $100 = 12 \times 8 + 4$ なので、$2^{100} \equiv 2^4 \ (\text{mod } 13)$ となります。

中国剰余定理

伝説によると、前漢の武将・韓信は目の前の兵士が何人いるのか知りたくて、兵士を三人ずつ、五人ずつ、七人ずつ並ばせたところ、それぞれ 2 人、3 人、2 人余りました。

3 で割ると 2 余り、5 で割ると 3 余り、7 で割ると 2 余る数をすべて書き出してみます：

• 3 で割ると 2 余る：2、5、8、11、14、17、20、23...
• 5 で割ると 3 余る：3、8、13、18、23、28...
• 7 で割ると 2 余る：2、9、16、23...

共通する数は 23 ですが、さらに書き進めれば同じような数がまだ見つかるかもしれません。それらを求めるには、23 に 3、5、7 の最小公倍数である 105 を足していけばよく、考えられる数はすべて $23 + 105n$ となります。

書き出すのも一つの方法ですが、『算法統宗』には別の解き方が載っています。

三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百零五便得知

「廿一」は 21、「正半月」は 15 日のことです。つまり、3 で割った余りに 70 を、5 で割った余りに 21 を、7 で割った余りに 15 を掛けて足し合わせ、その合計を 105 で割った余りを取れば、23 のような最小値が得られるという意味です。

105 は 3、5、7 の最小公倍数で、70 は 3 で割ると 1 余り、5 と 7 では割り切れます。同様に 21 は 5 で割ると 1 余り、15 は 7 で割ると 1 余ります。

韓信の例（余り 2、3、2）を公式に当てはめてみましょう。乗法と加法の性質から

$N = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233$

とすると

$N \equiv 2 \times 1 + 3 \times 0 + 2 \times 0 = 2 \ (\text{mod } 3)$

$N \equiv 2 \times 0 + 3 \times 1 + 2 \times 0 = 3 \ (\text{mod } 5)$

$N \equiv 2 \times 0 + 3 \times 0 + 2 \times 1 = 2 \ (\text{mod } 7)$

各項は自分が担当する法でだけ余りを残し、ほかの法ではすべて $0$ になるので、三つの条件を別々に処理してから足し合わせられます。

最後に、$105$ は $3$、$5$、$7$ のどれで割っても余りが $0$ なので、$105$ の倍数を引いても余りは変わらず、$233 - 2 \times 105 = 23$ となります。

Reference

• Day 14:[離散數學]同餘（Mod）是什麼？
• 中国古代稀有的一个数学定理，孙子定理是什么？韩信点兵又是怎么回事？李永乐老师带你了解中国剩余定理
• 【漫士】所以，到底什么是傅里叶变换？