Skip to main content

Section 6.1 Euler's \(\varphi\)-function

Note that if \(p\) is a prime then, all nonzero elements in \(\mathbb{Z}_p\) have an inverse, since for \(0\neq a\in \mathbb{Z}_p, \gcd(a, p) = 1.\) Also if \(n\) is not a prime, then there is a divisor \(d\) of \(n,\) with \(1\lt d\lt n,\) so that \(\varphi(n)\leq n-2,\) thus we have proven our first result.

A stronger statement, which has yet to be proved, is a conjecture of D.H. Lehmer.

One of the implications is a consequence of the previous theorem, but the other is still wide open.

The number \(\varphi(p^k)\) is the number of integers in the set

\begin{equation*} A = \{1, 2,..., p^k\} \end{equation*}

which are relatively prime to \(p^k;\) that is, divisible by \(p.\) Since every \(p\)th number is divisible by \(p,\) there are \(\dfrac{p^k}{p}=p^{k-1}\) numbers in \(A\) that are divisible by \(p.\) Thus the number of integers in \(A\) that are relatively prime to \(p^k,\) are

\begin{equation*} \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=n\left(1-\dfrac{1}{p}\right). \end{equation*}

If \(ax + b \equiv a'x + b\pmod{n}\) where \(a, a' \in A,\) then we have that \(ax\equiv a'x\pmod{n}.\) Since \(\gcd(x, n) = 1,\) we may cancel \(x\) so that \(a \equiv a'\pmod{n}.\) Thus since \(A\) is a complete set of residues, \(Ax + b\) is a complete set of residues, provided \(\gcd(x, n) = 1.\)

Let \(m, n\in\mathbb{N}\) with \(\gcd(m, n) = 1.\) The result is trivial if \(m\) or \(n\) is \(1\) since \(\varphi(1) = 1,\) so suppose that \(m, n\gt 1.\) Let us arrange the \(mn\) integers \(1, 2,..., mn\) into an array with \(n\) rows and \(m\) columns, as such:

\begin{equation*} \begin{matrix} 1 \amp 2 \amp 3 \amp \cdots \amp m \\ m+1 \amp m+2 \amp m+3 \amp \cdots \amp 2m \\ \vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \\ (n-1)m+1 \amp (n-1)m+2 \amp (n-1)m+3 \amp \cdots \amp mn \end{matrix} \end{equation*}

These integers \(i\) form a complete set of residues \(\mod{mn},\) so \(\varphi(mn)\) of them are relatively prime to \(mn,\) or equivalently, \(\gcd(i, m) = \gcd(i, n) = 1.\) If we look that the columns we can see that all of the integers in a given column are equivalent \(\mod{m},\) thus exactly \(\varphi(m)\) of the columns consist of integers that are relatively prime to \(m,\) and the other columns consist of integers for which \(\gcd(i, m) \gt 1.\)

Now each column of integers that are relatively prime to \(m\) has the form

\begin{equation*} b, m + b, 2m + b,...,(n-1)m + b \end{equation*}

for some \(b.\) By the previous lemma this is a complete set of residues \(\mod{n},\) since \(\{0, 1, 2,..., n-1\}\) is and since \(\gcd(m, n) = 1.\) Therefore such a column contains \(\varphi(n)\) integers relatively prime to \(n,\) and so each of the \(\varphi(m)\) columns contains \(\varphi(n)\) integers relatively prime to \(n,\) so that the array contains \(\varphi(m)\varphi(n)\) integers \(i\) such that \(\gcd(i, m) = 1\) and \(\gcd(i, n) = 1.\) Thus \(\varphi(mn) = \varphi(m)\varphi(n).\)

Definition 6.1.6.

An arithmetic function \(f\) is said to be multiplicative if

\begin{equation*} f(mn) = f(m)f(n) \end{equation*}

whenever \(\gcd(m, n) = 1.\)

The Euler phi-function is multiplicative.

This all rests on the fact that \(\gcd(p_i^{k_i}, p_j^{k_j})=1\) for \(i\neq j.\) Because of this we have

\begin{align*} \varphi(n) \amp= \varphi(p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r})\\ \amp= \varphi(p_1^{k_1})\varphi(p_2^{k_2}\cdots p_r^{k_r})\\ \amp= \varphi(p_1^{k_1})\varphi(p_2^{k_2})\varphi(p_3^{k_3}\cdots p_r^{k_r})\\ \amp \vdots\\ \amp= \varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots \varphi(p_r^{k_r})\\ \amp= p_1^{k_1}\left(1-\frac{1}{p_1}\right)p_2^{k_2}\left(1-\frac{1}{p_2}\right)\cdots p_r^{k_r}\left(1-\frac{1}{p_r}\right)\\ \amp= n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right), \end{align*}

