Euler's totient function (Fine!)

Introduction

Euler's Totient Function, $\phi$ (called Phi), is of significant importance in Number Theory.

$\phi(n)$ denotes the number of non-negative integers $x's<n$ such that $(x,n)=1$. In other words, it counts the number of elements in the residue class of $n$ such that those elements are co-prime to $n$.

For example, the residue class of $8$ is $\{0,1,2,3,4,5,6,7\}$. Among these $8$ numbers, $4$ of them, including $1,3,5,7$, are co-prime to $8$. So $\phi(8) = 4$.

Multiplicative Property of $\phi$

One powerful property of $\phi$ is that this function is multiplicative. That is $\phi(a,b) = \phi(a)\phi(b)$ for $(a,b)=1$. The condition $(a,b)=1$ is important, for this would not work for any random $a,b$.

In Introduction to Theory of Numbers (G.H. Hardy, E.M. Wright), a proof is provided. We will outline that proof here.

First, we prove that the multiplicative property implies that any unique pair from the residue classes of $x$ and $y$ uniquely determines a remainder mod $xy$. We claim that if $a,b$ run through the residue classes of $x,y$ respectively, $(x,y)=1$ then $ay+bx$ run through the residue class of $mn$. That is to prove the uniqueness of $ay+bx$.

Assume, on the contrary, that there exist $a,b,a',b'$ such that $ay+bx \equiv r \pmod{xy}$, and $a'y+b'x \equiv r \pmod{xy}$. This implies $ay + bx \equiv a'y + b'x \pmod{xy}$. Therefore, $(a-a')y+(b-b')x \equiv 0 \pmod{xy}$. $xy| (a-a')y+(b-b')x$ and $x| (b-b')x$ force $x|(a-a')y$. Because $(x,y)=1$, $x|(a-a')$. That is $a \equiv a' \pmod{x}$. Similarly, we prove that $b \equiv b' \pmod{y}$. Thus, we have proved that any unique pair of $(a,b)$ determines a unique remainder mod $xy$. Specifically, $ay+bx$ runs through the residue class of $xy$, as $a$ run through class $x$ and $b$ run through class $y$. Note that the number of elements in class $x$ is $x$, class $y$ is $y$ and class $xy$ is $xy$. So $ay+bx$ determines all members of residue class $xy$.

Now, we form the reduced class of $xy$ by picking out co-prime members from the "complete" residue class. The $\phi(xy)$ function then counts the number of members in the reduced class.

We will prove that if we restrict $a,b$ to run only through the reduced classes of $x$ and $y$, then $ay+bx$ run through the reduced class of $xy$. That is $(ay+bx,xy)=1 \iff (ay+bx,x)=1$ & $(ay+bx,y)=1$
$\iff (ay,x)=1$ & $(bx,y)=1 \iff (a,x)=1$ & $(b,y)=1$.
And the last assertion is true since we let $a,b$ run through the reduced classes of $x,y$. This completes the proof.

How to calculate $\phi$

First, we quickly note that $\phi(p) = p-1$, since that is the definition of prime number. The only remainder that is not co-prime to $p$ is $0$.

We prove that $\phi(p^c)=p^c-p^{c-1}$. First, note that $p^c$ is precisely the number of all remainders mod $p$. Then, $p^{c-1}$ must be the number of remainders that share some factor with $p$. Call such number $x$. Because $p$ is prime and cannot be divided further, if $(x,p)=d>1$ then $d$ must be of the form $kp$. Now, note that $k$ can run through $\{0,1,2,...,p^{c-1}\}$, and this completes the proof.

We will take advantage of the multiplicative property along with the property above to calculate $\phi(m)$ for arbitrary $m$. By the prime factorization theorem (Fundamental Theorem of Arithmetic), $m = \prod p^c$, where $\prod$ symbol denotes the product. For example, $72=2^33^2$. So $\phi(m) = \prod \phi(p^c) = \prod (p^c-p^{c-1}) = \prod p^c(1-\displaystyle\frac{1}{p} = m(\prod 1-\displaystyle\frac{1}{p})$

As an example,
$\phi(72) = \phi(2^3)\phi(3^2) = (2^3-2^2)(3^2-3)= 2^3(1-\displaystyle\frac{1}{2})3^2(1-\displaystyle\frac{1}{3})$
$=72(1-\displaystyle\frac{1}{2})(1-\displaystyle\frac{1}{3})=24$

More outrageous claims about $\phi$

Generalization of Fermat's Theorem

In Linear Congruence and Fermat Theorem, we prove:
$a^{p-1} \equiv 1 \pmod{p}$ with $0<a<p$

Now we generalize it to an even stronger statement:

$a^{\phi(m)} \equiv 1 \pmod{m}$ with $m$ not necessarily being a prime number, and $(a,m)=1$.

Call the reduced class of $m$, $\mathbb{Z}_m$. It is easy to see that $a\mathbb{Z}_m$ is also a reduced class. This is because for $x \in \mathbb{Z}_m$, it is evident that $(ax,m)=1$. This easily proves the generalization.

Sum of $\phi$ functions of factors

We will prove a rather surprising result, $\sum_{d|m} \phi(d) = m$

Compute $\phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(6)+\phi(12) (*)$ to convince yourself that it is indeed equal to $12$ (note that $\phi(1)$ is defined to be equal to $1$).

Now, we will prove the assertion. We know that if $m= \prod p^c$, one way to calculate the sum of all positive factors of $m$ is to expand out the product $ \displaystyle\prod (\sum_{i=0}^{c} p^i)$.

For example, sum of all positive factors of $12$, let call it $S(12)$, is $S(12)=(1+2+2^2)(1+3)=1+2+3+4+6+12$. Now instead of applying the $\phi$ functions to each factor when the sum has been expanded out as in $(*)$, we apply the function like this $(\phi(1)+\phi(2)+\phi(2^2))(\phi(1)+\phi(3)) (**)$. We see that the effect of applying the function as such is not different from $(*)$.

Now $(\phi(1)+\phi(2^2)+\phi(2^2))= (1+ (2^2-1))=2^2$. And similarly, $(\phi(1) + \phi(3)) = 3$. So $(**)=2^23=12$. In general, $\displaystyle\sum_{i=0}^{c} \phi(p^i) = \sum_{i=0}^{c} p^{c}-p^{c-1} = p^c$.

And thus $\displaystyle\prod (\sum_{i=0}^{c} \phi(p^i)) = \prod p^c = m$.

References:

Introduction to Theory of Numbers (G.H. Hardy, E.M. Wright)
Higher Arithmetic (H.Davenport)
Stanford Number Theory Handout (Dana Paquin)