Math 2.0

Number theory Theorem

Pépin's test

Builds on Fermat numberCongruence modulo n

Statement

Let nn be a positive integer and let Fn=22n+1F_n = 2^{2^n} + 1 be the Fermat number. Then FnF_n is prime if and only if 3(Fn−1)/2≡−1(modFn).3^{(F_n - 1)/2} \equiv -1 \pmod{F_n}.

Remarks

For example, F1=5F_1 = 5 and 32=9≡−1(mod5)3^2 = 9 \equiv -1 \pmod 5. The power can be computed by 2n−12^n - 1 squarings with modular exponentiation. The "only if" part follows from Euler's criterion and quadratic reciprocity, since 33 is a nonresidue modulo FnF_n.

History

The test is named after Théophile Pépin.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionFermat number, definition, no evidence levelFermat numberdefinitionCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionPépin's test, statement, no evidence levelPépin's teststatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Fermat number definition
  3. Congruence modulo n definition
  4. Pépin's test statement

Further reading

  1. Web https://en.wikipedia.org/wiki/P%C3%A9pin%27s_test, Description of the test
About this page
Tag07HXA8KV6F
URIm2://07HXA8KV6F
Kindstatement, theorem
WritingW1 stated
MSC11Y11
StatusThis copy of the site has no build data. Run m2 status 07HXA8KV6F.
UsesFermat number, Congruence modulo n
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.