# Proth's theorem

## Statement

### Existential version

Suppose  is a Proth number, i.e., a number of the form  where  and  is odd. Then,  is a prime number (and hence a Proth prime) if and only if there exists  such that:



Note that one direction of implication ( prime implying the existence of ) is true even for numbers that are not Proth numbers, so it is the other direction that is substantive.

### Particular element version

Suppose  is a Proth number, i.e., a number of the form  where  and  is odd. Pick an element  such that the Jacobi symbol  is -1. Then,  is a prime number (and hence a Proth prime) if and only if:



## Proof

Fill this in later