Statement Lemma If has non-trivial Fermat witness then atleast 1/2 of are Fermat witnesses. Proof Pick a non-trivial Fermat witness . Then for any such that it has a twin where Note as we are just multiplying by which is a bijection on integers mod we have that at most half of are not Fermat witnesses.