Euler's criterion - Revision history

Vipul: /* Related facts */

2012-01-02T20:19:25Z

Related facts

← Older revision		Revision as of 20:19, 2 January 2012
Line 27:		Line 27:
	===Primality tests===		===Primality tests===

			* [[Euler primality test]], which is not conclusive and can be fooled by [[Euler pseudoprime]]s to the given base
	* [[Euler-Jacobi primality test]], which is not conclusive and can be fooled by [[Euler-Jacobi pseudoprime]]s to the given base		* [[Euler-Jacobi primality test]], which is not conclusive and can be fooled by [[Euler-Jacobi pseudoprime]]s to the given base

Vipul: /* Related facts */

2012-01-02T20:18:49Z

Related facts

← Older revision		Revision as of 20:18, 2 January 2012
Line 24:		Line 24:
	* [[Congruence condition for two to be a quadratic residue]]		* [[Congruence condition for two to be a quadratic residue]]
	* [[Quadratic reciprocity]]		* [[Quadratic reciprocity]]

			===Primality tests===

			* [[Euler-Jacobi primality test]], which is not conclusive and can be fooled by [[Euler-Jacobi pseudoprime]]s to the given base

Vipul at 20:17, 2 January 2012

2012-01-02T20:17:49Z

← Older revision		Revision as of 20:17, 2 January 2012
Line 16:		Line 16:

	where the expression on the right side is the [[Legendre symbol]], defined to be <math>+1</math> for a [[quadratic residue]] and <math>-1</math> for a [[quadratic nonresidue]]. Note that the Legendre symbol is the restriction to primes of the [[Jacobi symbol]].		where the expression on the right side is the [[Legendre symbol]], defined to be <math>+1</math> for a [[quadratic residue]] and <math>-1</math> for a [[quadratic nonresidue]]. Note that the Legendre symbol is the restriction to primes of the [[Jacobi symbol]].

			==Related facts==

			===Applications===

			* [[Congruence condition for minus one to be a quadratic residue]]
			* [[Congruence condition for two to be a quadratic residue]]
			* [[Quadratic reciprocity]]

Vipul: Created page with "==Statement== ===In terms of quadratic residues and nonresidues=== Suppose $p$ is an odd prime number. Consider an integer $a$ that is not zero mod..."

2012-01-02T20:16:38Z

Created page with "==Statement== ===In terms of quadratic residues and nonresidues=== Suppose <math>p</math> is an odd prime number. Consider an integer <math>a</math> that is not zero mod..."

New page

==Statement==

===In terms of quadratic residues and nonresidues===

Suppose <math>p</math> is an odd [[prime number]]. Consider an integer <math>a</math> that is not zero mod <math>p</math>. Then:

* <math>a^{(p-1)/2}</math> is congruent to either 1 or -1 mod <math>p</math>.
* <math>a^{(p-1)/2}</math> is congruent to 1 mod <math>p</math> if and only if <math>a</math> is a [[fact about::quadratic residue]] mod <math>p</math>.
* <math>a^{(p-1)/2}</math> is congruent to -1 mod <math>p</math> if and only if <math>a</math> is a [[fact about::quadratic nonresidue]] mod <math>p</math>.

===In terms of Legendre symbol===

Suppose <math>p</math> is an odd [[prime number]]. Consider an integer <math>a</math> that is not zero mod <math>p</math>. Then:

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

where the expression on the right side is the [[Legendre symbol]], defined to be <math>+1</math> for a [[quadratic residue]] and <math>-1</math> for a [[quadratic nonresidue]]. Note that the Legendre symbol is the restriction to primes of the [[Jacobi symbol]].

Euler's criterion - Revision history

Vipul: /* Related facts */

Vipul: /* Related facts */

Vipul at 20:17, 2 January 2012

Vipul: Created page with "==Statement== ===In terms of quadratic residues and nonresidues=== Suppose p is an odd prime number. Consider an integer a that is not zero mod..."

Vipul: Created page with "==Statement== ===In terms of quadratic residues and nonresidues=== Suppose $p$ is an odd prime number. Consider an integer $a$ that is not zero mod..."