擬素数

$(\mathbb Z/n\mathbb Z)^\times$ は可換群なので、写像 $f\colon x\mapsto x^{n-1}$ は $f(xy)=(xy)^{n-1}=x^{n-1}y^{n-1}=f(x)f(y)$ を満たす準同型である。$B(n)$ はその核 $f^{-1}(1)$ なので部分群である。後半は、$a,b\in B(n)$ なら $ab\in B(n)$、$b^{-1}\in B(n)$ であることの言い換えである。$\square$

$g$ を $C$ の生成元とすると、$C$ の元は $g^j$（$0\le j< m$）とただ一通りに書け、$g^s=1$ であることと $m\mid s$ は同値である（元の位数）。よって $(g^j)^k=1$ は $m\mid jk$ と同値である。$d=\gcd(k,m)$、$m=dm'$、$k=dk'$ とおくと $\gcd(m',k')=1$ なので、$m\mid jk$ は $m'\mid jk'$、さらに $m'\mid j$ と同値である。$0\le j< m$ のうち $m'$ の倍数は $j=0,m',2m',\dots,(d-1)m'$ の $d$ 個である。$\square$

$n=p_1^{e_1}\cdots p_r^{e_r}$ と素因数分解する。中国剰余定理 により、法 $n$ の剰余類と、各法 $p_i^{e_i}$ の剰余類の組は一対一に対応し、この対応で $(\mathbb Z/n\mathbb Z)^\times$ は $\prod_i(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ に移る。$a^{n-1}\equiv1\pmod n$ は、すべての $i$ について $a^{n-1}\equiv1\pmod{p_i^{e_i}}$ が成り立つことと同値である。したがって
$$ \lvert B(n)\rvert=\prod_{i=1}^rN_i,\qquad N_i:=\#\{x\in(\mathbb Z/p_i^{e_i}\mathbb Z)^\times : x^{n-1}=1\} $$
である。各 $N_i$ を求める。以下 $p=p_i$、$e=e_i$ と書く。
$p$ が奇数のとき：$(\mathbb Z/p^e\mathbb Z)^\times$ は位数 $\varphi(p^e)=p^{e-1}(p-1)$ の巡回群である（原始根 の記事の定理「原始根が存在する法」）。lem-psp-cyclic-roots により $N_i=\gcd(n-1,\,p^{e-1}(p-1))$ である。$p\mid n$ なので $p\nmid n-1$ であり、$n-1$ は $p^{e-1}$ と互いに素である。一般に $\gcd(k,u)=1$ なら $\gcd(k,uv)=\gcd(k,v)$ なので（$k$ と $uv$ の公約数は $u$ と互いに素だから $v$ を割る）、$N_i=\gcd(n-1,p-1)$ である。
$p=2$ のとき：$n$ は偶数なので $n-1$ は奇数である。$(\mathbb Z/2^e\mathbb Z)^\times$ の位数は $2^{e-1}$ なので、$x^{n-1}=1$ を満たす元 $x$ の位数は $n-1$ と $2^{e-1}$ の両方を割り、したがって $1$ である。よって $x=1$ だけで、$N_i=1=\gcd(2-1,n-1)$ である。
以上を掛け合わせて公式を得る。$\square$

1：$\varphi(n)=\prod_ip_i^{e_i-1}(p_i-1)$ であり、thm-psp-count により $\lvert B(n)\rvert=\prod_i\gcd(p_i-1,n-1)$ である。各因子について $\gcd(p_i-1,n-1)\le p_i-1\le p_i^{e_i-1}(p_i-1)$ なので、両者が等しいことは、すべての $i$ で $e_i=1$ かつ $\gcd(p_i-1,n-1)=p_i-1$、すなわち $p_i-1\mid n-1$ であることと同値である。
2：$n$ が Carmichael 数でないとは、$n$ と互いに素なある $a$ について $a^{n-1}\not\equiv1\pmod n$ となること、すなわち $B(n)\ne(\mathbb Z/n\mathbb Z)^\times$ である。prop-psp-subgroup により $B(n)$ は部分群なので、Lagrangeの定理 により $\lvert B(n)\rvert$ は $\varphi(n)$ の約数であり、$\varphi(n)$ と異なるので $\varphi(n)/2$ 以下である。$\square$

$m$ が合成数であること：$n$ は合成数なので $n=rs$（$1< r< n$）と書ける。$x=2^r$ とおくと $2^n-1=x^s-1=(x-1)(x^{s-1}+\dots+x+1)$ なので、$2^r-1$ は $m$ を割り、$1<2^r-1<2^n-1=m$ である（$r\ge2$ より $2^r-1\ge3$）。
$2^{m-1}\equiv1\pmod m$ であること：$m-1=2^n-2$ であり、仮定 $2^n\equiv2\pmod n$ から $n\mid m-1$ である。$m-1=nk$ と書く。$2^n=m+1\equiv1\pmod m$ なので、$2^{m-1}=(2^n)^k\equiv1\pmod m$ である。
$n$ が底 $2$ の擬素数なら $2^{n-1}\equiv1$ の両辺に $2$ を掛けて $2^n\equiv2\pmod n$ が成り立つ。$2^n-1>n$ は $n\ge1$ で正しい。よって $341$ から始めて $n_0=341$、$n_{k+1}=2^{n_k}-1$ と定めると、$n_0< n_1< n_2<\cdots$ はすべて底 $2$ の擬素数である。$\square$

合成数であること：$p$ は奇数なので $a+1$ は $a^p+1$ を割り、$\frac{a^p-1}{a-1}=1+a+\dots+a^{p-1}$ と $\frac{a^p+1}{a+1}=a^{p-1}-a^{p-2}+\dots-a+1$ はどちらも整数である。前者は $1+a\ge3$ 以上であり、後者は $a^p>a$ より $\frac{a^p+1}{a+1}>1$ である。よって $n$ は $1$ より大きい 2 つの整数の積で、合成数である。
$n-1$ が偶数であること：$n=1+a^2+a^4+\dots+a^{2(p-1)}$（$p$ 項の和）である。$a$ が偶数なら $n$ は奇数、$a$ が奇数なら $n$ は奇数 $p$ 個の和で奇数である。どちらの場合も $n-1$ は偶数である。
$p\mid n-1$ であること：$(a^2-1)(n-1)=a^{2p}-1-(a^2-1)=a^2\bigl(a^{2(p-1)}-1\bigr)$ である。$p\nmid a$ なので Fermat の小定理により $a^{p-1}\equiv1\pmod p$、よって $p\mid a^{2(p-1)}-1$ である。$p$ は $a^2-1$ を割らない素数なので、$p\mid n-1$ が従う。
$p$ は奇数なので、$2p\mid n-1$ である。$n-1=2pu$ と書く。$n(a^2-1)=a^{2p}-1$ だから $a^{2p}\equiv1\pmod n$ であり、$a^{n-1}=(a^{2p})^u\equiv1\pmod n$ が成り立つ。よって $n$ は底 $a$ の擬素数である。
$n=1+a^2+\dots+a^{2(p-1)}$ は $p$ について狭義に増加するので、異なる $p$ は異なる $n$ を与える。$a(a^2-1)$ は $0$ でない整数なので、それを割る素数は有限個しかなく、素数は無限にあるから、条件を満たす $p$ は無限にある。$\square$

$a$ の法 $p^2$ での位数を $d$ とすると、$d$ は $\varphi(p^2)=p(p-1)$ を割る（Eulerの定理(整数論)）。$a^{p^2-1}\equiv1\pmod{p^2}$ なら $d\mid p^2-1$ でもあるので、$d$ は $\gcd\bigl(p(p-1),\,(p-1)(p+1)\bigr)=(p-1)\gcd(p,p+1)=p-1$ を割り、$a^{p-1}\equiv1\pmod{p^2}$ である。逆に $a^{p-1}\equiv1\pmod{p^2}$ なら、$p-1\mid p^2-1$ なので $a^{p^2-1}\equiv1\pmod{p^2}$ である。$\square$

Euler–Jacobi 擬素数のとき：$\gcd(a,n)=1$ なので Jacobi記号 の値は $\pm1$ であり、$a^{(n-1)/2}\equiv\pm1$ の両辺を 2 乗して $a^{n-1}\equiv1\pmod n$ を得る。
強擬素数のとき：$a^t\equiv1$ なら $a^{n-1}=(a^t)^{2^s}\equiv1$ である。$a^{2^jt}\equiv-1$（$0\le j< s$）なら、$a^{2^{j+1}t}\equiv1$ であり、さらに $2^{s-j-1}$ 乗して $a^{n-1}=a^{2^st}\equiv1$ である。$\square$