= Passing-base fraction for the Fermat test
{title2=$\alpha_N=|\{a\in U(N):a^{N-1}=1\}|/\varphi(N)$}
Among the <units> $U(N)$ modulo $N$, the passing <residue classes> form the <kernel of a group homomorphism> $a\mapsto a^{N-1}$. If each trial samples independently and uniformly from those <units>, with replacement, the probability that $r$ trials all pass is $\alpha_N^r$. This statement assumes that sampling rule; it does not describe arbitrary or dependent choices of bases.
For $341=11\cdot31$, the <Chinese remainder theorem> identifies the <unit group> with cyclic groups of orders $10$ and $30$. The number of solutions of $x^{340}=1$ is $\gcd(340,10)\gcd(340,30)=100$, among $\varphi(341)=300$ <units>. Thus $\alpha_{341}=1/3$. The <Carmichael numbers> $561$ and $1105$ have passing fractions $320/320$ and $768/768$, so their conditional false-pass probability remains one regardless of the number of independent trials.
\Image[/fermat-test-all-base-outcome-counts.png]
{title=All nonzero bases: coprime passes, coprime witnesses and factor-revealing <nonunits>}
{description=Exact enumeration for four stipulated moduli. A <greatest common divisor> check separates <nonunits> before <modular exponentiation>. Counts are finite arithmetic results, not measured rates or a universal bound for a <primality test>.}
The <Fermat test example> uses selected bases; this diagram exhausts the specified finite base sets. Both make the same logical distinction: an exponent witness can prove compositeness, whereas a passing result needs further justification before it can support a claim of primality.
Back to article page
