Euler's Totient Function and Modular Exponentiation

 

Introduction

In number theory and modern cryptography, dealing with astronomically large numbers is a daily necessity. To efficiently compute large powers in modular arithmetic, mathematicians rely on a powerful two-step combination: Euler’s Totient Function (to shrink the exponent) and the Method of Repeated Squares (to compute the final value).

Euler’s Totient Function

Euler's totient function, denoted by $\varphi(n)$, counts the number of positive integers up to $n$ that are relatively prime (coprime) to $n$. Two numbers are relatively prime if their greatest common divisor (GCD) is $1$.

Formally, for any integer $n > 1$: $\varphi(n) = \vert{}\{a \in \mathbb{Z} : 1 \le a \le n \text{ and } \gcd(a, n) = 1\}\vert{}$

For the base case, we define $\varphi(1) = 1$.

To see this in action, let’s look at the first 12 values of the function:

n	1	2	3	4	5	6	7	8	9	10	11	12
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4	10	4

The Euler $\varphi$-function is a map $\varphi: \mathbb{Z}^+ \to \mathbb{Z}^+$ such that $\varphi(1) = 1$ and $\varphi(n)$ is equal to the number of positive integers coprime to $n$ for $n \gt 1$.

Properties

• Prime Numbers: If $p$ is a prime number, every positive integer less than $p$ is coprime to it. $\varphi(p) = p - 1$

• Prime Powers: If you have a power of a prime, $p^k$, the only numbers not coprime to it are the multiples of $p$. $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

In the interval $[1, p^k]$, the multiples of $p$ are $[p, 2p, 3p, \dots, p^{k-1}p = p^k]$ (those not coprime of $p^k$), exactly $p^{k-1}$ of them. Subtracting these from the total number of integers in $[1, p^k]$, that is, $p^k$, gives the count of integers coprime to $p^k$.

Example: In the interval $[1, 8]$, the multiples of $2$ are $[2, 4, 6, 8]$, exactly 4 of them. $\varphi(8) = \varphi(2^3) = 2^3 - 2^2 = 8 - 4 = 4$. $\varphi(9) = \varphi(3^2) = 3^2 - 3^1 = 9 - 3 = 6$.

• Multiplicativity: The function is multiplicative for coprime integers. If two numbers are coprime $\gcd(a, b) = 1$, then: $\varphi(ab) = \varphi(a)\varphi(b)$

Examples: $\varphi(40) = \varphi(8)\varphi(5) = 4 \cdot 4 = 16$. $\varphi(6) = \varphi(2)\varphi(3) = 1 \times 2 = 2.$ $\varphi(12) = \varphi(4)\varphi(3) = 2 \times 2 = 4$.

• Euler’s Product Formula. By combining the prime power and multiplicative properties, we arrive at the general formula for any integer $n$.

If a number has the prime factorization $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$, then: $\boxed{\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)}$

Suppose $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}.$ Because the prime powers are pairwise coprime, multiplicativity gives $\varphi(n) = \varphi(p_1^{\alpha_1})\, \varphi(p_2^{\alpha_2})\, \cdots\, \varphi(p_k^{\alpha_k}).$

Now substitute the prime‑power formula into each factor: $\varphi(p_i^{\alpha_i}) = p_i^{\alpha_i} - p_i^{\alpha_i-1} = p_i^{\alpha_i}\left(1 - \frac{1}{p_i}\right)$.

Multiply all of them together: $\varphi(n) = \left(p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}\right) \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right).$

But the first parenthesis is just $n$. So we arrive at the compact form: $\boxed{\varphi(n) = n \prod_{p\mid n}\left(1 - \frac{1}{p}\right)}$

To find $\varphi(75)$, we factor it as $3 \cdot 5^2$. $\varphi(75) = 75 \left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 75 \left(\frac{2}{3}\right)\left(\frac{4}{5}\right) = 40$

