
Now I will present a wonderful fact about the coprimes to n  they form a group under multiplication mod n, which leads to:
If GCD(a,n) = 1 then a^{φ(n)} = 1 (mod n).
Proof: take a to be any positive integer coprime to n.
Let A be the set of numbers coprime to n: A = {a_{1}, a_{2}, a_{3}, ..., a_{φ(n)}}
Let aA be the product of the number, a, with each of the elements of A: aA = {aa_{1}, aa_{2}, aa_{3}, ..., aa_{φ(n)}}
No two elements of aA are congruent mod n (see lemma 1, below*), so their residues mod n must be {a_{1}, a_{2}, a_{3}, ..., a_{φ(n)}} in some order.
By equating the product of the numbers in set aA with the product of those in set A, mod n,
a^{φ(n)}a_{1}a_{2}a_{3}...a_{φ(n)} = a_{1}a_{2}a_{3}...a_{φ(n)} (mod n)
Since a_{1}a_{2}a_{3}...a_{φ(n)} is coprime to n, we can divide both sides by a_{1}a_{2}a_{3}...a_{φ(n)}, mod n, proving Euler's Totient Theorem.* Lemma 1: Why are no two elements of aA = {aa_{1}, aa_{2}, aa_{3}, ..., aa_{φ(n)}} congruent, mod n?
Suppose a is a number coprime to n, and b and c are two different numbers, also coprime to n, in the range [1,n1] and ab=ac, mod n.
Then abac=nk, where k is an integer.
a(bc)=nk, and since bc is smaller than n in absolute value, a must be larger than k in absolute value.
a and n have no factors in common, so ak, but a can't divide k, since a is larger than k, a contradiction.
If n is a positive integer, then n divides φ(2^{n}1)
Let's write m = 2^{n}1 for convenience.
Now 2^{n} = m+1, so 2^{n} = 1 (mod m), but no smaller (but still positive) power of 2 is equivalent to 1 (mod m).
So (2^{n})^{k} = 1 (mod m), which means 2^{kn} = 1 (mod m) for any integer, k.
2^{φ(m)} = 1 (mod m), by Euler's Totient Theorem.
We can divide φ(m) by n giving quotient q and remainder r such that φ(m) = qn+r, and so
2^{φ(m)} = 2^{qn+r} = 2^{qn} 2^{r} = 1 (mod m), and we know 2^{qn} = 1 (mod m), so 2^{r} = 1 (mod m), and 0 ≤ r < n, so r=0
Euler's criterion for determining whether a number is a quadratic residue (mod p), or in other words, if a number is the square of some other number (mod p).
Fermat's Theorems  Fermat's Little Theorem, in particular.
For any integer n, the sum of the totient values of each of its divisors equals n.
Number theory theorems, page 4: Totient.
Group  definition of a "group", which has properties closure, associativity, identity, and inverse.
The proof that primes of the form 4k+3 can be expressed as the sum of four squares uses Fermat's Little Theorem.
A bunch of Ring Theory theorems and definitions.
Proof that there is no solution to the Diophantine equation A^{4}+B^{4}=C^{2}, which means Fermat's last theorem is true
The webmaster and author of this Math Help site is Graeme McRae.