Proth's theorem

From Number
Jump to: navigation, search

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:

Related facts

Proof

Fill this in later