Vipul: Created page with "==Statement== ===Existential version=== Suppose $p$ is a fact about::Proth number, i.e., a number of the form $k \cdot 2^n +1$ where $k < 2^n..."$

2012-01-02T20:12:53Z

Created page with "==Statement== ===Existential version=== Suppose <math>p</math> is a fact about::Proth number, i.e., a number of the form <math>k \cdot 2^n +1</math> where <math>k < 2^n..."

New page

==Statement==

===Existential version===

Suppose <math>p</math> is a [[fact about::Proth number]], i.e., a number of the form <math>k \cdot 2^n +1</math> where <math>k < 2^n</math> and <math>k</math> is odd. Then, <math>p</math> is a [[prime number]] (and hence a [[Proth prime]]) if and only if there exists <math>a</math> such that:

<math>a^{(p-1)/2} \equiv -1 \pmod p</math>

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

===Particular element version===

Suppose <math>p</math> is a [[fact about::Proth number]], i.e., a number of the form <math>k \cdot 2^n +1</math> where <math>k < 2^n</math> and <math>k</math> is odd. Pick an element <math>a</math> such that the [[Jacobi symbol]] <math>\left(\frac{a}{p}\right)</math> is -1. Then, <math>p</math> is a [[prime number]] (and hence a [[Proth prime]]) if and only if:

<math>a^{(p-1)/2} \equiv -1 \pmod p</math>

==Related facts==

* [[Pepin's primality test]]: This is a version for [[Fermat number]]s. For Fermat numbers, we can choose <math>a = 3</math>.

==Proof==

{{fillin}}

Proth's theorem - Revision history

Vipul: Created page with "==Statement== ===Existential version=== Suppose p is a fact about::Proth number, i.e., a number of the form k \cdot 2^n +1 where k < 2^n..."

Vipul: Created page with "==Statement== ===Existential version=== Suppose $p$ is a fact about::Proth number, i.e., a number of the form $k \cdot 2^n +1$ where $k < 2^n..."$