Proth's theorem

From Number
Revision as of 20:12, 2 January 2012 by Vipul (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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