Existence of a Fermat witness if and only if composite

Statement

Lemma

A number has a Fermat witness if and only if is not prime.

Proof

If is prime from Fermat’s little theorem we know no Fermat witness exists.

If for then .

Suppose then we would have so is the inverse of .

Though by the existence modular multiplicative inverse lemma we know no such inverse exists for and therefore (mod ). So is a Fermat witness for .