which is the desired result.

For \(n = 60 = 2^2\cdot 3\cdot 5,\) we have

\begin{equation*} \varphi(60) = 60\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=60\cdot\frac{1}{2}\frac{2}{3}\frac{4}{5}=16 \end{equation*}

One can also think of this example in terms of probabilities. Since the probability of a number being divisible by a prime \(p\) is \(\frac{1}{p},\) the probability of a number being coprime to \(p\) is \(1-\frac{1}{p}.\) So that relating this to each one of it's prime divisors, the above equation for \(\varphi(60)\) says that the probability that a number \(n\leq 60\) is coprime to \(60\) is \(\frac{16}{60}.\)

Remark 6.1.10.

The symbol

\begin{equation*} \sum_{d\vert n}f(n) \end{equation*}

is interpreted to mean, "Sum the values \(f(d)\) as \(d\) runs over all the positive divisors of the positive integer \(n.\)"

If \(n = 10,\) then

\begin{equation*} \sum_{d\vert 10}f(d) = f(1) + f(2) + f(5) + f(10). \end{equation*}

Let \(S = \{1, 2, 3,..., n\},\) and for each divisor \(d\) of \(n\) let

\begin{equation*} S_d = \{a\in S : \gcd(a, n) = n/d\}. \end{equation*}

Now if \(d \neq d'\) then \(S_d\cap S_{d'}= \emptyset,\) so that since each \(a\in S\) is in \(S_d\) for some \(d\vert n,\) we have

\begin{equation*} S =\bigcup_{d\vert n}S_d. \end{equation*}

Thus

\begin{equation*} \sum_{d\vert n}\#S_d = \#S = n. \end{equation*}

So it is enough to show that \(\#S_d = \varphi(d).\) Now

\begin{equation*} a\in S_d \hspace{2mm} \mathrm{if} \hspace{2mm} \mathrm{and} \hspace{2mm} \mathrm{only} \hspace{2mm} \mathrm{if} \hspace{2mm} a\in S \hspace{2mm} \mathrm{and} \hspace{2mm} \gcd(a, n) = n/d. \end{equation*}

If we define a \(a' = ad/n\) for each \(a,\) then \(a'\) is an integer since \(n/d = \gcd(a, n)\vert a.\) So dividing on the right-hand side by \(n/d\) we can rewrite the condition as

\begin{equation*} a\in S_d \hspace{2mm} \mathrm{if} \hspace{2mm} \mathrm{and} \hspace{2mm} \mathrm{only} \hspace{2mm} \mathrm{if} \hspace{2mm} a =\frac{n}{d}a' \hspace{2mm} \mathrm{where} \hspace{2mm} a'\in S, 1\leq a'\leq d, \gcd(a',d)=1. \end{equation*}

Thus \(\#S_d\) is the number of integers, between \(1\) and \(d,\) inclusive, which are relatively prime to \(d.\) This is the definition of \(\varphi(d),\) so \(\#S_d = \varphi(d),\) and we have \(n =\sum_{d\vert n}\varphi(d).\)

Section 6.1.1 Euler's Theorem

Definition 6.1.1.

Let \(a \in\mathbb{Z}_n\) be an invertible element, then \(a\) is called a unit to the modulus \(n.\) The subset set \(U_n\) of \(\mathbb{Z}_n\) is called the set of units to the modulus \(n.\)

This theorem aids us in proving Euler's generalization of Fermat's Little Theorem.

Let \(a\in \mathbb{N}\) and \(\gcd(a, n) = 1.\) Consider

\begin{equation*} U_n = \{u_1, u_2,..., u_{\varphi(n)}\}. \end{equation*}

Since \(\gcd(a, n) = 1, a \in U_n.\) So \(aU_n = U_n.\) Since the sets are equal, we know that the product of the elements are congruent mod \(n;\) that is,

\begin{equation*} au_1\cdot au_2 \cdots au_{\varphi(n)}\equiv u_1\cdot u_2\cdots u_{\varphi(n)}\pmod{n}, \end{equation*}

so that

\begin{equation*} a^{\varphi(n)}(u_1\cdot u_2\cdots u_{\varphi(n)}) ≡ u_1\cdot u_2 \cdots u_{\varphi(n)} \pmod{n}. \end{equation*}

Since we have \(\gcd(u_i,n)=1\) for each \(i,\) we know that

\begin{equation*} \gcd(u_1 \cdot u_2 \cdots u_{\varphi(n)},n)=1, \end{equation*}

and so we may cancel it from the congruence. So we have

\begin{equation*} a^{\varphi(n)}\equiv 1\pmod{n}, \end{equation*}

which is Euler's Theorem.