Welcome guest
You're not logged in.
336 users online, thereof 0 logged in

From a necessary condition for an integer to be prime it follows that $n^{\frac{p-1}{2}}(p)\equiv\pm 1(p),$ since $n^{p-1}(p)\equiv 1(p)$ if $p\not\mid n$ and $p$ is a prime number. This motivates the following criterion, found by Leonhard Euler.

Proposition: Euler's Criterion For Quadratic Residues

Let $p > 2$ be a prime number and let $n\in\mathbb Z$ be a given integer. The Legendre symbol modulo $p$ can be calculated using the formula

$$\left(\frac np\right)(p)\equiv n^{\frac{p-1}{2}}(p).$$

In particular:

  • $n$ is a quadratic residue modulo $p$ if and only if $p\not\mid n$ and $n^{\frac{p-1}{2}}(p)\equiv 1(p),$
  • $n$ is a quadratic nonresidue modulo $p$ if and only if $p\not\mid n$ and $n^{\frac{p-1}{2}}(p)\equiv (p-1)(p)\equiv -1(p),$
  • otherwise, we have $p\mid n$ and $n^{\frac{p-1}{2}}(p)\equiv 0(p).$

| | | | | created: 2019-05-12 21:10:20 | modified: 2019-05-12 21:15:11 | by: bookofproofs | references: [1272]

1.Proof: (related to "Euler's Criterion For Quadratic Residues")

This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:


Bibliography (further reading)

[1272] Landau, Edmund: “Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.