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 {a₁, a₂, ... a_φ(n)} and a is an element of A, then aA={aa₁, a a₂, ... a a_φ(n)}=A in some order, so one of aa_i 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, p^k, or 2p^k (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 k²=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

{1², 2², 3², ..., ((p-1)/2)²}

These are distinct because if x²=y², then x=±y.  Proof: Suppose x²=y² (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 a=b^k, so a^(p-1)/2 = b^k ≡  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=b^k is the square of b^k/2.

("only if" direction) — suppose a ≡ b² (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)  ≡ b^2(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 root of a^(p-1) must be either 1 or -1 (mod p) because each quadratic residue has exactly two square roots, and by Euler's criterion the square root of a^(p-1) is not 1, so it has to be -1.

Internet references

 Wikipedia: Euler's criterion 

Related pages in this website

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]