📂整数論

コセット判定法

概要

カーマイケル数であるかを判断する方法として、必要十分条件である点がまた役立つ定理だ。

定理 ¹

奇数の合成数を$n$とする。

$n$は、全ての素数$p$に対して$p^2 \nmid n$であり、かつ$(p-1) \mid (n-1)$を満たすカーマイケル数$\iff$$p \mid n$である。

証明

カーマイケル数の定義：自然数$n$が全ての$1 \le a \le n$に対して$a^{n} \equiv a \pmod{n}$を満たす場合、カーマイケル数という。

---

$( \implies )$

カーマイケル数は$2$を除く異なる素数$p_{1} , \cdots , p_{m}$に対して$n = p_{1} \cdots p_{m}$と表せ、従って$p_{i}^2 \nmid n$を満たさなければならない。

$n$はカーマイケル数であるため$a^{n-1} \equiv 1 \pmod{n}$が成り立ち、ある$k$に対して $$a^{n-1} = n \cdot k + 1 = p_{i} \cdot \left( {{n} \over {p_{i}}} k \right) + 1$$ であるため$a^{n-1} \equiv 1 \pmod{p_{i}}$である。

位数の性質：素数$p$に対して$\gcd (a,p)=1$が成り立ち、$a^{n} \equiv 1 \pmod{p}$の場合$\text{ord}_{p} (a) \mid n$である。

位数の性質によって$\text{ord}_{p_{i} } (a)$は$(n-1)$を割り、原始根定理によって少なくとも$1$個の原始根を持つため、ある$a_{i}$に対して $$\text{ord}_{p_{i} } (a_{i}) = p_{i} - 1$$ である。従って、全ての$p_{1} , \cdots , p_{m}$に対して$(p_{i}-1) \mid (n-1)$でなければならない。

---

$( \impliedby )$

$n := p_{1} \cdots p_{m}$とする。

$n$を割る全ての素数$p_{1} , \cdots , p_{m}$に対して$p^2 \nmid n$であるため、$p_{1} , \cdots , p_{m}$は異なる。

$(p-1) \mid (n-1)$であるため、ある整数$k_{i}$に対して $$(n-1 ) = ( p_{i} - 1) k_{i}$$ 今、$1 \le a \le n$として$p_{i}$を割る場合と割らない場合を考える。

• ケース1. $p_{i} \mid a$
  明らかに$a^{n} \equiv 0 \equiv a \pmod{p_{i}}$が成立する。
• ケース2. $p_{i} \nmid a$
  フェルマーの小定理によると $$\begin{align*} a^{n} =& a^{ ( p_{i} - 1) k_{i} +1 } \\ =& a^{ ( p_{i} - 1) k_{i} } \cdot a \\ \equiv& 1^{k_{i}} \cdot a \pmod{p_{i}} \\ \equiv& a \pmod{p_{i}} \end{align*}$$

従って、どの場合でも $$( a^{n} - a ) \equiv 0 \pmod{ p_{i} }$$ となり、これはすなわち$( a^{n} - a )$が$p_{1}, \cdots , p_{m}$で割り切れるということである。言い換えれば、$( a^{n} - a )$は$n= p_{1} \cdots p_{m}$で割り切れ、要約すると次のようになる。 $$( a^{n} - a ) \equiv 0 \pmod{ n }$$

■