初等整数論/合成数を法とする剰余類の構造

素数を法とする場合、原始根が存在して、すべての既約剰余類が原始根の累乗によりあらわされることを先に見た。合成数を法としたとき、既約剰余類はどのような構造を持つだろうか。

素数の冪を法とする場合

中国の剰余定理から、素数の冪を法とする場合に還元できるので、まず、素数の冪を法とする場合を考える。

実は、奇素数の冪を法とする場合には素数を法とする場合同様、原始根に相当するものが存在し、すべての既約剰余類が原始根の累乗によりあらわされることがわかる。ところが2の冪を法とする場合は、幾分複雑である。というのは $8=2^3$ に対して $3^2\equiv 5^2\equiv 7^2\equiv 1(\mathrm{mod}8)$ となるからである。

8 を法とした既約剰余系の乗法は以下の構造を持つ。

乗法

×	1	3	5	7
1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

したがって $2^e(e\ge 3)$ を法とする既約剰余類は1つの剰余類の累乗だけで表すことができない。

2の場合でも奇素数の場合でも、指数に関して帰納的に考察することとなる。まず、次の事実がわかる。

命題

$p$ を素数とし $k$ を正の整数とする。 $a$ に対して合同式 $a\equiv 1(\mathrm{mod}{p}^k)$ かつ $a\equiv ̸1(\mathrm{mod}{p}^{k+1})$ が成り立つものとする。 このとき $a^s\equiv 1(\mathrm{mod}{p}^{k+1})⟺p|s$ である。さらに $p=2$ のときは $k\ge 2$ とすれば $a^p\equiv 1(\mathrm{mod}{p}^{k+1})$ かつ $a^p\equiv ̸1(\mathrm{mod}{p}^{k+2})$ である。

証明

$a=b{p}^k+1$ とおくと $a\equiv ̸1(\mathrm{mod}{p}^{k+1})$ より $b$ は $p$ で割り切れない。

$a^s\equiv (b{p}^k+1{)}^s\equiv bs{p}^k+1(\mathrm{mod}{p}^{k+1})$

より $a^s\equiv 1(\mathrm{mod}{p}^{k+1})⟺p|bs⟺p|s.$

さらに $p>2$ のとき

$a^p=(b{p}^k+1{)}^p=b^p{p}^{kp}+(p-1)b^{p-1}{p}^{k(p-1)}+\cdots +\frac{p(p-1)}{2}{b}^2{p}^{2k}+pb{p}^k+1\equiv \frac{b^2(p-1)}{2}{p}^{2k+1}+b{p}^{k+1}+1\equiv b{p}^{k+1}+1(\mathrm{mod}{p}^{k+2}).$

$p=2,k\ge 2$ のとき $2k>k+1$ より

$a^2=(b{2}^k+1{)}^2=b^2\cdot 2^{2k}+b\cdot 2^{k+1}+1\equiv 2^{k+1}+1(\mathrm{mod}{2}^{k+2}).$

ここから、素数冪の位数について次の事実がわかる。

補題

$g(\mathrm{mod}p)$ の位数を $e$ とし、

$g^e\equiv 1(\mathrm{mod}{p}^l),g^e\equiv ̸1(\mathrm{mod}{p}^{l+1})$

となる $l\ge 1$ をとる。ここで $p=2$ の場合に限り $l\ge 2$ と仮定する。 このとき $g(\mathrm{mod}{p}^k)$ の位数は

$e(k\le l),e{p}^{k-l}(k\ge l)$

により与えられる。さらに $k\ge l$ のとき

$g^{e{p}^{k-l}}\equiv 1(\mathrm{mod}{p}^k),g^{e{p}^{k-l}}\equiv ̸1(\mathrm{mod}{p}^{k+1})$

が成り立つ。

証明 $g^e\equiv 1(\mathrm{mod}{p}^l)$ より $g(\mathrm{mod}{p}^l)$ の位数は $e$ である。

$k\ge l$ の場合について帰納法により証明する。$g(\mathrm{mod}{p}^k)$ の位数を $e_k$ とおく。

ここで $e_k=e{p}^{k-l}$ かつ $g^{e{p}^{k-l}}\equiv 1(\mathrm{mod}{p}^k),g^{e{p}^{k-l}}\equiv ̸1(\mathrm{mod}{p}^{k+1})$ と仮定する。

$g^f\equiv 1(\mathrm{mod}{p}^{k+1})$ ならば $g^f\equiv 1(\mathrm{mod}{p}^k)$ でなければならないので位数の法則より $f$ は $e_k$ の倍数。 ここで

$a=g^{e_k}=b{p}^k+1,f=s{e}_k$

とおくと $g^f=a^s$ となり、ここで先の命題から

$g^f\equiv 1(\mathrm{mod}{p}^{k+1})⟺p|s⟺p{e}_k|f$

より $e_{k+1}=p{e}_k$ で、しかも

$g^{e{p}^{k+1-l}}\equiv 1(\mathrm{mod}{p}^{k+1}),g^{e{p}^{k+1-l}}\equiv ̸1(\mathrm{mod}{p}^{k+2})$

であることがわかる。

これにより、素数冪を法とする位数が確かに存在し、それが $(p-1)p^{e-1}$ の約数であることがわかる。

さて $p$ が奇数の場合 $g$ を $p$ を法とする原始根とすると $g^{p-1}\equiv 1(\mathrm{mod}{p}^2)$ のとき

