is confirmed. If none do, then compositeness is confirmed. This is because the inverse of Proth's theorem is also true:

: If no a exists such that , and p is a Proth number, then p is composite.

The contrapositive of this statement is that if p is a Proth prime, such an a value is guaranteed to exist.

Indeed, if p is a Proth prime then we expect roughly half of all a-values to satisfy the congruence, in the general case. On the other hand, if the second condition is not met

1.Previous
3.Next