$\varphi(12) = \varphi(2^2 \cdot 3) = 2(2-1)3^0(3-1) = 4, \varphi(20) = \varphi(2^2·5) = 2(2-1)5^0(5-1) = 2·4 = 8, \varphi(75) = \varphi(5^2·3) = 5(5-1)3^0(3-1) = 5·4·2 = 40.$

Euler’s Theorem and Group Theory Applications

Why do we care about counting coprime integers? Because it dictates the structure of multiplicative groups in modular arithmetic.

If we define $U_n$ (often denoted $\mathbb{Z}_n^\times$) as the set of all positive integers less than $n$ that have a multiplicative inverse modulo $n$, it turns out this set is exactly the numbers coprime to $n$. Therefore, the size of this group is $\vert{}U_n\vert{} = \varphi(n)$.

This leads us to the crown jewel of the totient function: Euler’s Theorem.

Let $a, n \in \mathbb{Z}$ with $n > 0$ and $\gcd(a, n) = 1$. Then, $\boxed{a^{\varphi(n)} \equiv 1 \pmod n}$

Proof.

1. Let $n \gt 0$ and list all integers in $[1, n]$ that are coprime to $n$: $r_1, r_2, \dots, r_{\varphi(n)}.$

2. Because $\gcd(a, n) = 1$, each product $ar_i$ is also coprime to $n$, and the set $ar_1, ar_2, \dots, ar_{\varphi(n)}$ is just a permutation of the original reduced residue system modulo $n$. They are distinct modulo $n$ and remain coprime to $n$.

3. Take the product of all these residues: Original product: $P = r_1 r_2 \cdots r_{\varphi(n)}.$ Product after multiplying each by $a$: $P' = (ar_1)(ar_2)\cdots(ar_{\varphi(n)}) = a^{\varphi(n)} P.$

