= Fermat witness
{c}
{title2=$a^{n-1}\not\equiv1\pmod n$}
A <Fermat witness> for an <integer> $n>1$ is a nonzero <residue class> represented by $1\leq a<n$ for which $a^{n-1}\not\equiv1\pmod n$. It proves that $n$ is a <composite number> by <Fermat's little theorem>. Here the definition includes <nonunits>; some conventions restrict <Fermat witnesses> to bases <coprime> to $n$. The <Fermat primality test> can first compute the <greatest common divisor>: if $1<\gcd(a,n)<n$, it already has a proper factor. A zero <residue class> is excluded. <Fermat's Test by Keith Conrad>[Keith Conrad, Fermat's Test, p. 2, Definition 2.4 and footnote 3 on the two witness conventions]{ref}
Back to article page
