Math 2.0

Number theory Quadratic residues and reciprocity Theorem

Euler's criterion

Builds on Legendre symbolFermat's little theorem

Statement

Let pp be an odd prime and let aa be an integer. Then a(p−1)/2≡(ap)(modp),a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p, where (ap)\left(\frac{a}{p}\right) is the Legendre symbol.

Remarks

So for p∤ap \nmid a, the integer aa is a quadratic residue modulo pp if and only if a(p−1)/2≡1(modp)a^{(p-1)/2} \equiv 1 \pmod p. For example, 33=27≡−1(mod7)3^3 = 27 \equiv -1 \pmod 7, so 33 is a quadratic nonresidue modulo 77. The proof uses Fermat's little theorem: x=a(p−1)/2x = a^{(p-1)/2} satisfies x2≡1x^2 \equiv 1, so x≡±1(modp)x \equiv \pm 1 \pmod p. A consequence is the multiplicativity of the Legendre symbol.

History

Leonhard Euler found the criterion.

Reading path

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

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionPrime number, definition, no evidence levelPrime numberdefinitionQuadratic residue, definition, no evidence levelQuadratic residuedefinitionFermat's little theorem, statement, no evidence levelFermat's little theor…statementLegendre symbol, definition, no evidence levelLegendre symboldefinitionEuler's criterion, statement, no evidence levelEuler's criterionstatement
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. Congruence modulo n definition
  3. Prime number definition
  4. Quadratic residue definition
  5. Fermat's little theorem statement
  6. Legendre symbol definition
  7. Euler's criterion statement

Where this leads

12 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Euler%27s_criterion, lead section
About this page
Tag0M7DEDKSYB
URIm2://0M7DEDKSYB
Kindstatement, theorem
WritingW1 stated
MSC11A15
StatusThis copy of the site has no build data. Run m2 status 0M7DEDKSYB.
UsesLegendre symbol, Fermat's little theorem
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

Used by