
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_{1}, a_{2}, ... a_{φ(n)}} and a is an element of A, then aA={aa_{1}, a a_{2}, ... 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,n1], and ab=ac (mod n). Then abac=nk, where k is an integer. a(bc)=nk, and since bc<n, a>k. a and n have no factors in common, so ak, and since a>k, k must be 0, so b=c.
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.)
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^{2}=a. A number that isn't a square is called a quadratic nonresidue. Normally, 0 is excluded from consideration as a quadratic residue or quadratic nonresidue. If p is prime, then there are exactly (p1)/2 distinct quadratic residues (mod p), namely
{1^{2}, 2^{2}, 3^{2}, ..., ((p1)/2)^{2}}
These are distinct because if x^{2}=y^{2}, then x=±y. Proof: Suppose x^{2}=y^{2} (mod p). Then (xy)(x+y)=0 (mod p), so xy 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 xy=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.
If p is an odd prime, and a is an integer coprime to p, then a is a quadratic residue (mod p) iff a^{(p1)/2} ≡ 1 (mod p)
Proof:
("if" direction) — suppose a^{(p1)/2} ≡ 1 (mod p). Let b be a primitive root (mod p), then for some k,
a=b^{k}, so a^{(p1)/2} = b^{k}^{(p1)/2} ≡ 1 (mod p).
Since b is a primitive root, the order of b is p1, and so k(p1)/2 must be a multiple of p1, 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^{2} (mod p). b^{(p1)} ≡ 1 (mod p) by Fermat's Little Theorem (or Euler's Totient Theorem). So we have
1 ≡ b^{(p1)} ≡ b^{2(p1)/2} ≡ a^{(p1)/2} (mod p).
If p is an odd prime, and a is an integer coprime to p, then a is a quadratic nonresidue (mod p) iff a^{(p1)/2} ≡ 1 (mod p)
Proof:
a^{(p1)} ≡ 1 (mod p) by Fermat's Little Theorem, so the square roots of a^{(p1)} must be 1 and 1 (mod p), because each quadratic residue has exactly two square roots. So if the square root of a^{(p1)} given by a^{(p1)/2} is not 1, it must be 1. The contrapositive of Euler's Criterion completes the proof.
Wikipedia: Euler's criterion
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.
The webmaster and author of this Math Help site is Graeme McRae.