Proth's theorem

Proth's theorem

In mathematics, Proth's theorem in number theory is a primality test for Proth numbers.

It states that if "p" is a Proth number, of the form "k"2"n" + 1 with "k" odd and "k" < 2"n", then if for some integer "a",

:a^{(p-1)/2}equiv -1 pmod{p},!

then "p" is prime (called a Proth prime). This is a practical test because if "p" is prime, any chosen "a" has about a 50 percent chance of working.

Numerical examples

Examples of the theorem include:

* for "p" = 3, 21 + 1 = 3 is divisible by 3, so 3 is prime.
* for "p" = 5, 32 + 1 = 10 is divisible by 5, so 5 is prime.
* for "p" = 13, 56 + 1 = 15626 is divisible by 13, so 13 is prime.
* for "p" = 9, which is not prime, there is no "a" such that "a"4 + 1 is divisible by 9.

The first Proth primes are OEIS|id=A080076::3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153

As of 2007, the largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust. It has 3918990 digits and is the largest known prime which is not a Mersenne prime. [http://primes.utm.edu/top20/page.php?id=3]

History

François Proth (1852 - 1879) published the theorem around 1878.

ee also

*Sierpinski number

External links

*MathWorld|urlname=ProthsTheorem|title=Proth's Theorem


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Proth number — In number theory, a Proth number is a number of the form :P=k, 2^n+1 where k is odd, n is a positive integer, and 2 n > k . Proth numbers are named after the mathematician François Proth.If a Proth number is prime, it is called Proth prime: Proth …   Wikipedia

  • François Proth — (1852 1879) was a French self taught mathematician farmer who lived near Verdun, France. He stated four primality related theorems, the most famous of which is Proth s theorem, published around 1878. Proth numbers, related to the above mentioned… …   Wikipedia

  • Fermat number — In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form:F {n} = 2^{2^{ overset{n} {} + 1where n is a nonnegative integer. The first nine Fermat numbers are OEIS|id=A000215:As of|2008 …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Число Прота — В теории чисел число Прота, названное в честь математика Франсуа Прота (англ.), представляет собой число вида , где является нечётным положительным целым числом и n  положительное целое число, причём . Без последнего условия все… …   Википедия

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Теорема Прота — В теории чисел теорема Прота является тестом простоты для чисел Прота. Содержание 1 Формулировка 2 Тестирование чисел Прота на простоту …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”