$(g+bp{)}^{p-1}\equiv g^{p-1}+(p-1)g^{p-2}bp+\frac{p(p-1)}{2}{g}^{p-3}b{p}^2+\cdots \equiv g^{p-1}+(p-1)g^{p-2}bp(\mathrm{mod}{p}^2)$

であるが $g^{p-2},p-1$ は $p$ と互いに素である。よって

$(g+bp{)}^{p-1}\equiv ̸1(\mathrm{mod}{p}^2)⟺\gcd (b,p)=1$

である。したがってこの場合には $g+bp(\gcd (b,p)=1)$ を改めて $g$ と置き直すことで $g^{p-1}\equiv 1(\mathrm{mod}p),g^{p-1}\equiv ̸1(\mathrm{mod}{p}^2)$ となる $g$ が存在することが言える。 この時、先の補題から $g(\mathrm{mod}{p}^e)$ の位数は $(p-1)p^{e-1}$ である。つまり位数 $p^{e-1}(p-1)$ の剰余類が確かに存在する。これは $p$ と互いに素な剰余類の個数と一致するから、次のことがわかる。

定理 2.5.1

$p$ が奇素数のとき、位数が $p^{e-1}(p-1)$ となる剰余類 $g(\mathrm{mod}{p}^e)$ が存在する。さらに $p^e$ を法とする剰余類で $p$ と互いに素なものは $g^k(\mathrm{mod}{p}^e)(k=0,1,\dots ,p^{e-1}(p-1)-1)$ と一意的にあらわせる。

$p=2$ の場合はどうか。$3^2\equiv 5^2\equiv 9(\mathrm{mod}16)$ であるから、$3,5(\mathrm{mod}{2}^e)$ の位数は $2^{e-2}$ である。$3^k\equiv 1,3(\mathrm{mod}8)$ であり、 $2^e$ を法とする剰余類で 8 を法として 1, 3 と合同であるものの個数は $2^{e-2}$個である。したがって、次の事実がわかる:

$e\ge 3$ のとき、位数が $2^{e-2}$ となる剰余類 $g(\mathrm{mod}{2}^e),g\equiv 3(\mathrm{mod}8)$ が存在する。さらに $2^e$ を法とする剰余類で 8 を法として 1, 3 と合同であるものは $g^k(\mathrm{mod}{p}^e)(k=0,1,\dots ,2^{e-2}-1)$ と一意的にあらわせる。

$8n+1(\mathrm{mod}{2}^e)(n=0,1,\dots ,2^{e-3}-1)$ に対し $-(8n+1)=8\cdot (-n)-1(\mathrm{mod}{2}^e)(n=0,1,\dots ,2^{e-3}-1)$ は 8 を法として 7 と合同な剰余類を一意的に表している。同様に $8n+3(\mathrm{mod}{2}^e)(n=0,1,\dots ,2^{e-3}-1)$ に対し $-(8n+3)=8\cdot (-n)-5(\mathrm{mod}{2}^e)(n=0,1,\dots ,2^{e-3}-1)$ は 8 を法として 5 と合同な剰余類を一意的に表している。よって2の冪を法とする剰余類について次のことがわかる。

定理 2.5.2

$e\ge 3$ のとき、位数が $2^{e-2}$ となる剰余類 $g(\mathrm{mod}{2}^e),g\equiv 3(\mathrm{mod}8)$ が存在する。さらに $2^e$ を法とする剰余類は $\pm g^k(\mathrm{mod}{p}^e)(k=0,1,\dots ,2^{e-2}-1)$ と一意的にあらわせる。

以上のことから、次の定理が従う。

定理 2.5.3

素数冪 $p^e$ に対し $\lambda (p^e)$ を

$\lambda (p^e)=p^{e-1}(p-1)$ （$p>2$ または $p=2,e=1,2$ のとき）

$\lambda (2^e)=2^{e-2}$ （$e\ge 3$ のとき）

により定めると $p$ で割り切れない整数 $a$ に対し

$a^{\lambda (p^e)}\equiv 1(\mathrm{mod}{p}^e)$

が成り立つ。そして $a(\mathrm{mod}{p}^e)$ の位数は $\lambda (p^e)$ の約数である。さらに 位数が $\lambda (p^e)$ に一致する $a(\mathrm{mod}{p}^e)$ が存在する。

一般の場合

定理 2.5.3 と中国の剰余定理から、一般の整数 $n$ を法とする場合の結果がすぐに導かれる。

定理 2.5.4

$n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$ と素因数分解する。 $\lambda (n)$ を $\lambda (p_i^{e_i})(i=1,2,\dots ,k)$ の最小公倍数とすると $n$ と互いに素整数 $a$ に対し

$a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$

が成り立つ。そして $a(\mathrm{mod}n)$ の位数は $\lambda (n)$ の約数である。さらに 位数が $\lambda (n)$ に一致する $a(\mathrm{mod}n)$ が存在する。

ここで定義した関数 $\lambda (n)$ をカーマイケル関数という（なお $\lambda (1)=1$ と定める）。定義から $\lambda (n)$ は $\phi (n)$ の約数であるが、$n=1,2,4,p^e,2p^e$ （$p$ は奇素数）の場合を除いて $\lambda (n)$ は $\phi (n)$ よりも小さい。