既約剰余類群
概要
既約剰余類群（multiplicative group of integers modulo $n$）とは、剰余環 $\mathbb{Z}/n\mathbb{Z}$ で掛け算の逆元をもつ剰余類（$n$ と互いに素な整数の剰余類）全体が掛け算についてなす群 $(\mathbb{Z}/n\mathbb{Z})^\times$ である。位数は Euler の関数 $\varphi(n)$ で、Euler の定理はこの群の性質として読める。中国剰余定理で素数冪の法に分かれ、奇素数冪では巡回群、$2^k$（$k\ge3$）では $\{\pm1\}$ と $5$ の冪の直積 $C_2\times C_{2^{k-2}}$ になる。この構造から、指数を与える Carmichael 関数 $\lambda(n)$、$x^2\equiv1$ の解の個数、Carmichael 数の判定が得られる。
正の整数 $n$ を法とする剰余類のうち、掛け算について逆元をもつものだけを集めると群になる。これが 既約剰余類群（multiplicative group of integers modulo $n$）$(\mathbb Z/n\mathbb Z)^\times$ である。Fermatの小定理・Eulerの定理(整数論)・原始根・平方剰余・RSA 暗号は、どれもこの有限アーベル群の性質として読める。この記事では、群としての定義と基本の形を述べたあと、主定理として すべての $n$ についての群の構造（どんな巡回群の直積になるか）を決定し、そこから指数（Carmichael 関数）、$x^2\equiv1$ の解の個数、Carmichael 数の判定を導く。
定義
$n\ge1$ とし、$\mathbb Z/n\mathbb Z$ を法 $n$ の剰余環とする。整数 $a$ の剰余類を $[a]$ または $a\bmod n$ と書く。
剰余環 $\mathbb Z/n\mathbb Z$ の単元（掛け算の逆元をもつ元）全体を
$$
(\mathbb Z/n\mathbb Z)^\times=\{[a]\in\mathbb Z/n\mathbb Z\mid [a][b]=[1]\text{ となる }[b]\text{ がある}\}
$$
と書き、剰余類の掛け算について群とみて 既約剰余類群（法 $n$ の単数群）という。その元を法 $n$ の 既約剰余類 という。
同じ群を $U_n$ と書く本もある（Cri24 Definition 9.1.2、p. 122）。
単元の積は単元で（$[a][b]$ の逆元は $[b]^{-1}[a]^{-1}$）、$[1]$ は単元で、単元の逆元も単元なので、$(\mathbb Z/n\mathbb Z)^\times$ は可換な群である（乗法群 の記事の定義「単元と乗法群」）。$n=1$ では $\mathbb Z/1\mathbb Z=\{0\}$ で $0=1$ なので、$(\mathbb Z/1\mathbb Z)^\times$ は $1$ 元の群である。
どの剰余類が単元かは、最大公約数で判定できる。
- $[a]$ が単元であることと $\gcd(a,n)=1$ は同値である（乗法群 の記事の命題「剰余環の乗法群」、合同式の割り算と逆元 の記事の定理「逆元をもつ条件」。証明は Bézout の等式 $ax+ny=1$ による）。
- この条件は代表元の選び方によらない。$\gcd(a+kn,n)=\gcd(a,n)$ だからである。
- したがって $(\mathbb Z/n\mathbb Z)^\times$ の位数は $\varphi(n)$（$1\le a\le n$ で $\gcd(a,n)=1$ となる $a$ の個数、Eulerのφ関数）である。
有限群の元の位数は群の位数を割るので（Lagrangeの定理）、$\gcd(a,n)=1$ なら $a^{\varphi(n)}\equiv1\pmod n$ である。これが Eulerの定理(整数論) であり、$n=p$ が素数のときが Fermatの小定理 である。
有限群 $G$ の 指数 とは、すべての $x\in G$ について $x^m=1$ となる最小の正の整数 $m$ のことである。$(\mathbb Z/n\mathbb Z)^\times$ の指数を $\lambda(n)$ と書き、Carmichael 関数 という。すなわち $\lambda(n)$ は、$n$ と互いに素なすべての整数 $a$ について $a^m\equiv1\pmod n$ となる最小の正の整数 $m$ である。
$G$ のすべての元について $x^m=1$ となる整数 $m$ の全体は $\mathbb Z$ の部分群なので、指数の倍数全体に一致する。$G$ が位数 $N$ の有限アーベル群なら $x^N=1$ なので指数は $N$ を割る。とくに $\lambda(n)\mid\varphi(n)$ である。指数が位数に等しいのは、$G$ が巡回群のとき、かつそのときに限る（巡回群なら生成元の位数が $N$。逆は、有限アーベル群には位数が指数に等しい元があることによる。この事実はこの記事では証明しない（Sho08 Theorem 6.41、p. 161）。$(\mathbb Z/n\mathbb Z)^\times$ については、この逆向きを使わず主定理から直接確かめる）。
直感
$(\mathbb Z/n\mathbb Z)^\times$ は「法 $n$ の世界で割り算ができる数」の集まりである。$n$ が素数なら $0$ 以外のすべてが入り、群は巡回群になる（原始根の存在）。$n$ が合成数になると、中国剰余定理によって法が素数冪に分かれ、群も素数冪ごとの群の直積に分かれる。奇素数冪では群は巡回群のままだが、$2$ の冪 $2^k$（$k\ge3$）では符号 $\pm1$ と「$5$ の冪」の 2 つの独立な方向があり、巡回群にならない。この「奇素数では 1 方向、$2$ では 2 方向」という違いは、p進数体 の乗法群の構造（$1$ に近い単元の群の構造）でもそのまま現れる。
例
次の表で、$C_m$ は位数 $m$ の巡回群、「生成元」はその積で群全体を表せる元の組である。
| $n$ | $\varphi(n)$ | 群の構造 | $\lambda(n)$ | 生成元 |
|---|---|---|---|---|
| $5$ | $4$ | $C_4$ | $4$ | $2$ |
| $7$ | $6$ | $C_6$ | $6$ | $3$ |
| $8$ | $4$ | $C_2\times C_2$ | $2$ | $3,\ 5$ |
| $9$ | $6$ | $C_6$ | $6$ | $2$ |
| $12$ | $4$ | $C_2\times C_2$ | $2$ | $5,\ 7$ |
| $15$ | $8$ | $C_2\times C_4$ | $4$ | $14,\ 2$ |
| $16$ | $8$ | $C_2\times C_4$ | $4$ | $15,\ 5$ |
| $20$ | $8$ | $C_2\times C_4$ | $4$ | $19,\ 3$ |
| $21$ | $12$ | $C_2\times C_6$ | $6$ | $20,\ 2$ |
| $24$ | $8$ | $C_2\times C_2\times C_2$ | $2$ | $5,\ 7,\ 13$ |
たとえば法 $15$ では $2$ の冪が $2,4,8,1$ と位数 $4$ で回り、$14\equiv-1$ はこの 4 個に含まれない位数 $2$ の元なので、$\{\pm1\}\times\{1,2,4,8\}$ が $8$ 個の既約剰余類をちょうど 1 回ずつ表す。法 $24$ では、$24$ と互いに素な $1,5,7,11,13,17,19,23$ の 2 乗はすべて $1$ と合同で、群は位数 $2$ の元ばかりである。
法 $8$ の既約剰余類は $1,3,5,7$ で、$3^2=9$、$5^2=25$、$7^2=49$ はすべて $1$ と合同である。位数 $4$ の元がないので巡回群 $C_4$ ではなく、$C_2\times C_2$（Klein の四元群）である（原始根 の記事の例「反例：法 8 には原始根がない」）。
性質
自己同型群としての意味
加法群 $\mathbb Z/n\mathbb Z$ の自己同型全体のなす群 $\operatorname{Aut}(\mathbb Z/n\mathbb Z)$ について、写像
$$
(\mathbb Z/n\mathbb Z)^\times\to\operatorname{Aut}(\mathbb Z/n\mathbb Z),\qquad [u]\mapsto\bigl(x\mapsto ux\bigr)
$$
は群の同型である。
$\mathbb Z/n\mathbb Z$ の加法群の準同型 $\phi$ は $\phi([1])$ で決まる。実際 $u$ を $\phi([1])=[u]$ となる整数とすると、$[x]=[1]+\dots+[1]$（$x$ 個、$x\ge0$ の代表元をとる）から $\phi([x])=x[u]=[ux]$ である。逆に各 $[u]$ について $\phi_u([x])=[ux]$ は well-defined な加法群の準同型である（$x\equiv x'$ なら $ux\equiv ux'\pmod n$）。$\phi_u\circ\phi_v=\phi_{uv}$ である。
$[u]$ が単元なら $\phi_{u^{-1}}$ が逆写像なので $\phi_u$ は自己同型である。逆に $\phi_u$ が自己同型なら全射なので $[uv]=\phi_u([v])=[1]$ となる $[v]$ があり、$[u]$ は単元である。よって $[u]\mapsto\phi_u$ は $(\mathbb Z/n\mathbb Z)^\times$ から $\operatorname{Aut}(\mathbb Z/n\mathbb Z)$ への全単射で、$\phi_u\circ\phi_v=\phi_{uv}$ から群の準同型である。
位数 $n$ の巡回群はすべて $\mathbb Z/n\mathbb Z$ に同型なので、この命題は「位数 $n$ の巡回群の自己同型群は $(\mathbb Z/n\mathbb Z)^\times$ である」とも言える。$(\mathbb Z/n\mathbb Z)^\times$ から $\mathbb C^\times$ への準同型は Dirichlet 指標（法 $n$）と呼ばれ、算術級数の中に素数が無限に多くあるという Dirichlet の定理の証明で使われる（Dirichlet指標）。
素数冪への分解と奇素数冪
$n=\prod_ip_i^{e_i}$ と素因数分解すると、中国剰余定理の環同型 $\mathbb Z/n\mathbb Z\cong\prod_i\mathbb Z/p_i^{e_i}\mathbb Z$ は単元どうしを対応させるので、群の同型
$$
(\mathbb Z/n\mathbb Z)^\times\cong\prod_i(\mathbb Z/p_i^{e_i}\mathbb Z)^\times
$$
が得られる（合成数を法とする合同式 の記事の命題「単数群の素数冪分解」）。したがって構造の決定は素数冪の法に帰着する。
奇素数 $p$ と $e\ge1$ について、法 $p^e$ の原始根が存在する（原始根 の記事の定理「原始根が存在する法」）。すなわち $(\mathbb Z/p^e\mathbb Z)^\times$ は位数 $\varphi(p^e)=(p-1)p^{e-1}$ の巡回群である。
$2$ の冪の法
$2$ の冪では原始根は $2$ と $4$ にしかない（同じ定理）。$k\ge3$ のとき、群がどのような直積になるかを決めるのが次の定理である。
各 $j\ge0$ について $5^{2^j}=1+2^{j+2}s_j$、$s_j$ は奇数、と書ける。
$j=0$ では $5=1+2^2\cdot1$ である。$5^{2^j}=1+2^{j+2}s$（$s$ 奇数）なら
$$
5^{2^{j+1}}=(1+2^{j+2}s)^2=1+2^{j+3}s+2^{2j+4}s^2=1+2^{j+3}\bigl(s+2^{j+1}s^2\bigr)
$$
であり、$s+2^{j+1}s^2$ は奇数である。
$(\mathbb Z/2\mathbb Z)^\times$ は $1$ 元の群、$(\mathbb Z/4\mathbb Z)^\times=\{\pm1\}\cong C_2$ である。$k\ge3$ なら、$5$ の法 $2^k$ での位数は $2^{k-2}$ であり、写像
$$
\{\pm1\}\times\langle5\rangle\to(\mathbb Z/2^k\mathbb Z)^\times,\qquad(\varepsilon,x)\mapsto\varepsilon x
$$
は群の同型である。したがって $(\mathbb Z/2^k\mathbb Z)^\times\cong C_2\times C_{2^{k-2}}$ である。さらに $\langle5\rangle$ は法 $4$ で $1$ と合同な既約剰余類全体に一致する。
$k=1,2$ は直接確かめられる。$k\ge3$ とする。
段 1（$5$ の位数）．lem-ug-five-powers で $j=k-2$ とすると $5^{2^{k-2}}\equiv1\pmod{2^k}$ なので、$5$ の位数は $2^{k-2}$ の約数、すなわち $2$ の冪である。$j=k-3$ とすると $5^{2^{k-3}}=1+2^{k-1}s$（$s$ 奇数）$\not\equiv1\pmod{2^k}$ なので、位数は $2^{k-3}$ を割らない。よって位数はちょうど $2^{k-2}$ である。
段 2（$\langle5\rangle$ の決定）．$A=\{[x]\in(\mathbb Z/2^k\mathbb Z)^\times\mid x\equiv1\pmod4\}$ は部分群で（法 $4$ で $1$ と合同な数の積はまた $1$ と合同）、$0\le x<2^k$、$x\equiv1\pmod 4$ となる $x$ は $2^k/4=2^{k-2}$ 個なので $|A|=2^{k-2}$ である。$5\equiv1\pmod4$ より $\langle5\rangle\subset A$ で、段 1 から両者の元の個数は等しいので $\langle5\rangle=A$ である。
段 3（直積）．奇数 $u$ は法 $4$ で $1$ か $3$ と合同なので、$u$ と $-u$ のちょうど一方が $A$ に属する。よって写像は全射である。$\varepsilon x\equiv1$（$\varepsilon=\pm1$、$x\in A$）なら $\varepsilon\equiv x^{-1}\equiv1\pmod 4$ なので $\varepsilon=1$（$-1\equiv3\pmod4$）、したがって $x=1$ であり、写像は単射である。$\{\pm1\}\times\langle5\rangle$ の積は成分ごとなので、写像は群の準同型である（群は可換）。位数は $2\cdot2^{k-2}=2^{k-1}=\varphi(2^k)$ で一致している。
原始根 の記事の補題「2 の冪の法」は「すべての奇数 $u$ について $u^{2^{k-2}}\equiv1\pmod{2^k}$」を示しており、これは上の定理で群の指数が $2^{k-2}$ 以下であることに当たる。上の定理は、その上限 $2^{k-2}$ が $5$ で実際に達せられること、そして群が $\pm1$ と $5$ の冪にきれいに分かれることまで述べている（同じ主張は Sho08 Theorem 7.28 にある）。
主定理：構造定理
$n=2^kp_1^{e_1}\cdots p_r^{e_r}$（$k\ge0$、$p_1,\dots,p_r$ は相異なる奇素数、$e_i\ge1$）とする。このとき
$$
(\mathbb Z/n\mathbb Z)^\times\cong T_k\times C_{(p_1-1)p_1^{e_1-1}}\times\cdots\times C_{(p_r-1)p_r^{e_r-1}}
$$
である。ここで $T_0=T_1$ は $1$ 元の群、$T_2=C_2$、$k\ge3$ なら $T_k=C_2\times C_{2^{k-2}}$ である。
中国剰余定理による分解 $(\mathbb Z/n\mathbb Z)^\times\cong(\mathbb Z/2^k\mathbb Z)^\times\times\prod_i(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ から始める（$k=0$ では最初の因子はない）。奇素数冪の因子は、法 $p_i^{e_i}$ の原始根が生成する位数 $\varphi(p_i^{e_i})=(p_i-1)p_i^{e_i-1}$ の巡回群である（原始根 の記事の定理「原始根が存在する法」）。$2$ の冪の因子は thm-ug-power-of-two により $T_k$ である。
$(p-1)$ と $p^{e-1}$ は互いに素なので、$C_{(p-1)p^{e-1}}\cong C_{p-1}\times C_{p^{e-1}}$ とも書ける。この形は p進数体 の記事の系「$\mathbb Q_p^\times$ の構造」の $\mathbb Z_p^\times\cong\mathbb Z/(p-1)\mathbb Z\times\mathbb Z_p$ を法 $p^e$ で見たものに当たる。$2$ の冪でも、$\mathbb Z_2^\times=\{\pm1\}\times5^{\mathbb Z_2}$ を法 $2^k$ で見たものが $T_k$ である。
Carmichael 関数
$\lambda(1)=\lambda(2)=1$、$\lambda(4)=2$、$k\ge3$ なら $\lambda(2^k)=2^{k-2}$、奇素数冪では $\lambda(p^e)=\varphi(p^e)=(p-1)p^{e-1}$ であり、$n=2^kp_1^{e_1}\cdots p_r^{e_r}$ について
$$
\lambda(n)=\operatorname{lcm}\bigl(\lambda(2^k),\lambda(p_1^{e_1}),\dots,\lambda(p_r^{e_r})\bigr)
$$
である。すべての $a$ で $\gcd(a,n)=1$ なら $a^{\lambda(n)}\equiv1\pmod n$ であり、$\lambda(n)$ はこの性質をもつ最小の正の整数である。
有限群 $G_1,\dots,G_s$ の直積の元 $x=(x_1,\dots,x_s)$ について $x^m=1$ は「すべての $i$ で $x_i^m=1$」と同じである。よって「直積のすべての元で $x^m=1$」となる $m$ の全体は、各 $G_i$ の指数の倍数全体の共通部分、すなわち指数の最小公倍数の倍数全体であり、直積の指数は各因子の指数の最小公倍数である。巡回群 $C_m$ の指数は生成元の位数 $m$ であり、$C_2\times C_{2^{k-2}}$（$k\ge3$）の指数は $\operatorname{lcm}(2,2^{k-2})=2^{k-2}$ である。これを thm-ug-structure の各因子に当てはめればよい。
たとえば $\lambda(15)=\operatorname{lcm}(2,4)=4$ で、$\varphi(15)=8$ より小さい。したがって $7^{100}=(7^4)^{25}\equiv1\pmod{15}$ のように、Euler の定理の指数 $\varphi(n)$ を $\lambda(n)$ に下げて計算できる（$7^4=2401=15\cdot160+1$）。$\lambda(n)=\varphi(n)$ となるのは群が巡回群のとき、すなわち $n=1,2,4,p^e,2p^e$（$p$ 奇素数）のときに限る。これは 原始根 の記事の定理「原始根が存在する法」の言い換えであり、構造定理の側からは、互いに素でない偶数位数の巡回群が 2 つ以上並ぶと指数が位数より小さくなることとして見える。
$x^2\equiv1$ の解の個数
素数 $p$ を法とすると $x^2\equiv1$ の解は $\pm1$ だけだが、合成数の法ではそうとは限らない。
$n=2^kp_1^{e_1}\cdots p_r^{e_r}$ を構造定理と同じ形とする。合同式 $x^2\equiv1\pmod n$ の法 $n$ での解の個数は
$$
2^r\cdot c_k,\qquad c_k=\begin{cases}1&(k=0,1),\\2&(k=2),\\4&(k\ge3)\end{cases}
$$
である。
$x^2\equiv1$ の解は $\gcd(x,n)=1$ を満たすので（$x\cdot x\equiv1$）、$(\mathbb Z/n\mathbb Z)^\times$ の中で $x^2=1$ となる元を数えればよい。直積では $x^2=1$ は成分ごとの条件なので、個数は因子ごとの個数の積である。巡回群 $C_m=\langle g\rangle$ で $(g^i)^2=1$（$0\le i< m$）は $m\mid2i$ と同値で、$m$ が偶数なら $i=0,m/2$ の $2$ 個、奇数なら $i=0$ の $1$ 個である。奇素数冪の因子 $C_{(p-1)p^{e-1}}$ は位数が偶数なので $2$ 個ずつ、$T_0,T_1$ は $1$ 個、$T_2=C_2$ は $2$ 個、$T_k=C_2\times C_{2^{k-2}}$（$k\ge3$、$2^{k-2}$ は偶数）は $2\cdot2=4$ 個である。
たとえば $n=15$ では $r=2$、$k=0$ で解は $4$ 個（$1,4,11,14$）、$n=24$ では $r=1$、$k=3$ で $8$ 個（$24$ と互いに素な $8$ 個すべて）である。$n$ が奇素数冪なら解は $\pm1$ の $2$ 個だけである。Wilsonの定理 の記事の定理「Gaussによる一般化」は、既約剰余類全体の積が $-1$ と合同になるのが $n=2,4,p^e,2p^e$ のときであることを述べている。$n\ge3$ ではこれはちょうど $x^2\equiv1$ の解が $\pm1$ の $2$ 個だけの場合であり、この個数の公式と組み合わせて読める。
Carmichael 数
$p$ が素数なら $\gcd(a,p)=1$ のとき $a^{p-1}\equiv1\pmod p$ である。この逆は成り立たない。合成数 $n$ で、$n$ と互いに素なすべての $a$ について $a^{n-1}\equiv1\pmod n$ となるものを Carmichael 数 という（Ste17 §2.4、p. 37）。
$n\ge2$ について、$n$ と互いに素なすべての整数 $a$ で $a^{n-1}\equiv1\pmod n$ となるための必要十分条件は $\lambda(n)\mid n-1$ である。
def-ug-exponent の直後に述べたとおり、群のすべての元で $x^m=1$ となる整数 $m$ の全体は指数の倍数全体である。$(\mathbb Z/n\mathbb Z)^\times$ の指数は $\lambda(n)$ なので、「すべての既約剰余類 $a$ で $a^{n-1}=1$」は $\lambda(n)\mid n-1$ と同値である。
$561=3\cdot11\cdot17$ で、cor-ug-carmichael-function より
$$
\lambda(561)=\operatorname{lcm}(2,10,16)=80,\qquad 560=7\cdot80
$$
なので、prop-ug-carmichael-number により $561$ と互いに素なすべての $a$ で $a^{560}\equiv1\pmod{561}$ である。$561$ は合成数なので Carmichael 数である。一方 $\varphi(561)=2\cdot10\cdot16=320$ は $560$ を割らないので、Euler の定理の指数だけからはこの結論は出てこない。
反例と注意
次の表は、既約剰余類群について誤りやすい推論を、条件を外した反例で示したものである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\gcd(a,n)=1$ | $n=4$、$a=2$ | $2x\equiv1\pmod 4$ の解（逆元）がなく、$2$ は群に入らない |
| 法が $2,4,p^e,2p^e$ | $n=8$ | 群が巡回群であること（$C_2\times C_2$） |
| 法が素数 | $n=15$ | $x^2\equiv1$ の解が $\pm1$ だけであること（$4,11$ も解） |
| 群が巡回群 | $n=15$ | 指数が位数に等しいこと（$\lambda(15)=4<8=\varphi(15)$） |
| 法が素数 | $n=561$ | 「すべての $a$ で $a^{n-1}\equiv1$ なら $n$ は素数」 |
$4^2=16\equiv1$、$11^2=121=8\cdot15+1\equiv1\pmod{15}$ なので、$x^2\equiv1\pmod{15}$ は $\pm1$ 以外に $4,11$ という解をもつ。素数 $p$ を法とするときは $\mathbb Z/p\mathbb Z$ が体なので $(x-1)(x+1)\equiv0$ から $x\equiv\pm1$ が従うが、法 $15$ では $(4-1)(4+1)=15\equiv0$ のように $0$ でない数の積が $0$ になる。この例は、条件「法が素数」を外すと含意「$x^2\equiv1\Rightarrow x\equiv\pm1$」が破れることを示す。
「$a^{\varphi(n)}\equiv1$」は群の位数による主張で、どの $n$ でも成り立つ。「$a^{m}\equiv1$ がすべての $a$ で成り立つ最小の $m$」は指数 $\lambda(n)$ で、巡回群でないときは $\varphi(n)$ より真に小さい。個々の元の位数は $\lambda(n)$ を割る。たとえば法 $24$ では $\varphi(24)=8$ だが、すべての元の位数は $1$ か $2$ で、$\lambda(24)=2$ である。
関連項目
- 前提: 合同式, 乗法群, Eulerのφ関数, 中国剰余定理
- 比較: 原始根, 合成数を法とする合同式, Wilsonの定理
- 直後に読む: Eulerの定理(整数論), Dirichlet指標, 平方剰余
- 発展: p進数体, 初等整数論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
