|
|
|
This is a surprising factoid:
Σ φ(d) = n
d|n
Proof:
We will prove this sum-of-totients-of-divisors theorem by partitioning the set {1,2,3,...,n} into subsets according to each element's greatest common divisor with n. Each subset of {1,2,3,...,n} will be called Q(g), the set of all integers between 1 and n inclusive, such that gcd(x,n) = g. The Q(g) sets don't overlap, and their union is {1,2,3,...,n}, so the sum of the cardinality of the Q(g) sets is n. Also, there is a one-to-one correspondence between the elements of Q(g) and the "proper coprimes" of n/g, which completes the proof.
For example, if n=12, then the set {1,2,3,4,5,6,7,8,9,10,11,12} is partitioned into these sets:
Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}(All other Q(g) are empty sets)
These "Q" sets have the following three properties:
Q(g) is nonempty if and only if g divides n. (If g weren't a divisor of n, then it could never be the greatest common divisor of n and some other number).
If x belongs to Q(g) for a given g, then it can't belong to another Q(h) where h≠g, because it wouldn't be possible for gcd(x,n)=g and gcd(x,n)=h.
For all x between 1 and n inclusive, there exists a g such that gcd(x,n) = g
Put together, these three properties imply that the union of all the Q(g) sets (for each g a divisor of n), which are pairwise mutually exclusive, is the set {1,2,3,...,n}. And therefore, the sum of the cardinalities of each Q(g) equals n.
Now consider the set Q(g)/g, which is the set obtained by dividing each element of Q(g) by g. You know all the elements of Q(g)/g are integers, because g is a divisor of every element of Q(g). Let's look at our example, where n=12, again:
Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}Q(1)/1 = {1,5,7,11}
Q(2)/2 = {1,5}
Q(3)/3 = {1,3}
Q(4)/4 = {1,2}
Q(6)/6 = {1}
Q(12)/12 = {1}
Now we will show that Q(g)/g is the set of "proper coprimes" of n/g. By "proper coprimes" I mean positive numbers coprime to n that don't exceed n. Keep in mind that the set of proper coprimes of n/g contains φ(n/g) elements, so by showing that Q(g)/g is the set of proper coprimes of n/g, we will show that |Q(g)| = φ(n/g). Also, since the set {n/g | g divides n} is equal to the set {d | d divides n}, and the union of the Q(g) sets is {1,2,3,...,n}, the result will follow, and the proof will be complete.
Suppose x is an element of Q(g)/g. That means gx is an element of Q(g), so gcd(gx,n)=g, so gcd(x,n/g)=1, which means x is a coprime of n/g. gx does not exceed n, so x does not exceed n/g, which means x is a proper coprime of n/g.
Now suppose x is a proper coprime of n/g. gcd(x,n/g)=1, so gcd(gx,n)=g, so x is an element of Q(g)/g.
Therefore, |Q(g)| = φ(n/g). The proof is complete.
Now, let's take one more look at our example, filling in the part about φ(n/g):
Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}Q(1)/1 = {1,5,7,11}
Q(2)/2 = {1,5}
Q(3)/3 = {1,3}
Q(4)/4 = {1,2}
Q(6)/6 = {1}
Q(12)/12 = {1}φ(12/1) = φ(12) = 4
φ(12/2) = φ(6) = 2
φ(12/3) = φ(4) = 2
φ(12/4) = φ(3) = 2
φ(12/6) = φ(2) = 1
φ(12/12) = φ(1) = 1Union of Q(g):
{1,2,3,...,12}Sum of φ(d): 12
Fermat's Theorems -- Fermat's Little Theorem, in particular.
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
The webmaster and author of this Math Help site is Graeme McRae.