Euler's Totient Function

One of the most important function in number theory is the Euler's function $\phi(n)$, which gives the number of congruence classes $[a] \in \mathbb{Z}_n$ which have an inverse under multiplication.

Fermat's Little Theorem states  that if $p$ is prime then $a^{p-1} \equiv 1 \pmod{p}$ for all integers $a \not \equiv 0 \pmod {p}$. We would like a similar result for composite moduli, but if we simply replace $p$ with a composite integer $n$, then the resulting congruence $a^{n-1} \equiv 1 \pmod {n}$ is not generally true: if $gcd(a,n) = d > 1$ then any positive power of $a$ is divisible by $d$, so it cannot be congruent to $1 \pmod {n}$. This suggests that we should restrict attention to those integers $a$ coprime to $n$, but even then the congruence can fail: if $n = 4$ and $a = 3$ then $a^{4-1}=3^3 = 27 \not \equiv 1 \pmod {4}$, for example. We need a different exponent $e(n)$ such that $a^{e(n)} \equiv 1 \pmod {n}$ for all $a$ coprime to $n$. The simplest function with this property turns out to be Euler's  function $\phi(n)$.

Units

A multiplicative inverse for a class $[a] \in Z_n$, is a class $[b] \in Z_n$, such that $[e][b] = [1]$. A class $[a] \in Z_n$, is a unit if it has a multiplicative inverse in $Z_n$.(In this case, we sometimes say that the integer $a$ is a unit $\pmod {n}$, meaning that $ab \equiv 1 \pmod {n}$ for some integer $b$.

Lemma: $[a]$ is a unit in $Z_n$, if and only if $gcd(a,n) = 1$.

Proof: If $[a]$ is a unit then $ab = 1+ qn$ for some integers $b$ and $q$; any common factor of  $a$ and $n$ would therefore divide 1, so $gcd(a,n) = 1$. Conversely, if $gcd(a,n) = 1$ then $1 = au + nv $ for some $u$ and $v$ , so $[u]$ is a multiplicative inverse of $[a]$ in $\pmod{n}$

Example:

We let $U_n$, denote the set of units in $Z_n$, Thus $U_8 = \{[1], [3], [5], [7]\}$ and $U_9 =\{[1], [2], [4], [5], [7], [8]\}$. 

Theorem:For each integer $n > 1$, the set $U_n$, forms a group under multiplication $\pmod {n}$, with identity element $[1]$.

Euler's Function

We define $\phi(n)=|U_n|$, the number of units in $Z_n$; by the above Lemma  this is the number of integers $a = 1,2,\ldots, n$ such that $gcd(a,n) = 1$. This function $\phi$ is called Euler's function(Euler's totient function).

For small $n$, its values are as follows:

$$n \: \: \: \: \: \: \quad= 1,2,3,4,5,6,7,8,9,10,11,12,\ldots$$

$$\phi(n) =1,1,2,2,4,2,6,4,6, 4, 10, 4, \ldots $$

We define a subset $R$ of $Z$ to be a reduced set of residues $\pmod {n}$ if it contains one element from each of the $\phi(n)$ congruence classes in $U_n$; For instance, $\{1,3,5,7\}$ and $\{\pm 1,\pm 3\}$ are both reduced sets of residues $\pmod {8}$.

In 1760. Euler proved the following generalisation of Fermat's Little Theorem, often called Euler's Theorem.

Theorem:

If $gcd(a,n) = 1$ then $a^{\phi(n)} = 1 \pmod {n}$.

Proof: 

The above Equation is true if $n$ is prime, because in that case,$\phi(n)=n-1$ and Fermat’s theorem holds. However, it also holds for any integer $n$. Recall that $\phi(n)$ is the number of positive integers less than $n$ that are relatively prime to $n$ .Consider the set of such integers, labeled as

$$R=\{x_1,x_2,\ldots,x_{\phi(n)}\}$$

That is, each element  $x_i$ of $R$ is a unique positive integer less than $n$ with $gcd(x_i,n)=1$.Now multiply each element by $a$ modulo $n$:

$$S=\{ax_1 \pmod{n},ax_2 \pmod{n},\ldots,ax_{\phi(n)} \pmod{n}\}$$

The set $S$ is a permutation of  $R$, by the following line of reasoning:

1. Because $a$ is relatively prime to $n$ and $x_i$ is relatively prime to $n$ , $ax_i$ must also be relatively prime to $n$. Thus, all the members of $S$ are integers that are less than $n$ and that are relatively prime to $n$.

2.There are no duplicates in $S$.If $ax_i \pmod{n} = ax_j \pmod{n}$, then $x_i = x_j$

Note:Fermat's little theorem is a special case of this result.if $n$ is a prime $p$, then the units in $\mathbb{Z}_p$ are the classes $[1],[2],\ldots,[p-1]$, so $\phi(p)=p-1$ and hence $a^{p-1} \equiv 1 \pmod{p}$

Example: Lets consider $n=12$,$U_12=\{1,5,7,11\}$ and $\phi(12)=4$.

$1^4 \equiv 1\pmod{12}$

$5^4 \equiv 1\pmod{12}$

$7^4 \equiv (-5)^4 \equiv 1 \pmod{12}$

$11^4 \equiv (-1)^4 \equiv 1 \pmod{12}$

So $a^4 \equiv 1 \pmod{12}$ for each $a$ coprime to $12$.

We aim now to find a general formula for $\phi(n)$. We have just seen that $\phi(p) = p-1$ for all primes $p$, and a simple extension of this deals with the case where $n$ is a prime-power:

Lemma 

If $n = p^e$  where $p$ is prime, then