4. Equating the products of the elements of both sets modulo $n$ yields: $(ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$.

5. Factoring out $a$ from each term on the left side results in $a^{\varphi(n)} P \equiv P \pmod n.$

6. Since every $r_i$ is coprime to $n$, their product $P$ is also coprime to $n$, ensuring $P$ has a valid multiplicative inverse modulo $n$. Canceling $P$ from both sides leaves $\boxed{a^{\varphi(n)} \equiv 1 \pmod n}$.

This theorem is a computational lifesaver. If you are asked to compute a massive exponent, say $7^{1000} \pmod{10}$, you don’t need to multiply $7$ a thousand times.

1. Compute $\varphi(10)$. Prime factorization: $10 = 2 \cdot 5.$ Euler’s product formula: $\varphi(10) = 10\left(1-\frac12\right)\left(1-\frac15\right) = 10 \cdot \frac12 \cdot \frac45 = 4.$
2. So every number coprime to $10$ satisfies: $a^4 \equiv 1 \pmod{10}.$
3. Since $\gcd(7,10)=1$, this applies to $7$.
4. Reduce the exponent using Euler’s theorem. You want: $7^{1000} \pmod{10}.$ Euler tells you: $7^4 \equiv 1 \pmod{10}.$ So you reduce the exponent modulo $4$: $1000 \equiv 0 \pmod{4}.$ That means: $7^{1000} = (7^4)^{250}.$ And since $7^4 \equiv 1$: $(7^4)^{250} \equiv 1^{250} \equiv 1 \pmod{10}.$
5. Final result $\boxed{7^{1000} \equiv 1 \pmod{10}}.$

The Method of Repeated Squares

Euler’s Theorem shrinks the exponent, but what if the shrunken exponent is still fairly large? How do we efficiently compute $a^k \pmod n$? We use Binary Exponentiation, also known as the Method of Repeated Squares.

Instead of multiplying the base by itself $k$ times (which requires $k$ operations), we can achieve the result in roughly $\log_2(k)$ operations.

The Algorithm:

1. Convert the exponent $k$ into its binary (base-2) representation. This expresses $k$ as a sum of distinct powers of 2.
2. Repeatedly square the base $a$, taking the modulo $n$ at every step to keep the numbers small. This generates a list: $a^1, a^2, a^4, a^8, a^{16} \dots$
3. Multiply together only the squared terms that correspond to the binary $1$s in your exponent’s binary representation.

Example 1: A Small Case

Compute $5^7 \pmod{21}$.

First, break the exponent $7$ into powers of 2: $7 = 4 + 2 + 1$. This means $5^7 = 5^4 \cdot 5^2 \cdot 5^1$.

Now, build our table of squares modulo $21$:

1. $5^1 \equiv \mathbf{5} \pmod{21}$
2. $5^2 = 25 \equiv \mathbf{4} \pmod{21}$
3. $5^4 = (5^2)^2 \equiv 4^2 = 16 \equiv \mathbf{16} \pmod{21}$

Finally, multiply the necessary pieces together: $5^7 \equiv 5^4 \cdot 5^2 \cdot 5^1 \equiv 16 \cdot 4 \cdot 5 \pmod{21}$. $16 \cdot 4 \cdot 5 = 320 \equiv \mathbf{5} \pmod{21}$.

Example 2: A Massive Case

Compute $271^{321} \pmod{481}$.

First, express the exponent $321$ in binary (or sum of powers of 2): $321 = 256 + 64 + 1 = 2^8 + 2^6 + 2^0$.

So, $271^{321} = 271^{256} \cdot 271^{64} \cdot 271^1$.

Now, we repeatedly square the base, reducing modulo $481$ at every single step so the numbers never exceed our calculator’s limits:

1. $271^{1} \equiv \mathbf{271} \pmod{481}$
2. $271^{2} \equiv 271^2 = 73441 \equiv 329 \pmod{481}$
3. $271^{4} \equiv 329^2 = 108241 \equiv 16 \pmod{481}$
4. $271^{8} \equiv 16^2 = 256 \pmod{481}$
5. $271^{16} \equiv 256^2 = 65536 \equiv 120 \pmod{481}$
6. $271^{32} \equiv 120^2 = 14400 \equiv 451 \pmod{481}$
7. $271^{64} \equiv 451^2 = 203401 \equiv \mathbf{419} \pmod{481}$
8. $271^{128} \equiv 419^2 = 175561 \equiv 477 \pmod{481}$ (Note: $477 \equiv -4$, which makes the next step easy!)
9. $271^{256} \equiv 477^2 \equiv (-4)^2 = \mathbf{16} \pmod{481}$

Finally, we combine the partial results for the powers we actually need ($256, 64,$ and $1$): $271^{321} \equiv 271^{256} \cdot 271^{64} \cdot 271^{1} \pmod{481} \equiv 16 \cdot 419 \cdot 271 \pmod{481}$

Break this down into two manageable multiplications:

• $16 \cdot 419 = 6704 \equiv 451 \pmod{481}$
• $451 \cdot 271 = 122221 \equiv \mathbf{47} \pmod{481}$

Through the Method of Repeated Squares, a computation that would normally result in a number with hundreds of digits was easily solved using only basic arithmetic.

Applications of Euler’s Totient Function in Abstract Algebra

The Group of Units ($U_n$)

In modular arithmetic, not every number has a multiplicative inverse. For example, if you are working modulo $6$, there is no integer $b$ you can multiply by $2$ to get $1$ (since $2b$ is always even, and $1$ is odd).

For any integer $n > 1$, we define a special set: The Group of Units, denoted $U_n$ (or $\mathbb{Z}_n^\times$), is the set of all positive integers strictly less than $n$ that possess a multiplicative inverse modulo $n$.Mathematically, an element $a$ belongs to $U_n$ if there exists some element $b$ such that: $ab \equiv 1 \pmod n$

Why does Euler’s Totient function matter here?

Because an element has a multiplicative inverse modulo $n$ if and only if it is relatively prime to $n$.

We can prove this elegantly using Bézout’s Identity, which states that if $\gcd(a, n) = 1$, there exist integers $x$ and $y$ such that: $ax + ny = 1$

If we take this entire equation modulo $n$, the $ny$ term becomes $0$ (since it is a multiple of $n$), leaving us with: $ax \equiv 1 \pmod n$

Here, $x$ is our multiplicative inverse! If $\gcd(a, n) > 1$, this equation can never equal $1$, meaning no inverse can exist.

Therefore, the set of units is exactly the set of coprime integers: $U_n = \{a \in \mathbb{Z}_n : \gcd(a, n) = 1\}$

Because $\varphi(n)$ literally counts the number of integers coprime to $n$, the size (or order) of this group is precisely determined by the totient function: $\vert{}U_n\vert{} = \varphi(n)$

Example: $U_{10}$

Let’s find the units modulo $10$. We check the numbers from $1$ to $9$ to see which share no prime factors with $10$ (which is $2 \cdot 5$).

• Coprime to 10: $\{1, 3, 7, 9\}$
• Not coprime: $\{2, 4, 5, 6, 8\}$
• Thus, $U_{10} = \{1, 3, 7, 9\}$. The size of this group is $4$, which perfectly matches our formula: $\varphi(10) = \varphi(2)\varphi(5) = (1)(4) = 4$.

Generators of a Cyclic Group

Euler’s totient function also rules the geometry of Cyclic Groups.

Let $G = \langle a \rangle$ be a cyclic group of order $n$ generated by an element $a$. By definition, this means applying the group operation to $a$ repeatedly generates every single element in the group until $a^n$ returns to the identity element.

But $a$ is usually not the only generator of the group. Other elements of the form $a^j$ might also generate the entire group. How do we know which ones?

We rely on the formula for the order of an arbitrary element $a^j$: $\vert{}a^j\vert{} = \frac{n}{\gcd(n, j)}$

For $a^j$ to generate the entire group, its order must be exactly $n$. Looking at our formula, this happens if and only if the denominator is exactly $1$: $\langle a^j \rangle = \langle a \rangle \iff \frac{n}{\gcd(n, j)} = n \iff \gcd(n, j) = 1$

An element $a^j$ generates the cyclic group of order $n$ if and only if its exponent $j$ is relatively prime to $n$. Consequently, because there are exactly $\varphi(n)$ integers relatively prime to $n$, the total number of distinct generators of a cyclic group of order $n$ is exactly $\varphi(n)$.

Counting Elements of a Specific Order

We can push this logic one step further to analyze the internal subgroups of our cyclic group.

According to the Fundamental Theorem of Cyclic Groups, if $G$ is a cyclic group of order $n$, then for every positive divisor $d$ of $n$, there exists exactly one unique subgroup of order $d$. Furthermore, this subgroup is itself cyclic.

Because this subgroup is cyclic and has order $d$, we can apply the exact same rule we just proved above: the number of generators of this subgroup is $\varphi(d)$.

Any element in the main group $G$ that has an order of exactly $d$ must be a generator for this unique subgroup of order $d$. Therefore, if $d$ is a positive divisor of $n$, the number of elements of order $d$ in a cyclic group of order $n$ is exactly $\varphi(d)$.

Example: Elements of order 4 in $\mathbb{Z}_{12}$

Consider the cyclic group of integers modulo 12 under addition. Because $4$ perfectly divides $12$, we know there is exactly one subgroup of order $4$.

How many elements in $\mathbb{Z}_{12}$ have an order of exactly $4$? We do not need to manually check all $12$ elements. We simply calculate: $\varphi(4) = \varphi(2^2) = 2^2 - 2^1 = 2$

There are exactly $2$ elements of order $4$. (If we check manually, those elements are $3$ and $9$, because $3+3+3+3 = 12 \equiv 0$ and $9+9+9+9 = 36 \equiv 0$, and no fewer additions reach $0$). The mathematics flawlessly predicts the group’s architecture.