Euler's Totient Theorem
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 = {a1, a2, a3,
..., aφ(n)}
Let aA be the product of the number, a, with each of the elements of A: aA =
{aa1, aa2, aa3, ..., aaφ(n)}
No two elements of aA are congruent mod n (see lemma 1, below*), so their residues mod
n must
be {a1, a2, a3, ..., 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)a1a2a3...aφ(n) =
a1a2a3...aφ(n)
(mod n)
Since a1a2a3...aφ(n)
is coprime to n, we can divide both sides by a1a2a3...aφ(n),
mod n, proving
Euler's Totient Theorem.
* Lemma 1: Why are no two elements of aA = {aa1, aa2, aa3,
..., 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,n-1] and ab=ac, mod n.
Then ab-ac=nk, where k is an integer.
a(b-c)=nk, and since b-c 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 a|k, but a can't divide k, since a is
larger than k, a contradiction.
Other Totient Theorems
If n is a positive integer, then n divides φ(2n-1)
Let's write m = 2n-1 for convenience.
Now 2n = m+1, so 2n = 1 (mod m), but no smaller (but
still positive) power of 2 is equivalent to 1 (mod m).
So (2n)k = 1 (mod m), which means 2kn = 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) = 2qn+r = 2qn 2r = 1 (mod
m), and we know 2qn = 1 (mod m), so 2r = 1 (mod m), and 0
≤ r < n, so r=0
Internet References
Related Pages in this website
Squares.
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
A4+B4=C2, which means Fermat's last theorem
is true
|
