mod(合同式)を学んでみよう！(知識編)

$a,b$を$m$で割った商と余りをそれぞれ$q_1,r_1$および$q_2,r_2$とすると、
$$ a=q_1m+r_1,\qquad b=q_2m+r_2 $$
と表せます。ただし、$0\leqq r_1,r_2< m$です。
余りが等しく$r_1=r_2$ならば、
$$ a-b=(q_1-q_2)m $$
となるので、$a-b$は$m$の倍数です。
逆に、$a-b$が$m$の倍数ならば、
$$ a-b=(q_1-q_2)m+(r_1-r_2) $$
より、$r_1-r_2$も$m$の倍数です。
一方、
$$ -(m-1)\leqq r_1-r_2\leqq m-1 $$
なので、この範囲にある$m$の倍数は$0$だけです。したがって$r_1=r_2$となります。

定義より、ある整数$k,l$を用いて
$$ a-b=km,\qquad c-d=lm $$
と表せます。
したがって、
$$ (a+c)-(b+d)=(a-b)+(c-d)=(k+l)m $$
$$ (a-c)-(b-d)=(a-b)-(c-d)=(k-l)m $$
となるので、和と差の性質が示されます。
また、
$$ ac-bd=c(a-b)+b(c-d)=(ck+bl)m $$
となるので、積の性質も示されます。

$n=0$ならば結論は明らかです。
$n\ne0$とします。符号は約数・倍数の関係に影響しないので、必要なら絶対値をとり、正の整数の素因数分解を考えます。
$m$を素因数分解して
$$ m=p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s} $$
とします。
$c,m$は互いに素なので、$p_1,p_2,\ldots,p_s$のいずれも$|c|$の素因数ではありません。
一方、$m\mid cn$より、$|cn|$の素因数分解には$p_i^{e_i}$がすべて含まれます。これらは$|c|$には含まれないので、すべて$|n|$に含まれなければなりません。
したがって$m\mid n$です。

$$ ac\equiv bc\pmod m $$
ならば、$c(a-b)$は$m$の倍数です。
$c,m$は互いに素なので、ユークリッドの補題より$a-b$は$m$の倍数です。したがって、
$$ a\equiv b\pmod m $$
となります。

まず、$cu\equiv1\pmod m$を満たす整数$u$が存在するとします。
ある整数$k$を用いて
$$ cu-km=1 $$
と表せます。$c,m$の共通の正の約数は$cu$と$km$の両方を割るので、その差である$1$も割ります。したがって共通の正の約数は$1$だけであり、$c,m$は互いに素です。
逆に、$c,m$が互いに素であるとします。
$$ c,2c,3c,\ldots,(m-1)c $$
を$m$で割った余りを考えます。
もし$1\leqq i< j\leqq m-1$について
$$ ic\equiv jc\pmod m $$
ならば、$c,m$が互いに素なので約分でき、$i\equiv j\pmod m$となります。しかし$0< j-i< m$なので、これは不可能です。
また、$ic\equiv0\pmod m$ならば、同様に約分して$i\equiv0\pmod m$となり、$1\leqq i\leqq m-1$に反します。
したがって、上の$m-1$個の数の余りは、$1,2,\ldots,m-1$を重複なく並べ替えたものです。よって、その中には余りが$1$となるものが必ず存在します。すなわち$c$は逆元を持ちます。
さらに、
$$ cu\equiv cv\equiv1\pmod m $$
ならば、$c,m$が互いに素なので$cu\equiv cv$の両辺を$c$で約分でき、
$$ u\equiv v\pmod m $$
となります。したがって逆元は法$m$においてただ一つです。

$$ c=dc_1,\qquad m=dm_1 $$
とおきます。
$c_1,m_1$が互いに素であることを確認します。
もし正の整数$e$が$c_1,m_1$の共通の約数ならば、$de$は$c,m$の共通の約数です。ところが$d$は$c,m$の最大公約数なので、$de\leqq d$です。したがって$e=1$となり、$c_1,m_1$は互いに素です。
さて、
$$ \begin{aligned} ac\equiv bc\pmod m &\iff m\mid c(a-b)\\ &\iff dm_1\mid dc_1(a-b)\\ &\iff m_1\mid c_1(a-b)\\ &\iff m_1\mid(a-b)\\ &\iff a\equiv b\pmod{m_1} \end{aligned} $$
です。
最後から二つ目の同値では、$c_1,m_1$が互いに素であることを用いました。$m_1=1$の場合は両側がともに常に成り立ち、$m_1\geqq2$の場合はユークリッドの補題を使えます。
$m_1=m/d$なので、題意が示されました。

