mod(合同式)を学んでみよう！(知識編)
導入(introduction)
ごきげんよう
まずは見てくれた皆さんに感謝を
(Mathlogって投稿後にも全然編集できるので全然途中でも投稿してるかも)
本記事では、整数の性質における強力な武器の一つである「合同式（モジュロ演算）」について
初学者レベルから成長していけるようにまとめてみた記事です。
今回あくまで性質などの知識を取り扱ってます！
つまりはそれをどう使うか？みたいなところには今回は触れません。(次回作とかで書くかもー?)
ですのであまり恐れず見てってくださいね。
で、ということはですよ皆さん、
性質→証明→性質→証明→
みたいな形になりますよね、
ここで合同式の性質についてですが、まずはその性質をおさえちゃってください。
要は証明を頑張るのは後にして何が言いたいのかしっかり理解してみてほしい。
そして簡単な性質については当たり前に思えたら完璧です！
学校ではあまり詳しく取り扱わないところも多いと聞きます。
しかしとても便利なのでぜひ知って友達に自慢しちゃいましょう！
(注意)
後半は唐突な難易度上昇のため初学の人は読まなくてOK
具体的には3,4章くらいまででOK
目次
- 第1章：等式の向こう側へ —— 合同式の導入と定義
- 第2章：合同式の四則演算 —— 割り算の壁を越える
- 第3章：代数への拡張 —— 多項式と冪乗の世界
- 第4章：合同式の古典的大定理たち
- 第5章：上級の扉 —— 位数と原始根（数論の深淵へ）
- 結び（次回予告：最強の武器をどう使うか？）
第1章：等式の向こう側へ —— 合同式の導入と定義
1.1 合同式がもたらす「世界の単純化」
例えば、$2^{100}$ の下一桁の数を求めたいとき、愚直に$100$回掛け算を行うのはちょっと大変すぎて厳しい。
しかし、私たちは「下一桁の本質は$10$で割った余りである」ということを感覚的に知っていたりします。(実験すれば見えてくるでしょう。)
常に$10$で割った余りのみ考えてみればいいのなら数字少ないし楽になりそうだよね？
(実際に$2$のべき乗やってみると)
$2→4→8→16→32→64→ \cdots $
一桁目だけ注目したら周期性ありそう!
あと一桁目って$10$で割った余りと同じか～
みたいになくらいで今はOK!
合同式は、このように「巨大な数を、その余りという極小の代表元に退化させて計算する」ための画期的なツールです。等式（$=$）と同じような感覚で余りを扱える心地よさを、まずは定義から体感していきましょう。
1.2 【前提知識】割り算の原理と「互いに素」
合同式の話を進めるにあたり、すべての基盤となる大前提を確認しておきます。
割り算の原理： 任意の整数 $a$ と、正の整数 $m$ に対し、
$$a = qm + r \quad (0 \le r < m)$$
を満たす整数 $q, r$ がただ一通りに定まります。この $r$ を「$a$ を $m$ で割った余り」と呼びます。約数: ある整数を余りなく(余り$0$)割り切ることのできる数。
倍数: ある整数を$0,\pm1,\pm2,\pm3\cdots$と整数倍した数
$m \mid n$ : $n$ が $m$ の倍数である($m$ が $n$ を割り切る)の数式表現
要は約数が左で、倍数が右とおさえておこう。$m \nmid n$ :簡単に言うなら上の否定で、$n$が$m$の倍数ではない。
($\neq$の感覚でいいかも)素数: $2$以上の整数で自分と$1$以外の約数を持たない数
素因数: ある整数の約数になる素数のこと。
- 互いに素： 2つの整数 $a, b$ の最大公約数が 1 であるとき、$a$ と $b$ は「互いに素」であるといいます。
$a$と$b$の最大公約数を $\gcd(a, b) $ と表すことが良くありますが、それを用いると、
$\gcd(a,b)=1$と書けます。
→(要は共通の素因数を持たないと考えていいです)
割り算
割り算くらい知ってますなんて人も一応確認ですね。
逆に、$a$という整数が、$m$で割った余りが$r$です。と言われたら、
整数$k$を用いて、$a=mk+r$とおける。ということをよくします。
よく偶数奇数をそれぞれ
$n=2k,n=2k+1$と置いてるのはまさにそれですね。
互いに素
互いに素という概念にはかなり注目です。
整数分野では超大事。
具体的に問題で見てみましょう。
(〇が互いに素、×が互いに素ではないとしますね。)
$2$と$10$→(どちらも$2$を含むので)×
$2$と$3$→($2$は$2$のみ、$3$は$3$のみなので)〇
$3$と$10$→($3$は$3$のみ、$10$は$2,5$を持つが共通してないので)〇
$6$と$10$→(どちらも$2$を含むので)×
$10$と$21$→($10$は$2,5$、$21$は$3,7$で共通してないので)〇
↑素因数分解して同じ素数がない時互いに素って呼べるから簡単ね
$(1$と$1$),($1$と$2$),($1$と$3$)→〇
定義にのっとたら、$1$にはそもそも素因数がない。
(注意)素数とは$2$以上の整数で自分と$1$以外の約数を持たない数
したがって$1$と共通の素因数を持てるものはないので$1$は任意の整数と互いに素なのですね。
($2$と$3$),($3$と$4$),($4$と$5$)→〇
勿論一つづつ素因数分解考えてもいいですが実は連続する$0$でない$2$つの整数は互いに素なんです。
今回は詳しく取り扱いませんが結構使うのでいつかの記事で紹介しますね。
1.3 合同式の定義（負の余りを受け入れる）
少し硬派な書き方をする(多分わかりにくい)ので一旦軽く流してそのあとの簡単な説明読んで戻ってきてみてね。
2つの整数 $a, b$ を正の整数 $m$ で割った余りが等しいとき、$a$ と $b$ は $m$ を法（ほう）として合同であるといい、次のように表します。
$$a \equiv b \pmod m$$
これを代数的に扱いやすくするため、同値な性質を合同式のとして次の定義も見てみましょう。
$a \equiv b \pmod m \iff a-b\equiv0\pmod{m}$ $\iff (a - b)$が$m$の倍数である。
※ 「$a-b$ が $m$ の倍数である($m$ が $a-b$ を割り切る）」
は、数式で$m \mid (a-b)$と表現できる。
※ $\mod m $で、議論を続けていく場合、以下法を$m$とする。と記述して毎回$\pmod m$と書かなくてもよい。
■要はどゆこと?
$\mod{m}$というのはまず世界を$m$で割った余りに限定しますよと認識して欲しいです。
以降具体で見てみましょうか。
具体例
世界を$6$で割った余りに限定、つまり$\mod{6}$を考えてみましょう。
するとある整数$n=1,2,3,4,5,6,7,8\cdots$を $6$で割るとその余りは、
$1,2,3,4,5,0,1,2\cdots$となります。
(その余りの種類は$0,1,2,3,4,5$しかないことが分かりますね。)
$\mod{6}$の世界では$6$で割った余りのみに数を限定しますね。
ここで$7,13$はいずれも$6$で割った余りが$1$となりますから、この
$\mod{6}$という世界においては同じ(区別できない)ものとして認識されます。
故に、これを合同式で表現すると
$1\equiv7\equiv13\pmod{6}$
となります。
ここで余りが同じものの差を考えてみます。
具体的に余りが$1$のものを見ると
$6$で割って余り$1$のものは$n=6k+1$,$m=6l+1$ ($k,l$は整数)
と置けますね。
$n-m=(6k+1)-(6l+1)=6k-6l=6(k-l)$
となります。
余りが$1$でなくても同様に余りが同じであればその差は$6$の倍数ですね。
それを用いた定義がもう一つの定義ですがまあ大雑把に今は理解初てみましょう。
■差の定義のうまみ
この「差が $m$ の倍数」という定義の最大の功績は、負の余りを極めて自然に導入できる点にあります。例えば、$5$ を $6$ で割ると余りは $5$ ですが、
$5$と$-1$の差を考えると$5 - (-1) = 6$ となり、
これは $6$ の倍数（$1$倍）であるため、以下の合同式が成立します。
$$5 \equiv -1 \pmod 6$$
「$6$ に $1$ 足りない数」という直感を、マイナスを用いることで等式のようにスマートに表現できるのが合同式の大きな強みです。
☆補足
$a \equiv b \pmod m \iff a-b\equiv0\pmod{m}$
これは次の合同式の四則演算の性質からめちゃ当たり前に見えます。
$ $
$ $
第2章：合同式の四則演算 —— 割り算の壁を越える
2.1 和・差・積の保存（証明付き）
合同式の本領は、通常の等式と同様に「足し算・引き算・掛け算」を自由に行ってよいという点にあります。
証明は一応軽くしますが正直大した難易度ではありません。
結論がめちゃ重要です。
$a \equiv b \pmod m$ かつ $c \equiv d \pmod m$ のとき、以下の性質が成り立ちます。
- $a + c \equiv b + d \pmod m$
- $a - c \equiv b - d \pmod m$
- $ac \equiv bd \pmod m$
定義から$a=mk+b,c=ml+d$($k,l$は整数)と置ける。
$a+c=(mk+b)+(ml+d)=m(k+l)+(b+d)$
$m(k+l)$は$m$の倍数であるから、整数$q$を用いて$m(k+l)=mq$とおけ、
$a+c=mq+(b+d)$となり示される。
$a-c$ も同様に示してみてね。
☆補足
さて、和・差が成り立つので
$a \equiv b \pmod m \iff a-b\equiv0\pmod{m}$
を考えてみよう
$a \equiv b \pmod m$ の両辺から$b$を引いて、
$a-b \equiv 0 \pmod m$が成り立つ。
当然$b$足せば元の式に戻る。
当たり前ですね
ではせっかくなのでその差の形の定義を利用して次の性質を示そう。
定義より、$a - b = k_1 m$, $c - d = k_2 m$ となる整数 $k_1, k_2$ が存在します。これらを変形すると $a = b + k_1 m$, $c = d + k_2 m$ です。
ふたつの積を考えると、
$$ac = (b + k_1 m)(d + k_2 m) = bd + m(bk_2 + dk_1 + k_1 k_2 m)$$
$bd$ を左辺に移行すると、
$$ac - bd = m(bk_2 + dk_1 + k_1 k_2 m)$$
となり、右辺は $m$ の倍数であることが分かります。したがって、$m \mid (ac - bd)$ が示され、定義より $ac \equiv bd \pmod m$ が成り立ちます。
2.2 割り算の制限：なぜ「互いに素」が必要なのか（証明付き）
和差積が完璧に成り立つ一方で、割り算（両辺を同じ数で割る操作）には厳しい制限がかかります。ここが初学者が必ずぶつかる「割り算の壁」です。
例えば、$\pmod 6$ の世界を考えます。$2 \times 3 = 6 \equiv 0$、そして $2 \times 0 = 0 \equiv 0$ なので、当然以下が成り立ちます。
$$2 \times 3 \equiv 2 \times 0 \pmod 6$$
しかし、ここから両辺を安易に $2$ で割って $3 \equiv 0 \pmod 6$ とすることはできません（$3$ を $6$ で割った余りは $3$ であり、$0$ ではないため、これは明らかに誤りです）。
合同式において、両辺を共通の因数 $c$ で割るためには、「割る数 $c$ と 法 $m$ が互いに素であること」が絶対条件となります。
$\gcd(c, m) = 1 $つまり$c,m$が互いに素のとき
$$ac \equiv bc \pmod m \implies a \equiv b \pmod m$$
(両辺を$c$で割れる)
$ac \equiv bc \pmod m \iff m \mid (ac - bc) \iff m \mid c(a - b)$ となります。
いま、$\gcd(c, m) = 1$ （$c$ と $m$ は共通の素因数を持たない）であるため、$c(a-b)$ が $m$ の倍数になるためには、因数である $a-b$ 自身が $m$ の倍数であるしかありません。したがって $m \mid (a - b)$ より、$a \equiv b \pmod m$ が示されます。
2.3【＋α】割り算の裏に潜む「逆元」の正体
2.2節で「割り算のルール」を学びましたが、ここで一歩深く足を踏み入れて、数論の世界における衝撃の舞台裏を覗いてみましょう。
実は、合同式の世界には……「割り算」という演算そのものが存在しません。
「え？ さっき両辺を $c$ で割るって言ったじゃん！」と思うかもしれませんが、数学的には「掛けると $1$ になる最強の相棒を掛け算している」だけなのです。
通常の世界（実数など）なら、$2$ の相棒は $\frac{1}{2}$ ですよね。$4 ÷ 2$ は、$4 \times \frac{1}{2}$ を計算しているのと同じです。
しかし、私たちが今いるのは、分数なんて存在しない「整数の世界（$\mod m$）」です。
じゃあ、どうするのか？
「掛けて $1$ になる『整数』」を世界から探し出して、それを掛け算するのです！
■ 具体例で相棒を探してみよう
世界を $5$ で割った余り、つまり $\mod 5$ の世界で考えてみましょう。
この世界で「$2$ で割る」という操作をしたいとします。
私たちが探すべきは、「 $2$ に何を掛けたら $\mod 5$ で $1$ になるか？」です。
- $2 \times 1 = 2 \equiv 2$
- $2 \times 2 = 4 \equiv 4$
- $2 \times 3 = 6 \equiv 1$ ← みつけた！！！
なんと、 $\mod 5$ の世界では $2 \times 3 \equiv 1$ が成り立ちます。
つまり、この世界における $2$ の割り算の相棒（逆数みたいなもの）は、分数ではなく $3$ という立派な整数 なのです。
この「掛けると $1$ になる相棒」のことを、数学の言葉で 逆元（ぎゃくげん） と呼び、数式では $2^{-1}$ や $c^{-1}$ のように表したりします。
意味を繋げると、 $\mod 5$ において 「 $2$ で割る」とは「 $3$ を掛ける」ことと同義 なのです！
（例： $4 ÷ 2 \equiv 4 \times 3 = 12 \equiv 2$ となり、普通の割り算とちゃんと一致しますね。）
■ なぜ「互いに素」じゃないと壁にぶつかるのか？
先ほど「割る数 $c$ と法 $m$ が互いに素じゃないと割り算しちゃダメ」というルールを学びました。逆元の視点からこれを見ると、ものすごくスッキリ納得がいきます。
実は、「 $c$ と $m$ が互いに素であるとき、かつそのときに限って、 $c$ の逆元（相棒）が世界にただ一つだけ存在する」 という性質があります。
もし互いに素じゃない場合（例えば $\mod 6$ の世界における $2$ など）は、いくら整数を掛けても $2 \times x \equiv 1 \pmod 6$ になるような $x$ は絶対に存在しません。（ $2x - 6k = 1$ になる整数解がないためです）。
相棒（逆元）がこの世に存在しないから、割り算ができない。
これが「割り算の壁」の本当の正体だったわけです。
☆ちょっと未来の話
この先、第4章の「ウィルソンの定理」や、第5章の「ラグランジュの定理の証明」で、唐突に 逆元 や $c_1^{-1}$ という記号が当たり前のような顔をして登場します。
そのときは、この「割り算の代わりに掛ける、最強の相棒のことだな」と思い出してあげてくださいね！
2.4 発展：互いに素でない場合の割り算と「法の変化」（証明付き）
では、割る数 $c$ と法 $m$ が互いに素でない場合はどうなるのでしょうか。最大公約数を $\gcd(c, m) = d \quad (d > 1)$ とします。このとき、両辺を $c$ で割ると、なんと「法そのものが変化」します。
$c, m$ が互いに素ではない、つまり $\gcd(c, m) = d \quad (d > 1)$ のとき、
$$ac \equiv bc \pmod m \implies a \equiv b \pmod{\frac{m}{d}}$$
(式は$c$で割られるが法は$d$で割られる。)
$\displaystyle\frac{c}{d}$ と $\displaystyle\frac{m}{d}$ は互いに素である。
証明
$\displaystyle\frac{c}{d},\frac{m}{d}$が共通素因数$p$を持つと仮定する。
このときある整数$k,l$を用いて
$\displaystyle\frac{c}{d}=pk , \frac{m}{d}=pl$とおける。
故に$c=dpk , m=dpl$となる。
$c,m$はいずれも$dp$を約数に持ち、$c,m$の最大公約数が$d$であることに矛盾。
故に$\displaystyle\frac{c}{d},\frac{m}{d}$が共通素因数$p$を持つと仮定は誤りである。
題意は示された。
$ac \equiv bc \Longleftrightarrow ac-bc=c(a-b)\equiv0\pmod m$
$m \mid c(a - b)$ ($c(a-b)$は$m$の倍数)より、
ある整数 $k$ を用いて $c(a - b) = km$ と書けます。
この等式の両辺を最大公約数 $d$ で割ると、
$$\frac{c}{d}(a - b) = k \cdot \frac{m}{d}$$
となります。ここで、(補題)$\displaystyle\frac{c}{d}$ と $\displaystyle\frac{m}{d}$ は互いに素であるため、
先ほどと同様の議論から、$a - b$ は $\displaystyle\frac{m}{d}$ の倍数でなければなりません。
∴$\displaystyle a-b\equiv0\pmod{\frac{m}{d}}$
したがって $\displaystyle a \equiv b \pmod{\frac{m}{d}}$ が成り立ちます。
先ほどの反例（$2 \times 3 \equiv 2 \times 0 \pmod 6$）にこれを適用してみましょう。割る数 $c=2$ と法 $m=6$ の最大公約数は $d=2$ です。公式に当てはめると、
$$3 \equiv 0 \pmod{\frac{6}{2}} \implies 3 \equiv 0 \pmod 3$$
となり、これは完全に正しい主張と確認できます。
共通因数によって、「法の世界（周期）のサイズそのものが小さく縮小する」というこの挙動は、上級レベルへのステップアップに不可欠な代ucionales感覚です。
この式の定性的な考え
？？？「互いに素でなければ割り算ができないのなら互いに素な世界にして考えればいいじゃない。」
ということです。
第3章：代数への拡張 —— 多項式と冪乗の世界
3.1 多項式合同定理 $f(a) \equiv f(b)$
積の保存性を繰り返し用いることで、自然数 $n$ に対して $a \equiv b \pmod m \implies a^n \equiv b^n \pmod m$ が成り立つことが分かります。これを極限まで推し進めると、以下の極めて強力な定理が導かれます。
$ a^n \equiv b^n \pmod m$を用いて次が成り立つ。
すべての係数が整数である多項式 $f(x) = c_n x^n + c_{n-1} x^{n-1} + \dots + c_1 x + c_0$ について、
$$a \equiv b \pmod m \implies f(a) \equiv f(b) \pmod m$$
この定理により、複雑な多項式に巨大な数を代入したときの余りを、代入する数自体をあらかじめ法 $m$ で小さく削っておくことで、一瞬で計算できるようになります。
3.2 冪乗の剰余（平方剰余・立方剰余の観察）
合同式の世界では、数を2乗（平方）、3乗（立方）したときの余りの挙動を調べることで、整数方程式（ディオファントス方程式）の不可能性を鮮やかに証明できたりします。
■平方剰余
例えば、任意の整数 $x$ について、$\mod 3$ での平方数 $x^2$ の余りをすべて観察してみましょう。
- $x \equiv 0 \implies x^2 \equiv 0 \pmod 3$
- $x \equiv 1 \implies x^2 \equiv 1 \pmod 3$
- $x \equiv 2 \equiv -1 \implies x^2 \equiv (-1)^2 \equiv 1 \pmod 3$
これより、平方数は $\pmod 3$ において「$0$ または $1$ しか取らない」（絶対に $2$ にはならない）という強力な縛りがあることが分かります。これらをさらに深く体系化したものが、のちの「平方剰余の相互法則」へと繋がる、数論の美しい一分野です。
さて、私は合同式ではマイナスを活用することを強くお勧めしているのですが、ここでその性質がいきてきます。
今度は$4$で割った余りを見ましょう
以下法を$4$とする。
全ての整数$x$は$x\equiv0,\pm1,2$より、これを二乗すると、
$x^2\equiv0,1,4\equiv0,1$となる。勘のいい読者なら察しがつきましたか?
そうです、二乗すると$\pm1$は$1$に、つまりはプラスマイナスは関係なくなります。
これ故に、平方数は$3$以上の数で割る場合、必ず余りの種類が減ることが分かります。
■立法剰余
登場することは少なめだと思いますが、かるく。
基本的には何で割った余りも減らないように見えますが、ちゃんと減るやつがいます。
$7$で割った余りを考えてみましょう。
以下法を$7$とする。
$x\equiv0\pm1.\pm2,\pm3$
$x^3\equiv0\pm1.\pm8,\pm27$
∴$x^3\equiv0\pm1$
$Tip$
この立法剰余の背景には後のフェルマーの小定理が絡んでいる。
第4章：合同式の古典的大定理たち
4.1 フェルマーの小定理（魔術的な証明）
数論において最も有名かつ重要な大定理です。
$p$ を素数とし、$a$ を $p$ と互いに素な整数（$p \nmid a$）とするとき、
$$a^{p-1} \equiv 1 \pmod p$$
これのより一般系ともいえる方をおさえてほしい
互いに素とかいう条件なしに
↓
$p$が素数のとき、
$$a^{p} \equiv a \pmod p$$
が成り立つ。
上の式はあくまで両辺を$a$で割ったものである。
割り算だから互いに素とか条件が付いたのです。
証明はちょっと難しい
そのため一旦は結論だけ流してもいいかもしれない。
$1, 2, 3, \dots, (p-1)$ という $(p-1)$ 個の整数に、すべて $a$ を掛けた集合 $\{a, 2a, 3a, \dots, (p-1)a\}$ を考える。
この集合の要素を $p$ で割った余りはすべて異なる。
証明
背理法で証明。
全ては異ならない即ち同じものが存在すると仮定する。
つまり、
$ia \equiv ja \pmod p \quad (1 \le i < j \le p-1)$
を満たすような整数$i,j$が存在すると仮定。
$\gcd(a, p)=1$ より両辺を $a$ で割ることができ、$i \equiv j \pmod p$ となって範囲の仮定に矛盾する。
故に仮定に矛盾し補題は示される。
補題から、$1, 2, 3, \dots, (p-1)$ という $(p-1)$ 個の整数に、
すべて $a$ を掛けた集合 $\{a, 2a, 3a, \dots, (p-1)a\}$ を
$p$ で割った余りはすべて異なります。
したがって、これら $(p-1)$ 個の数を $p$ で割った余りは、
順序を並び替えるとすべて $1, 2, 3, \dots, (p-1)$ に一対一で完全に対応します。
よって、すべての要素の積を考えると、
$$a \cdot 2a \cdot 3a \dots (p-1)a \equiv 1 \cdot 2 \cdot 3 \dots (p-1) \pmod p$$
$$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$$
ここで、$p$ は素数であるため、$(p-1)!$ は $p$ と互いに素です。したがって、両辺を $(p-1)!$ で割ることができ、
$$a^{p-1} \equiv 1 \pmod p$$
が示される。
この「既約剰余類の並び替え（全単射）」の視点は、のちの位数や原始根の議論へダイレクトに繋がっていきます。
ちょっとだるくなってきたので今回は証明を省かせてください。
ここからは特に応用といえます。
(ごめん...いつか書くかも)
結論だけは紹介します。
4.2 オイラーの定理への一般化
フェルマーの小定理は、法が「素数 $p$」のときにしか使えませんでした。これを一般の整数 $m$ に拡張したのが、数論の王者とも言えるオイラーの定理です。
$1$ から $m$ までの整数のうち、$m$ と互いに素なものの個数を
$\phi(m)$ （オイラーの $\phi$ 関数）と定義します。
(トーシェント関数とも呼ばれるはず)
このとき、以下が成り立ちます。
$$\gcd(a, m) = 1 \implies a^{\phi(m)} \equiv 1 \pmod m$$
法が素数 $p$ のとき、$1$ から $p-1$ までのすべての数（計 $p-1$ 個）が $p$ と互いに素なので $\phi(p) = p-1$ となり、フェルマーの小定理と完全に一致しますね。
4.3 ウィルソンの定理
素数に関するもう一つの美しい境界条件を示す定理です。
整数 $p > 1$ について、$p$ が素数であることと、以下の合同式が成り立つことは同値です。
$$(p-1)! \equiv -1 \pmod p$$
これは、$\pmod p$ の世界において、$1$ から $p-1$ までの各数が、自分自身と掛け合わせて $1$ になるような「逆元」のペアに綺麗に分かれ、自分自身が逆元になる $1$ と $p-1$（$\equiv -1$）だけがペアを組めずに生き残る性質から魔術的に証明されます。
4.4 中国剰余定理（CRT）の主張
互いに素な整数 $m, n$ について、連立合同方程式
$$\begin{cases} x \equiv a \pmod m \\ x \equiv b \pmod n \end{cases}$$
は、$mn$ を法として一意に解をひとつ持ちます。
古代中国の「孫子算経」に由来する定理であり、大きな法を小さな法へと分解して考えるための代数的な重要基盤（環の直積分解）となっています。
第5章：上級の扉 —— 位数と原始根（数論の深淵へ）
ここからは、合同式の概念をさらに抽象化し、整数論における最重要トピックである「周期性」と「生成元」の議論、すなわち位数（order）と原始根（primitive root）の世界へ足を踏み入れます。
多くの参考書では天下り的に定義され、ざっくりとした説明で終わってしまいがちなこの章ですが、ここでは言葉の定義から基本性質の厳密な証明、数論最高峰の「原始根定理」へと繋がる論理の糸を、一切の妥協なく解き明かします。
結構ハードな内容なので読み飛ばしても$OK$です！！！
性質だけでもおさえられたらばっちり！！
5.1 「位数（order）」の厳密な定義
まずはすべての議論の土台となる「位数」の定義を明確にします。
法 $m$ を正の整数とし、$a$ を $m$ と互いに素な整数（$\gcd(a, m) = 1$）とします。このとき、オイラーの定理より $a^{\phi(m)} \equiv 1 \pmod m$ となる正の整数が存在することは保証されていますが、必ずしも $\phi(m)$ 乗まで待たずとも、より小さな累乗の段階で初めて余りが $1$ になることがあります。
$$a^d \equiv 1 \pmod m$$
を満たす最小の正の整数 $d$ を、法 $m$ における $a$ の位数（order）と呼び、$\text{ord}_m(a)$ または単に $d$ と表す。
注意（大前提の確認）：
$a$ と $m$ が互いに素でなければ、いくら累乗しても余りが $1$ になることは絶対にありません。なぜなら、$\gcd(a, m) = g > 1$ と仮定すると、ある整数 $k$ を用いて $a^d - 1 = km \implies a^d - km = 1$ となり、左辺は $g$ の倍数ですが右辺は $1$ となって矛盾するためです。したがって、位数を語る上では「互いに素」という前提が不可欠です。
5.2 位数の基本性質とその証明
位数は単なる「最初に1になる指数」というだけでなく、余りの周期を完全に支配する代数的性質を持っています。以下の定理は、整数論の証明問題で極めて頻出する最重要の基盤です。
$\pmod m$ における $a$ の位数を $d$ とするとき、任意の自然数 $n$ について以下が成り立つ。
$$a^n \equiv 1 \pmod m \iff d \mid n \quad \text{($n$は$d$の倍数)}$$
割り算の原理を用いて、位数の「最小性」で挟み撃ちにする証明です。
- （$\impliedby$ の証明）
$d \mid n$ であるとき、ある整数 $k$ を用いて $n = dk$ と表せます。このとき、位数の定義（$a^d \equiv 1$）より、
$$a^n = a^{dk} = (a^d)^k \equiv 1^k \equiv 1 \pmod m$$
となり、こちらは自明に成り立ちます。 - （$\implies$ の証明）
$a^n \equiv 1 \pmod m$ が成り立っていると仮定します。ここで、$n$ を位数 $d$ で割ったときの商を $q$、余りを $r$ とおくと、割り算の原理より、
$$n = qd + r \quad (0 \le r < d)$$
とただ一通りに表すことができます。これを指数の法則に従って変形すると、
$$a^n = a^{qd + r} = (a^d)^q \cdot a^r$$
となります。いま、仮定より $a^n \equiv 1$ であり、位数の定義より $a^d \equiv 1$ ですから、これを合同式に代入すると、
$$1 \equiv (1)^q \cdot a^r \implies a^r \equiv 1 \pmod m$$
が得られます。
ここで、余り $r$ の範囲に着目します。$0 \le r < d$ ですが、もし $r > 0$（すなわち $d$ が $n$ を割り切らない）と仮定すると、「$a^d \equiv 1$ を満たす最小の正の整数が $d$ である」という位数の定義に完全に矛盾してしまいます（$d$ より小さな正の整数 $r$ で $1$ になってしまったため）。
したがって、$r = 0$ であるほかなく、$n = qd$ となるため、$d \mid n$ が示されました。$\blacksquare$
【系：オイラーの定理との接続】
オイラーの定理より、$\gcd(a, m) = 1$ ならば必ず $a^{\phi(m)} \equiv 1 \pmod m$ です。上記の定理に $n = \phi(m)$ を代入すると、直ちに次の強力な事実が導かれます。
$$\text{ord}_m(a) \mid \phi(m)$$
つまり、「任意の元の位数は、必ず $\phi(m)$ の約数になる」ということです。これにより、具体的な位数の候補を圧倒的に絞り込むことが可能になります。
5.3 原始根の定義と「一巡する」性質
位数が「取り得る最大値である $\phi(m)$」にぴったり一致するとき、その数を特別な名前で呼びます。ここからは話を最も美しく展開するため、法を素数 $p$（したがって $\phi(p) = p-1$）に限定して議論を進めます。
$3$ 以上の素数 $p$ と、$1$ 以上 $p$ 未満の整数 $r$ について、$r$ の位数が限界値である $p-1$ に一致するとき、すなわち、
$$r^1, r^2, \dots, r^{p-2} \text{ のいずれもが } p \text{ で割って余り } 1 \text{ でない}$$
かつ
$$r^{p-1} \equiv 1 \pmod p$$
を満たすとき、$r$ を法 $p$ に対する原始根（primitive root）と呼びます。（※なお、$r=1$ は $p=2$ に対する原始根と定めます）
原始根がなぜ強力な道具とされるのか。それは、以下の「剰余類を一巡してすべて支配する」という極めて嬉しい性質を持つからです。
$r$ が法 $p$ に対する原始根のとき、$r^1, r^2, \dots, r^{p-1}$ を $p$ で割った余りはすべて異なり、その余りは $1$ から $p-1$ までのすべての整数を過不足なく一巡する。
背理法を用いて示します。
$r^1, r^2, \dots, r^{p-1}$ の中に、$p$ で割った余りが等しいペアが存在すると仮定します。つまり、
$$r^m \equiv r^n \pmod p \quad (1 \le n < m \le p-1)$$
となる自然数 $m, n$ が存在すると仮定する。
左辺に移行すると $r^m - r^n \equiv 0 \iff r^n(r^{m-n} - 1) \equiv 0 \pmod p$ となる。
いま、$r$ は法 $p$ と互いに素（$p \nmid r$）であるため、両辺を共通因数である $r^n$ で割ることができる。
両辺を $r^n$ で割ると、
$$r^{m-n} \equiv 1 \pmod p$$
となります。ここで、この新たな指数の範囲を確認すると、$1 \le n < m \le p-1$ より、その差の範囲は、
$$1 \le m-n \le p-2$$
となります。ところがどっこい、これは $r$ が原始根であるという定義（$p-1$ より小さな正の指数では絶対に $1$ にならない）に矛盾する。
したがって、仮定は誤りであり、$r^1, r^2, \dots, r^{p-1}$ の余りはすべて異なります。
$1$ から $p-1$ までの余りの種類はちょうど $p-1$ 個であり、これら $r$ の累乗の個数も $p-1$ 個で、かつすべて異なるため、鳩の巣原理より、これらは $1$ から $p-1$ までのすべての余りを漏れなく重複なく並び替えたものに完全に一致する。$\blacksquare$
具体例による観察（$p=7$ の場合）
素数 $p=7$ （$\phi(7)=6$）における $2$ と $3$ の累乗の周期の挙動を比較してみましょう。
| $x$ | $x^1 \pmod 7$ | $x^2 \pmod 7$ | $x^3 \pmod 7$ | $x^4 \pmod 7$ | $x^5 \pmod 7$ | $x^6 \pmod 7$ | 位数 $\text{ord}_7(x)$ |
|---|---|---|---|---|---|---|---|
| 2 | 2 | 4 | 1 | 2 | 4 | 1 | 3 |
| 3 | 3 | 2 | 6 | 4 | 5 | 1 | 6（原始根） |
表から一目瞭然な通り、$2$ の位数は $3$ であり、最大値に到達する前に周期が巡ってしまいます。一方、$3$ の位数はちょうど最大値の $6$ であり、$3^1$ から $3^6$ までの余りを書き出すと $\{3, 2, 6, 4, 5, 1\}$ となり、$7$ と互いに素な余り（$1$ から $6$ まで）を完璧にすべて生成しています。これが原始根の持つ圧倒的な構造的美しさですね。
5.4 【伏線回収】ラグランジュの定理が紡ぐ「原始根存在証明」の全貌
記事の冒頭で触れた「ラグランジュの定理」。これがなぜ原始根の議論において「最高峰の伏線」となるのか、その論理的な繋がりと存在証明の全貌をここに明かします。
まず、決定的な役割を果たす超重要定理を、その証明とともにここに刻みます。
$p$ を素数とする。$\pmod p$ において、$n$ 次合同方程式
$$f(x) = c_n x^n + c_{n-1} x^{n-1} + \dots + c_0 \equiv 0 \pmod p \quad (c_n \not\equiv 0)$$
の解は、高々 $n$ 個しか存在しない。
多項式 $f(x)$ の次数 $n$ に関する数学的帰納法で示します。
1. $n=1$ のとき
1次合同方程式 $c_1 x + c_0 \equiv 0 \pmod p \quad (c_1 \not\equiv 0)$ を考える。
$p$ は素数であり、$c_1 \not\equiv 0 \pmod p$ より、$\gcd(c_1, p) = 1$ である。
したがって、両辺に $c_1$ の $\pmod p$ における逆元 $c_1^{-1}$ を掛けることで、解は $x \equiv -c_0 c_1^{-1} \pmod p$ のただ1つ（高々1個）に定まり、成立する。
2. $n=k$ のとき成り立つと仮定し、$n=k+1$ のときを考える
$(k+1)$ 次合同方程式 $f(x) \equiv 0 \pmod p$ が、もし $\pmod p$ で1つも解を持たないならば、「高々 $k+1$ 個」という主張は当然成り立つ。
解を少なくとも1つ持つと仮定し、その解の1つを $x \equiv \alpha \pmod p$ とする。
このとき、多項式 $f(x)$ を $x - \alpha$ で割った商を $q(x)$ とおくと、因数定理（整式の割り算）より、
$$f(x) = (x - \alpha)q(x)$$
と表すことができる。ここで $q(x)$ は $c_{k+1}$ を最高次の係数に持つ $k$ 次多項式である。
いま、$\alpha$ 以外の任意の解 $x \equiv \beta \pmod p \quad (\beta \not\equiv \alpha)$ を方程式に代入すると、
$$f(\beta) = (\beta - \alpha)q(\beta) \equiv 0 \pmod p$$
となる。ここで法 $p$ が素数であることが決定的な意味を持つ。
$\beta \not\equiv \alpha \pmod p$ より $\beta - \alpha \not\equiv 0 \pmod p$ であるため、積が $p$ の倍数になるためには、もう一方の $q(\beta) \equiv 0 \pmod p$ が成り立たなければならない。
つまり、$\alpha$ 以外の $f(x) \equiv 0$ の解は、すべて $k$ 次合同方程式 $q(x) \equiv 0 \pmod p$ の解になっている必要がある。
帰帰法の仮定より、$k$ 次方程式 $q(x) \equiv 0$ の解は高々 $k$ 個しか存在しない。
したがって、元の $(k+1)$ 次方程式 $f(x) \equiv 0$ の解は、最初に固定した $\alpha$ の1個と、$q(x) \equiv 0$ の解（高々 $k$ 個）を合わせても、全体で高々 $1 + k = k+1$ 個しか存在しない。
以上より、数学的帰納法により任意の自然数 $n$ について定理は示された。$\blacksquare$
1. なぜ法が「素数」のときだけ解が制限されるのか？
一般の合成数（例えば法 $8$）では、$x^2 \equiv 1 \pmod 8$ という2次方程式の解が $x \equiv 1, 3, 5, 7$ の4個も存在し、次数をオーバーして大爆発してしまいます。
なぜこんなバグが起きるのか。それは合成数の世界に「$2 \times 4 = 8 \equiv 0$」のような零因子が存在し、因数分解しても「どちらかが $0$」と断定できないからです。先ほどの証明の終盤で「$\beta - \alpha \not\equiv 0$ だから相方の $q(\beta) \equiv 0$ だ！」と強引に押し切れたのは、法 $p$ が素数という平和な世界（整域）だったからに他なりません。
私たちがよく知る複素数などの世界と同じように「積が $0$ ならば、少なくとも一方は $0$」という代数学の基本論理が完全に通用する。だからこそ、解の個数が次数以下にビシッと抑えられるのです。
2. 原始根の存在証明（原始根定理）の厳密な証明
いよいよ、本理論編の最高到達点である「原始根定理」の厳密な証明に挑みます。
「$1$ から $p-1$ までの各数を、その位数ごとにグループ分けして数え上げる」という緻密な戦略をとるため、まずはその数え上げの絶対的なレールとなるオイラー関数の強力な性質（補題）を一歩目に置きましょう。
任意の自然数 $n$ について、 $n$ のすべての約数 $d$ に対する $\phi(d)$ の和は、元の数 $n$ にぴったり一致する。
$$\sum_{d \mid n} \phi(d) = n$$
（例えば $n=6$ のとき、約数は $1, 2, 3, 6$ なので、 $\phi(1)+\phi(2)+\phi(3)+\phi(6) = 1 + 1 + 2 + 2 = 6$ となり、確かに成立します。）
この武器を持った状態で、 $p-1$ の任意の約数 $d$ に対して「位数 $d$ を持つ数がこの世界に何個存在するか？」を、ラグランジュの定理を用いて完全に封じ込めます。
$p$ を素数とする。 $p-1$ の任意の約数 $d$ について、法 $p$ において位数 $d$ を持つ元の個数を $N(d)$ と表すとき、以下が成り立つ。
$$N(d) = 0 \quad \text{または} \quad N(d) = \phi(d)$$
位数 $d$ を持つ元が1つも存在しない場合、当然 $N(d) = 0$ となり定理の主張を満たします。
したがって、「位数 $d$ を持つ元 $a$ が少なくとも1つ存在する（$N(d) > 0$）」と仮定したときに、必ず $N(d) = \phi(d)$ になることを示せば証明が完了します。
いま、位数 $d$ を持つ元 $a$ が存在すると仮定します。位数の定義より $a^d \equiv 1 \pmod p$ です。このとき、 $a$ の累乗を用いて以下の $d$ 個 of 元の集合を考えます。
$$A = \{a^1, a^2, a^3, \dots, a^d\}$$
5.3で示した通り、位数の最小性からこれら $d$ 個の元は $\pmod p$ ですべて互いに異なります。
空間の任意の $k \quad (1 \le k \le d)$ について、
$$(a^k)^d = (a^d)^k \equiv 1^k \equiv 1 \pmod p$$
が成り立つため、集合 $A$ の要素はすべて $d$ 次合同方程式 $x^d - 1 \equiv 0 \pmod p$ の解になっています。
ここでラグランジュの定理が絶対的な威力を発揮します。
法が素数 $p$ であるため、 $d$ 次合同方程式 $x^d - 1 \equiv 0 \pmod p$ の解は高々 $d$ 個しか存在しません。
ところが、いま集合 $A$ の中にすでに「互いに異なる $d$ 個の解」が見つかっています。
したがって、この方程式の解の集合は、集合 $A$ そのものと完全に一致する（これ以外の解は存在し得ない）ことが確定します。
この事実から、「世界に存在する『位数 $d$ を持つ元』は、すべてこの集合 $A = \{a^1, a^2, \dots, a^d\}$ の中にいる」ということになります。
では、集合 $A$ の要素 $a^k$ のうち、本当に位数自体がちょうど $d$ になるものは何個あるでしょうか？
位数の性質から、 $a^k$ の位数は $\frac{d}{\gcd(k, d)}$ と計算できます。
これがぴったり $d$ に一致するためには、分母の $\gcd(k, d) = 1$、すなわち $k$ と $d$ が互いに素であることが絶対条件です。
$1 \le k \le d$ の範囲で、 $d$ と互いに素な整数 $k$ の個数は、オイラーの $\phi$ 関数の定義そのものからぴったり $\phi(d)$ 個です。
以上より、位数 $d$ の元が1つでも存在すれば、ラグランジュの定理による解の制限によって余計な解がすべて排除され、個数は完全にコントロールされて $N(d) = \phi(d)$ となることが示されました。 $\blacksquare$
ここまでのパーツが揃えば、最後のパズルが驚くほど鮮やかに組み上がります。これこそが数論最高峰の美しさです。
任意の素数 $p$ に対して、法 $p$ における原始根は必ず存在し、その個数はぴったり $\phi(p-1)$ 個である。
5.2の系より、 $1$ から $p-1$ までのすべての元の位数は、必ず $p-1$ の約数のいずれかになります。
したがって、 $p-1$ のすべての約数 $d$ について、位数 $d$ を持つ元の個数 $N(d)$ を足し合わせると、全体の元の個数である $p-1$ 個に完全に一致します。
$$\sum_{d \mid (p-1)} N(d) = p-1$$
一方で、先ほど導入した【補題】の数式 $\sum_{d \mid n} \phi(d) = n$ に $n = p-1$ を代入すると、以下の等式が得られます。
$$\sum_{d \mid (p-1)} \phi(d) = p-1$$
この2つの式を並べて比較してみましょう。
$$\sum_{d \mid (p-1)} N(d) = \sum_{d \mid (p-1)} \phi(d) = p-1$$
先ほど示した【位数の個数定理】より、すべての約数 $d$ について $N(d) \le \phi(d)$ （ $0$ か $\phi(d)$ なので）が成り立っています。
各項がすべて「相手以下」のサイズしか持たないにもかかわらず、全部足し算したトータルの合計値（$p-1$）が完全に一致しているということは、途中のどこかの項で一箇所でもサボる（ $N(d) = 0$ になる）ことなど絶対に許されません。
もし仮に、どこか1つの約数でも $N(d) = 0 < \phi(d)$ となってしまえば、全体の合計が $p-1$ に届かなくなってしまい、矛盾が生じるからです。
したがって、すべての $p-1$ の約数 $d$ について $N(d) = 0$ になるケースは完全に否定され、
$$N(d) = \phi(d)$$
であることが確定します。
原始根とは、「位数がちょうど $p-1$ である元」のことでした。
したがって、約数 $d = p-1$ の場合をピンポイントで引き抜くと、位数 $p-1$ を持つ元の個数は、
$$N(p-1) = \phi(p-1)$$
となります。オイラー関数の性質から $\phi(p-1) \ge 1$ であるため、法 $p$ における原始根は「絶対に存在し、その個数はぴったり $\phi(p-1)$ 個である」という事実が完全に証明されました。 $\blacksquare$
結び（次回予告）
今回は合同式の基礎から、数論の深淵とも言える位数・原始根の定義まで、知識と理論を繋ぎました。
ここまでの知識を完全に咀嚼できれば、整数論のあらゆる大武器を手に入れたといえるでしょう。
今回は「知っとくべき理論」を網羅しました。
次回【活用編】では、これらの強力な定理群を使って、
実際の入試問題やオリンピック問題、巨大な剰余方程式をどのように一瞬でなぎ倒していくのか、
その圧倒的な実践アプローチを解説する。かも
お楽しみに！
みなさまの日常に良き数学の彩りのあらんことを。
それでは、ごきげんよう。
この記事を高評価した人
この記事に送られたバッジ
投稿者
