Euler’s Totient: A Guide

Daniel Liu

June 2021

Introduction: 

Euler’s totient is a function that, when given an integer n, computes the number of integers less than n that are relatively prime to n. The function is denoted by the symbol \phi. Thus, \phi(3) is simply 2, since the numbers less than 3 that are relatively prime to 3 are 1 and 2. Similarly, \phi(8) is 4, as we see there are four integers less than 8 relatively prime to 8: 1, 3, 5, and 7. As you will see later, this function is extremely useful in number theory, especially when computing the last a digits of a given expression, such as 23^5 . Note that Euler’s totient is synonymous with the phi function and both names will be used interchangeably throughout this guide.

Computing Values:

Calculating values for Euler’s totient turns out to be a fairly easy task- though it may become computationally burdensome for larger integers. The general formula for the function is, given a prime integer a,

\phi(a^k)=a^k - a^{k-1}

Remark: From this, one can derive that \phi of a prime p is always p-1.  

However, this formula seems to be of little use at first glance, as it is only applicable to powers of primes, such as 7^{12}. This renders it useless for numbers such as 35 (5*7) whose factorizations involve more than one prime.

Luckily, there is one identity that connects the formula to all integers: 

\phi(ab)=\phi(a)*\phi(b)

which holds for all relatively prime integers a and b. 

Example 1.1: Compute \phi(27).

Since 27’s prime factorization is 3^3, we simply plug this value into the formula to get 

\phi(3^3)=3^3-3^{3-1}

which equals 18.

Example 1.2: Compute \phi(1932).

Through a bit of long division and guess-and-check, we come to the conclusion that 1932 = 2^2 * 3 * 7 * 23. We repeat the above process to compute that \phi(2^2) is equal to 2. Because 3, 7, and 23 are all prime, we can use the identity that ϕ of a prime number is equivalent to the prime number minus one: \phi(3)=2, \phi(7)=6, \phi(23)=22. To finish out the problem, we multiply together the values of each computation to get 528.

Exercise 1.1: Compute \phi(17).

Exercise 1.2: Compute \phi(42226).

☆ Exercise 1.3: Prove the identity \phi(ab) = \phi(a) * \phi(b).

Euler’s Theorem

Admittedly, the phi function alone has little use in the real world. However, its applications allow its influence on the field of number theory to range far. Perhaps the most prominent use is in Euler’s Theorem. The theorem states that, for coprime integers a and n, 

a^{\phi(n)} \equiv 1 (mod \ n)

Example 2.1: Find the last two digits of 37^{2042}. 

To find the last two digits of the number, we take its value modulo 100. At first, this task seems quite daunting. How would we find that? But note that 37 and 100 are relatively prime. This means that 37^{\phi(100)} \equiv 1 (mod \ n) by Euler’s theorem. 

We observe that 100 = 2^2 * 5^2, which mean \phi(100) is 40. Thus, 37^{40} \equiv 1 (mod\ 100). Further, (37^{40})^{51} = 37^{2040}. This means that 37^{2040} \equiv 1 (mod\ 100). 

We now claim that 37^{2042} \equiv 37^2 (mod\ 100). From here, 37^2 =1369 \equiv 69 (mod\ 100). Therefore, the last two digits of 37^{2042} are 69.

Example 2.2: Find the last two digits of 44^{2006} . 

The obvious solution would be to attempt to emulate our process in the previous problem. However, we quickly realize that we are unable to do that, since 44 and 2006 are not coprime.

We shall now use properties of exponents and mod to our advantage. 44^{2006} = 4^{2006} * 11^{2006} . Moreover, if 4^{2005} \equiv a\ (mod\ 25), then 4*4^{2005}=4a\ (mod\ 4*25) by the property ac \equiv bc\ (mod\ nc) . 

Thus, we can claim that 4^{2006} \equiv 4a\ (mod\ 100). 

From here, we compute 4^{2005} \ (mod\ 25). If we can do this, we know 4^{2006}\ (mod\ 100), based on the claim above. Since 4 and 25 are relatively prime, 4^{\phi(25)} \equiv 1\ (mod\ 25) \to 4^{20} \equiv 1\ (mod\ 25). Because (4^{20}) ^{100} is equivalent to 4^{2000}, 4^{2005} \equiv 4^5 \ (mod\ 25). We can easily compute 4^5 by hand to get that 4^{2005} \equiv -1\ (mod\ 25). 

This means that 4^{2006} \equiv -4\ (mod\ 100).

We now compute 11^{2006}\ (mod\ 100). For the sake of brevity, its calculation will not be fully explained, since it is a direct application of Euler’s theorem and exactly mirrors example 2.1, but with different numbers. 11^{2006} \equiv 61\ (mod\ 100).

The answer is simply (-4)* 61 \ (mod\ 100), which equals -244\ (mod\ 100). Since -300 is the closest multiple of 100 to -244 that is still less than -244, we perform -244 - (-300) to arrive at our answer, 56.

     Exercise 2.1: Find\ the\ last\ two\ digits\ of\ 29^{63} .

     Exercise 2.2: Find the last three digits of 42^{56} .

☆ Exercise 2.3: Let N be a positive integer, and A(N) be the sum of the digits of N. Define S(N) to be the single digit obtained by repeatedly applying the function A(N) on N (as many times as needed). Find S(7^{7^{7^{\dots}}}), where there are 2021 7’s in the tower. Hint: A(N) is equivalent to N (mod 9). 

☆ Exercise 2.4: Prove that a^{\phi(n)} \equiv 1 \ (mod\ n). Hint: Consider an arbitrary set A whose elements are all taken modulo m, where each element is relatively prime to m. Prove that A is identical to set B mod m, where the elements of B are found by multiplying the elements of A by a constant a.

Leave a comment