$a\equiv b\pmod m$ならば、各正の整数$k$について$a^k\equiv b^k\pmod m$です。
その両辺に整数$c_k$を掛け、すべて足し合わせれば、
$$ c_na^n+c_{n-1}a^{n-1}+\cdots+c_1a+c_0 \equiv c_nb^n+c_{n-1}b^{n-1}+\cdots+c_1b+c_0 \pmod m $$
となります。これは$f(a)\equiv f(b)\pmod m$を意味します。

まず、$a$が$p$と互いに素である場合を考えます。
$$ a,2a,3a,\ldots,(p-1)a $$
を$p$で割った余りは、すべて異なります。
実際、$1\leqq i< j\leqq p-1$について
$$ ia\equiv ja\pmod p $$
と仮定すると、$a,p$は互いに素なので両辺を$a$で約分でき、
$$ i\equiv j\pmod p $$
となります。しかし、$0< j-i< p$なので矛盾です。
また、$ia\equiv0\pmod p$とすると、同様に$i\equiv0\pmod p$となり、$1\leqq i\leqq p-1$に反します。
したがって、これら$p-1$個の数を$p$で割った余りは、$1,2,\ldots,p-1$を重複なく並べ替えたものです。
よって積をとると、
$$ (a)(2a)(3a)\cdots((p-1)a) \equiv 1\cdot2\cdot3\cdots(p-1) \pmod p $$
となります。すなわち、
$$ a^{p-1}(p-1)!\equiv(p-1)!\pmod p $$
です。
$(p-1)!$は$p$と互いに素なので約分でき、
$$ a^{p-1}\equiv1\pmod p $$
が得られます。
次に、任意の整数$a$について$a^p\equiv a\pmod p$を示します。
$a$が$p$の倍数ならば、両辺はともに$0$と合同です。
$a$が$p$の倍数でなければ、$p$は素数なので$a,p$は互いに素です。先ほど示した式の両辺に$a$を掛けて、
$$ a^p\equiv a\pmod p $$
となります。

$1$以上$m$以下の整数のうち、$m$と互いに素なものを
$$ r_1,r_2,\ldots,r_{\phi(m)} $$
とします。
$a$も$m$と互いに素なので、$ar_i$も$m$と互いに素です。実際、$m$の素因数が$ar_i$を割るならば、その素因数は$a$または$r_i$を割ることになり、いずれの場合も互いに素であることに反します。
また、
$$ ar_i\equiv ar_j\pmod m $$
ならば、$a,m$が互いに素なので約分でき、$r_i\equiv r_j\pmod m$となります。したがって、$ar_1,ar_2,\ldots,ar_{\phi(m)}$の余りはすべて異なります。
よって、これらの余りは$r_1,r_2,\ldots,r_{\phi(m)}$を並べ替えたものです。積をとると、
$$ a^{\phi(m)}r_1r_2\cdots r_{\phi(m)} \equiv r_1r_2\cdots r_{\phi(m)} \pmod m $$
となります。
$r_1r_2\cdots r_{\phi(m)}$は$m$と互いに素なので約分でき、
$$ a^{\phi(m)}\equiv1\pmod m $$
が得られます。

まず、$n=p$が素数であるとします。
$1,2,\ldots,p-1$の各整数は$p$と互いに素なので、法$p$において逆元を持ちます。
ある整数$x$が自分自身の逆元であるための条件は、
$$ x^2\equiv1\pmod p $$
です。このとき、
$$ (x-1)(x+1)\equiv0\pmod p $$
となります。$p$は素数なので、
$$ x\equiv1\pmod p \quad\text{または}\quad x\equiv-1\pmod p $$
です。
$p$が奇素数ならば、$1$と$p-1$以外の整数は、互いに異なる逆元同士の組に分けられます。各組の積は$1$と合同なので、
$$ (p-1)!\equiv1\cdot(p-1)\equiv-1\pmod p $$
となります。
$p=2$のときも、
$$ 1!\equiv1\equiv-1\pmod2 $$
なので成立します。
逆に、$n>1$が合成数であるとします。
$n=4$ならば、
$$ 3!=6\equiv2\not\equiv-1\pmod4 $$
です。
$n>4$ならば、$n=ab$を満たす整数$1< a\leqq b< n$が存在します。
$a< b$ならば、$(n-1)!$の中に$a,b$がともに含まれるので、$n=ab$は$(n-1)!$の約数です。
$a=b$ならば$n=a^2$であり、$n>4$より$a\geqq3$です。このとき
$$ 2a\leqq a^2-1=n-1 $$
なので、$a,2a$はともに$1$以上$n-1$以下であり、
$$ a\cdot2a=2n $$
なので、やはり$n$は$(n-1)!$の約数です。
したがって、合成数$n>4$については
$$ (n-1)!\equiv0\not\equiv-1\pmod n $$
です。
以上より、同値が示されました。

