Fermat witness ($a^{n-1}\not\equiv 1(\mathrm{mod}n)$)

A Fermat witness for an integer $n>1$ is a nonzero residue class represented by $1\le a<n$ for which $a^{n-1}\not\equiv 1(\mathrm{mod}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. ^[ref]