Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Euler's Criterion

Coprimes of n form a group

For a given n, the numbers not exceeding n that are coprime to n form a group under multiplication (mod n).  It's a group because it's closed (ab shares no factor with n if neither a nor b do), associative (multiplication is associative), an identity exists (1 is in the group because it's coprime to every number), and every element has an inverse (if A is the set of coprimes to n {a1, a2, ... aφ(n)} and a is an element of A, then aA={aa1, a a2, ... a aφ(n)}=A in some order, so one of aai must be the identity element).

That last statement may require additional explanation:  Suppose a,b,c are coprime to n and in the range [1,n-1], and ab=ac (mod n).  Then ab-ac=nk, where k is an integer.  a(b-c)=nk, and since |b-c|<n, |a|>|k|.  a and n have no factors in common, so a|k, and since |a|>|k|, k must be 0, so b=c.

Primitive Root

If n is of the form 1, 2, 4, pk, or 2pk (where p is prime), then the group of coprimes of n is cyclic, and so it has an element of order φ(n).  Such an element is called a primitive root (mod n). . . . . . .   (a proof of this factoid would be helpful.)

Quadratic Residue

A quadratic residue (mod p) is a square (mod p).  That is, a is a quadratic residue (mod p) if a number, k, exists such that k2=a.  A number that isn't a square is called a quadratic non-residue.  Normally, 0 is excluded from consideration as a quadratic residue or quadratic non-residue.  If p is prime, then there are exactly (p-1)/2 distinct quadratic residues (mod p), namely

{12, 22, 32, ..., ((p-1)/2)2}

These are distinct because if x2=y2, then x=±y.  Proof: Suppose x2=y2 (mod p).  Then (x-y)(x+y)=0 (mod p), so x-y is a factor of 0 or else x+y is a factor of 0 (mod p).  But the only factor of 0 is 0 (mod p), since p is prime.  So either x-y=0 or x+y=0, completing the proof.

In particular, note that each quadratic residue has exactly two square roots, which are negatives of one another.

Euler's Criterion

If p is an odd prime, and a is an integer coprime to p, then a is a quadratic residue (mod p) iff a(p-1)/2 ≡ 1 (mod p)

Proof:

("if" direction) — suppose a(p-1)/2 ≡ 1 (mod p).  Let b be a primitive root (mod p), then for some k,

a=bk, so a(p-1)/2 = bk(p-1)/2 ≡  1 (mod p).

Since b is a primitive root, the order of b is p-1, and so k(p-1)/2 must be a multiple of p-1, which means k/2 must be an integer, so a=bk is the square of bk/2.

("only if" direction) — suppose a ≡ b2 (mod p).  b(p-1) ≡ 1 (mod p) by Fermat's Little Theorem (or Euler's Totient Theorem).  So we have

1 ≡ b(p-1)  ≡ b2(p-1)/2 ≡ a(p-1)/2 (mod p).

Corollary to Proof of Euler's Criterion

If p is an odd prime, and a is an integer coprime to p, then a is a quadratic non-residue (mod p) iff a(p-1)/2 ≡ -1 (mod p)

Proof:

a(p-1)  ≡ 1 (mod p) by Fermat's Little Theorem, so the square roots of a(p-1) must be 1 and -1 (mod p), because each quadratic residue has exactly two square roots.  So if the square root of a(p-1) given by a(p-1)/2 is not 1, it must be -1.  The contrapositive of Euler's Criterion completes the proof.

Internet references

 Wikipedia: Euler's criterion 

Related pages in this website

Legendre symbol —  ( a

p
)  , where a is any integer, and p is an odd prime
Jacobi symbol —  ( a

n
)  , where a is any integer, and n is a positive integer greater than 2, an extension of the Legendre symbol.
Kronecker symbol —  ( a

n
)  , where a and n are any integers, an extension of the Jacobi symbol.

Fermat's Little Theorem 

Euler's Totient Theorem 

 

The webmaster and author of this Math Help site is Graeme McRae.