$m,n$は互いに素なので、$m$は法$n$において逆元を持ちます。その逆元を$u$とすると、
$$ mu\equiv1\pmod n $$
です。
ここで、
$$ x=a+mu(b-a) $$
とおきます。
法$m$では$mu(b-a)\equiv0$なので、
$$ x\equiv a\pmod m $$
です。
また、法$n$では$mu\equiv1$なので、
$$ x\equiv a+(b-a)=b\pmod n $$
です。したがって解は少なくとも一つ存在します。
次に、$x,y$がともにこの連立合同式の解であるとします。
すると$x-y$は$m$の倍数かつ$n$の倍数です。ある整数$k$を用いて$x-y=mk$とおくと、$n\mid mk$です。
$m,n$は互いに素なので、ユークリッドの補題より$n\mid k$です。したがって、$x-y$は$mn$の倍数となり、
$$ x\equiv y\pmod{mn} $$
です。
よって解は$mn$を法としてただ一つです。

まず$d\mid n$ならば、ある正の整数$k$を用いて$n=dk$と表せます。したがって、
$$ a^n=(a^d)^k\equiv1^k\equiv1\pmod m $$
です。
逆に、$a^n\equiv1\pmod m$とします。
$n$を$d$で割った商を$q$、余りを$r$とすると、
$$ n=qd+r\qquad(0\leqq r< d) $$
と表せます。
よって、
$$ a^n=(a^d)^qa^r\equiv a^r\pmod m $$
です。$a^n\equiv1$なので、$a^r\equiv1\pmod m$となります。
もし$r>0$ならば、$d$より小さい正の整数$r$について$a^r\equiv1$となり、$d$の最小性に反します。したがって$r=0$です。
よって$d\mid n$となります。

$1\leqq i< j\leqq d$について$a^i\equiv a^j\pmod m$と仮定します。
$a,m$は互いに素なので$a^i$も$m$と互いに素です。したがって両辺を$a^i$で約分でき、
$$ a^{j-i}\equiv1\pmod m $$
となります。
しかし、$1\leqq j-i< d$なので、これは位数$d$の最小性に反します。

$a^k$も$m$と互いに素なので、その位数は定義できます。
$h=\gcd(k,d)$とし、
$$ k=hu,\qquad d=hv $$
とおきます。このとき$u,v$は互いに素です。
まず、
$$ (a^k)^v=a^{huv}=a^{ud}=(a^d)^u\equiv1\pmod m $$
です。
一方、正の整数$t$について$(a^k)^t\equiv1\pmod m$とすると、$a^{kt}\equiv1\pmod m$です。
先ほどの定理より$d\mid kt$なので、
$$ hv\mid hut $$
すなわち$v\mid ut$です。
$u,v$は互いに素なので、ユークリッドの補題より$v\mid t$となります。
したがって、$(a^k)^t\equiv1$となる正の整数$t$の最小値は$v$です。よって、
$$ \operatorname{ord}_m(a^k)=v =\frac{d}{\gcd(k,d)} $$
となります。

$r$の位数は$p-1$なので、5.2節の補題より
$$ r,r^2,\ldots,r^{p-1} $$
は法$p$においてすべて異なります。
また、$r$は$p$と互いに素なので、どの累乗も$p$の倍数ではありません。
したがって、これら$p-1$個の余りは、$p$の倍数でない$p-1$種類の余り
$$ 1,2,\ldots,p-1 $$
を重複なく並べ替えたものです。

