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

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

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

8 を法とした既約剰余系の乗法は以下の構造を持つ。
素数の冪を法とする場合

したがって 2 e ( e ≥ 3 ) {\displaystyle 2^{e}(e\geq 3)} を法とする既約剰余類は1つの剰余類の累乗だけで表すことができない。
素数の冪を法とする場合

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

命題
素数の冪を法とする場合

p {\displaystyle p} を素数とし k {\displaystyle k} を正の整数とする。 a {\displaystyle a} に対して合同式 a ≡ 1 ( mod p k ) {\displaystyle a\equiv 1{\pmod {p^{k}}}} かつ a ≢ 1 ( mod p k + 1 ) {\displaystyle a\not \equiv 1{\pmod {p^{k+1}}}} が成り立つものとする。 このとき a s ≡ 1 ( mod p k + 1 ) ⟺ p | s {\displaystyle a^{s}\equiv 1{\pmod {p^{k+1}}}\iff p|s} である。さらに p = 2 {\displaystyle p=2} のときは k ≥ 2 {\displaystyle k\geq 2} とすれば a p ≡ 1 ( mod p k + 1 ) {\displaystyle a^{p}\equiv 1{\pmod {p^{k+1}}}} かつ a p ≢ 1 ( mod p k + 2 ) {\displaystyle a^{p}\not \equiv 1{\pmod {p^{k+2}}}} である。
素数の冪を法とする場合

証明
素数の冪を法とする場合

a = b p k + 1 {\displaystyle a=bp^{k}+1} とおくと a ≢ 1 ( mod p k + 1 ) {\displaystyle a\not \equiv 1{\pmod {p^{k+1}}}} より b {\displaystyle b} は p {\displaystyle p} で割り切れない。
素数の冪を法とする場合

より a s ≡ 1 ( mod p k + 1 ) ⟺ p | b s ⟺ p | s . {\displaystyle a^{s}\equiv 1{\pmod {p^{k+1}}}\iff p|bs\iff p|s.}
素数の冪を法とする場合

さらに p > 2 {\displaystyle p>2} のとき
素数の冪を法とする場合

p = 2 , k ≥ 2 {\displaystyle p=2,k\geq 2} のとき 2 k > k + 1 {\displaystyle 2k>k+1} より
素数の冪を法とする場合

ここから、素数冪の位数について次の事実がわかる。
素数の冪を法とする場合

補題
素数の冪を法とする場合

g ( mod p ) {\displaystyle g{\pmod {p}}} の位数を e {\displaystyle e} とし、
素数の冪を法とする場合

となる l ≥ 1 {\displaystyle l\geq 1} をとる。ここで p = 2 {\displaystyle p=2} の場合に限り l ≥ 2 {\displaystyle l\geq 2} と仮定する。 このとき g ( mod p k ) {\displaystyle g{\pmod {p^{k}}}} の位数は
素数の冪を法とする場合

により与えられる。さらに k ≥ l {\displaystyle k\geq l} のとき
素数の冪を法とする場合

が成り立つ。
素数の冪を法とする場合

証明 g e ≡ 1 ( mod p l ) {\displaystyle g^{e}\equiv 1{\pmod {p^{l}}}} より g ( mod p l ) {\displaystyle g{\pmod {p^{l}}}} の位数は e {\displaystyle e} である。
素数の冪を法とする場合

k ≥ l {\displaystyle k\geq l} の場合について帰納法により証明する。 g ( mod p k ) {\displaystyle g{\pmod {p^{k}}}} の位数を e k {\displaystyle e_{k}} とおく。
素数の冪を法とする場合

ここで e k = e p k − l {\displaystyle e_{k}=ep^{k-l}} かつ g e p k − l ≡ 1 ( mod p k ) , g e p k − l ≢ 1 ( mod p k + 1 ) {\displaystyle g^{ep^{k-l}}\equiv 1{\pmod {p^{k}}},g^{ep^{k-l}}\not \equiv 1{\pmod {p^{k+1}}}} と仮定する。
素数の冪を法とする場合

g f ≡ 1 ( mod p k + 1 ) {\displaystyle g^{f}\equiv 1{\pmod {p^{k+1}}}} ならば g f ≡ 1 ( mod p k ) {\displaystyle g^{f}\equiv 1{\pmod {p^{k}}}} でなければならないので位数の法則より f {\displaystyle f} は e k {\displaystyle e_{k}} の倍数。 ここで
素数の冪を法とする場合

とおくと g f = a s {\displaystyle g^{f}=a^{s}} となり、ここで先の命題から
素数の冪を法とする場合

より e k + 1 = p e k {\displaystyle e_{k+1}=pe_{k}} で、しかも
素数の冪を法とする場合

であることがわかる。
素数の冪を法とする場合

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

さて p {\displaystyle p} が奇数の場合 g {\displaystyle g} を p {\displaystyle p} を法とする原始根とすると g p − 1 ≡ 1 ( mod p 2 ) {\displaystyle g^{p-1}\equiv 1{\pmod {p^{2}}}} のとき
素数の冪を法とする場合

であるが g p − 2 , p − 1 {\displaystyle g^{p-2},p-1} は p {\displaystyle p} と互いに素である。よって
素数の冪を法とする場合

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

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

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

e ≥ 3 {\displaystyle e\geq 3} のとき、位数が 2 e − 2 {\displaystyle 2^{e-2}} となる剰余類 g ( mod 2 e ) , g ≡ 3 ( mod 8 ) {\displaystyle g{\pmod {2^{e}}},g\equiv 3{\pmod {8}}} が存在する。さらに 2 e {\displaystyle 2^{e}} を法とする剰余類で 8 を法として 1, 3 と合同であるものは g k ( mod p e ) ( k = 0 , 1 , ... , 2 e − 2 − 1 ) {\displaystyle g^{k}{\pmod {p^{e}}}(k=0,1,\ldots ,2^{e-2}-1)} と一意的にあらわせる。
素数の冪を法とする場合

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

e ≥ 3 {\displaystyle e\geq 3} のとき、位数が 2 e − 2 {\displaystyle 2^{e-2}} となる剰余類 g ( mod 2 e ) , g ≡ 3 ( mod 8 ) {\displaystyle g{\pmod {2^{e}}},g\equiv 3{\pmod {8}}} が存在する。さらに 2 e {\displaystyle 2^{e}} を法とする剰余類は ± g k ( mod p e ) ( k = 0 , 1 , ... , 2 e − 2 − 1 ) {\displaystyle \pm g^{k}{\pmod {p^{e}}}(k=0,1,\ldots ,2^{e-2}-1)} と一意的にあらわせる。
素数の冪を法とする場合

以上のことから、次の定理が従う。
素数の冪を法とする場合

素数冪 p e {\displaystyle p^{e}} に対し λ ( p e ) {\displaystyle \lambda (p^{e})} を
素数の冪を法とする場合

により定めると p {\displaystyle p} で割り切れない整数 a {\displaystyle a} に対し
素数の冪を法とする場合

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

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

n = p 1 e 1 p 2 e 2 ⋯ p k e k {\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}} と素因数分解する。 λ ( n ) {\displaystyle \lambda (n)} を λ ( p i e i ) ( i = 1 , 2 , ... , k ) {\displaystyle \lambda (p_{i}^{e_{i}})(i=1,2,\ldots ,k)} の最小公倍数とすると n {\displaystyle n} と互いに素整数 a {\displaystyle a} に対し
一般の場合

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

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