Example:

$\phi(8)=\phi(2^3)=8(1-1/2)=4$

The set $U_8=\{1,3,5,7\}$

Theorem:

 If $m$ and $n$ are coprime $\phi(mn)=\phi(m).\phi(n)$

Proof:

To see that $\phi(n)=\phi(p) \times \phi(q)$, consider that the set of positive integers less than $n$ is the set $[1,2,\ldots,(pq-1)]$. The integers in this set that are not relatively prime to $n$ are the set 

$\{p,2p,\ldots,(q-1)p\}$ and the set $\{q,2q,\ldots,(p-1)q\}$. Accordingly

$$\phi(n)=(pq-1)-[(q-1)+(p-1)]$$

$$\phi(n)=pq-p-q+1$$

$$\phi(n)=(p-1) \times (q-1)$$

$$\phi(n)=\phi(p) \times \phi(q)$$

An alternate Proof

Example:

$\phi(12)=\phi(4)*\phi(3)=2*2=4$

The set $U_{12}=\{1,5,7,11\}$

Corollary

Example:

$\phi(60)=\phi(2^2 \times 3 \times 5)=\phi(2^2).\phi(3).\phi(5)=4.(1-1/2).2.4=16$

$\phi(60)=60(1-1/2)(1-1/3)(1-1/5)=(60*2*4)/(2*3*5)=16$

The units  $U_{60}=\{1, 7, 11, 13, 17, 19, 23, 29,31, 37, 41, 43, 47, 49, 53, 59\}$

Theorem (Euler's Phi Function Summation Formula). 

Let $d_1, d_2, \ldots , d_r$ be the divisors of $n$. Then 

$$\phi(d_1)+\phi(d_2)+\ldots+\phi(d_r)=n$$

Example:

we take all the divisors of $n$, apply Euler's phi function to each divisor, add the values of Euler's phi function and see what we get.

We start with an example, say $n = 15$. The divisors of 15 are 1, 3, 5, and 15.

We first evaluate Euler's phi function at the numbers 1, 3, 5, and 15,

$\phi(1) = 1, \phi(3) = 2, \phi(5) = 4, \phi(15) = 8.$

Next we add the values to get

$\phi(1) + \phi(3) + \phi(5) + \phi(15) = 1 + 2 + 4 + 8 = 15.$

Euler's Totient Function has following properties

1.$\phi(mn)=\phi(m).\phi(n),\quad if \: gcd(m,n)=1$

2.$\phi(p^e)=p^e-p^{e-1}$ for prime $p$ and $e \ge 1$

3.$a|b$ implies $\phi(a)|\phi(b)$

4.$\phi(n)$ is even for $n \ge 3$.More over if $n$ has $r$ distinct odd prime factors , then $2^r|\phi(n)$

Application of Euler's Function

We can make use of Euler's Theorem $a^{\phi(n)} \equiv 1$ to simplify congruences $\pmod{n}$ when $n$ is composite.Euler's Theorem is useful in solving large power congruences because it reduces the computation of large powers modulo $n$ to powers modulo $\phi(n)$, which can be significantly smaller than $n$, if $n$ has many prime factors. This makes it more efficient to compute and work with.

Example:

Let's demonstrate Euler's Theorem with an example.
Suppose we want to compute $7^{100} \pmod{15}$

First, we need to compute $\phi(15)$, which is the number of integers coprime to 15.

Since 15 can be factored into $3×5$ and both 3 and 5 are primes, $\phi(15)=\phi(3) \times \phi(5)=(3−1)×(5−1)=2×4=8$.

Now, applying Euler's Theorem, we have:
$$7^{\phi(15)}≡7^8≡1 \pmod{15}$$
So, $7^{100}$ is congruent to $7^{8×12+4}\pmod {15}$.

$7^{100}≡(7^8)^{12} ×7^ 4≡1^{12}×7^4≡1×2401≡1×1≡1 \pmod{15}$

Thus, $7^{100}≡1 \mod{15}$

Euler's Theorem allows us to efficiently compute the congruence of large powers, reducing the computation modulo $\phi(n)$ rather than $n$.

Example:

Find the last two digits of $3^{1492}$ using Euler's theorem.

Here we need to compute $3^{1492} \pmod{100}$

First, we need to find $\phi(100)$, which is the count of positive integers less than 100 that are coprime to 100.

 so $\phi(100)=100(1-1/2)(1-1/5)=(100.1.4)/(2.5)=40$.

Now, according to Euler's theorem, if $a$ and $n$ are coprime, then $a^{\phi(n)}≡1 \pmod{n}$

Therefore, $3^{40}≡1 \pmod{100}$

Next, we'll reduce the exponent 1492

$1492≡12 \pmod{40}$

So, we have:

$1492=40×37+12$

$3^{1492}=(3^{40})^{37}×3^{12}$

$=1^{37}×3^{12} \pmod{100}$

$=3^{12} \pmod{100}$

Now, we can directly compute $3^{12}$

$3^{12}=531441$

Taking only the last two digits, we get 41.

Therefore, the last two digits of $3^{1492}$ are 41.

Example Python code for finding  Euler's Phi function

from math import gcd

def phi(n):

   relprime = 0        

    for k in range(1, n + 1):

        if gcd(n, k) == 1:

            relprime+= 1

    return relprime

print(phi(60))

output:

16

# import totient() method from sympy 

from sympy.ntheory import totient 

n = 24

# Use totient() method 

totient_n = totient(n) 

print("phi({}) = {} ".format(n, totient_n)) # 1 5 7 11 13 17 19 23 

Output:

phi(24)=8