次数$n$に関する数学的帰納法で示します。
まず$n=1$とします。
$$ c_1x+c_0\equiv0\pmod p $$
において、$c_1\not\equiv0\pmod p$です。$p$は素数なので$c_1,p$は互いに素であり、$c_1$は逆元を持ちます。
したがって、
$$ x\equiv-c_0c_1^{-1}\pmod p $$
となり、解は高々一個です。
次に、$k$次多項式について定理が成り立つと仮定し、$(k+1)$次多項式$f(x)$を考えます。
$f(x)\equiv0\pmod p$が解を一つも持たない場合、主張は明らかです。
そこで、解を少なくとも一つ持つとし、その一つの代表元を$\alpha$として、$x\equiv\alpha\pmod p$とします。
多項式$f(x)-f(\alpha)$は$x=\alpha$を整数としての解に持つので、因数定理より、整数係数$k$次多項式$q(x)$を用いて
$$ f(x)-f(\alpha)=(x-\alpha)q(x) $$
と表せます。
$q(x)$の最高次の係数は$f(x)$の最高次の係数と同じなので、$p$の倍数ではありません。したがって、$q(x)$には帰納法の仮定を適用できます。
$f(\alpha)\equiv0\pmod p$なので、
$$ f(x)\equiv(x-\alpha)q(x)\pmod p $$
です。
ここで、$\beta\not\equiv\alpha\pmod p$を$f(x)\equiv0\pmod p$の別の解とすると、
$$ 0\equiv f(\beta) \equiv(\beta-\alpha)q(\beta) \pmod p $$
となります。
$\beta-\alpha\not\equiv0\pmod p$であり、$p$は素数なので、両辺を$\beta-\alpha$で約分できます。よって、
$$ q(\beta)\equiv0\pmod p $$
です。
したがって、$\alpha$以外の$f(x)\equiv0$の解は、すべて$k$次合同方程式$q(x)\equiv0$の解です。
帰納法の仮定より、$q(x)\equiv0$の解は高々$k$個なので、$f(x)\equiv0$の解は$\alpha$を合わせても高々$k+1$個です。
以上より、任意の正の整数$n$について定理が成り立ちます。

$1,2,\ldots,n$を、$n$との最大公約数によって分類します。
$e$を$n$の正の約数とし、
$$ \gcd(k,n)=e $$
を満たす$1\leqq k\leqq n$の個数を考えます。
$k=et$、$n=ed$とおくと、
$$ \gcd(k,n)=e \iff \gcd(t,d)=1 $$
です。
また、$1\leqq k\leqq n$は$1\leqq t\leqq d$と同値です。したがって、このような$k$の個数は$\phi(d)$個です。
$e$が$n$のすべての約数を動くとき、$d=n/e$も$n$のすべての約数を動きます。
よって、$1,2,\ldots,n$の$n$個の整数をすべて数えると、
$$ \sum_{d\mid n}\phi(d)=n $$
となります。

位数$d$の整数が存在しなければ$N(d)=0$なので、主張は成り立ちます。
そこで、位数$d$の整数$a$が少なくとも一つ存在するとします。
5.2節の補題より、
$$ a,a^2,\ldots,a^d $$
は法$p$においてすべて異なります。
また、$1\leqq k\leqq d$について、
$$ (a^k)^d=(a^d)^k\equiv1\pmod p $$
なので、これら$d$個の整数はすべて合同方程式
$$ x^d-1\equiv0\pmod p $$
の解です。
ラグランジュの定理より、この$d$次合同方程式の解は高々$d$個です。すでに異なる$d$個の解が見つかっているので、解はちょうど
$$ a,a^2,\ldots,a^d $$
だけです。
位数が$d$である任意の整数は$x^d\equiv1\pmod p$を満たすので、必ずこの中にあります。
5.2節で示した累乗の位数の公式より、
$$ \operatorname{ord}_p(a^k) = \frac{d}{\gcd(k,d)} $$
です。
これが$d$に等しいことと、$\gcd(k,d)=1$であることは同値です。
$1\leqq k\leqq d$のうち$d$と互いに素な整数は、$\phi(d)$個あります。
したがって、位数$d$の整数が一つでも存在するならば、
$$ N(d)=\phi(d) $$
です。

$1,2,\ldots,p-1$の各整数$a$について、フェルマーの小定理より
$$ a^{p-1}\equiv1\pmod p $$
です。
したがって、5.2節の定理より、$a$の位数は必ず$p-1$の約数です。
よって、$p-1$のすべての正の約数$d$について、位数$d$の整数の個数$N(d)$を足すと、
$$ \sum_{d\mid(p-1)}N(d)=p-1 $$
となります。
一方、オイラー関数の約数和より、
$$ \sum_{d\mid(p-1)}\phi(d)=p-1 $$
です。
位数の個数定理より、各$d$について
$$ N(d)=0 \quad\text{または}\quad N(d)=\phi(d) $$
です。
もし、ある約数$d$について$N(d)=0$ならば、$\phi(d)\geqq1$なので、
$$ \sum_{d\mid(p-1)}N(d) < \sum_{d\mid(p-1)}\phi(d) $$
となってしまいます。しかし、両方の和は$p-1$に等しいので矛盾です。
したがって、すべての$d\mid(p-1)$について
$$ N(d)=\phi(d) $$
です。
特に$d=p-1$とすると、位数$p-1$の整数、すなわち原始根の個数は
$$ N(p-1)=\phi(p-1) $$
です。
$\phi(p-1)\geqq1$なので、原始根は必ず存在します。