Euler's Totient Function Reference Cheat Sheet

Euler's totient function counts how many positive integers up to a given integer are relatively prime to it. This cheat sheet helps students compute $\varphi(n)$ quickly, recognize useful number patterns, and connect factorization to counting. It is especially useful for modular arithmetic, cryptography, and contest-style number theory problems.

Key Facts

Euler's totient function $\varphi(n)$ equals the number of integers $k$ with $1 \le k \le n$ and $\gcd(k,n)=1$ .
For a prime number $p$ , every positive integer less than $p$ is relatively prime to $p$ , so $\varphi(p)=p-1$ .
For a prime power $p^a$ , the formula is $\varphi(p^a)=p^a-p^{a-1}=p^a\left(1-\frac{1}{p}\right)$ .
If $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ , then $\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)$ .
If $\gcd(a,b)=1$ , then Euler's totient function is multiplicative, so $\varphi(ab)=\varphi(a)\varphi(b)$ .
Euler's theorem states that if $\gcd(a,n)=1$ , then $a^{\varphi(n)} \equiv 1 \pmod n$ .
For $n>2$ , the value $\varphi(n)$ is even because relatively prime residues can be paired as $k$ and $n-k$ .

Vocabulary

Euler's Totient Function: The function $\varphi(n)$ counts the positive integers from $1$ to $n$ that are relatively prime to $n$ .
Relatively Prime: Two integers $a$ and $b$ are relatively prime when $\gcd(a,b)=1$ .
Prime Power: A prime power is a number of the form $p^a$ , where $p$ is prime and $a$ is a positive integer.
Prime Factorization: Prime factorization writes an integer as a product of prime powers, such as $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ .
Multiplicative Function: A function $f$ is multiplicative when $f(ab)=f(a)f(b)$ for all pairs with $\gcd(a,b)=1$ .
Euler's Theorem: Euler's theorem says that if $\gcd(a,n)=1$ , then $a^{\varphi(n)} \equiv 1 \pmod n$ .

Common Mistakes to Avoid

Using $\varphi(ab)=\varphi(a)\varphi(b)$ when $\gcd(a,b)\ne 1$ is wrong because multiplicativity only works for relatively prime factors.
Forgetting to use only distinct prime factors in $\varphi(n)=n\prod\left(1-\frac{1}{p}\right)$ is wrong because each prime divisor should appear once, not once for every power.
Thinking $\varphi(p^a)=p^a-1$ is wrong because multiples of $p$ are not relatively prime to $p^a$ , so the correct formula is $\varphi(p^a)=p^a-p^{a-1}$ .
Counting $0$ as part of $\varphi(n)$ is wrong because $\varphi(n)$ counts positive integers $k$ with $1 \le k \le n$ and $\gcd(k,n)=1$ .
Applying Euler's theorem without checking $\gcd(a,n)=1$ is wrong because the congruence $a^{\varphi(n)} \equiv 1 \pmod n$ requires $a$ and $n$ to be relatively prime.

Practice Questions

1 Compute $\varphi(36)$ using the prime factorization $36=2^2\cdot 3^2$ .
2 Find $\varphi(100)$ and list the distinct prime factors used in the product formula.
3 Use Euler's theorem to simplify $7^{\varphi(20)} \pmod {20}$ , after checking that $\gcd(7,20)=1$ .
4 Explain why $\varphi(n)$ depends on the distinct prime divisors of $n$ , not just on the size of $n$ .

Understanding Euler's Totient Function Reference

The fastest way to understand the formula is to think about excluded numbers. Start with every number in a complete set of residues. Any number sharing a prime factor with the modulus must be removed.

For a number divisible by two, half the residues are removed. For a number divisible by three, one third are removed. Some residues were removed twice because they are divisible by both primes, so they must be restored once.

This is the inclusion and exclusion idea. It explains why each distinct prime contributes one factor of one minus one over that prime. The exponent of a prime changes the size of the set, but it does not create a new kind of exclusion.

Factorisation is therefore the main practical skill. To find the totient of sixty, first write sixty as two squared times three times five. Begin with sixty.

Removing the multiples of two leaves thirty possible residues. Removing the remaining multiples of three leaves twenty. Removing the remaining multiples of five leaves sixteen.

Thus the totient of sixty is sixteen. This method works cleanly because only distinct prime divisors matter in the fractional reductions. Students often make the mistake of using every repeated prime factor in the product.

For example, a factor of two squared still gives only one reduction based on two. Prime factorisation must be correct before any totient calculation can be trusted.

Totients appear when powers repeat in modular arithmetic. Suppose a base has no common prime factor with the modulus. Its successive powers can be reduced to a repeating cycle.

A totient gives a dependable cycle length, though the actual cycle can be shorter. This makes large exponents manageable. For example, when working modulo fifteen, the powers of two return to one after a number of steps that divides the totient of fifteen, which is eight.

An exponent such as one hundred can then be reduced using the cycle. This idea is important in public key cryptography. Encryption systems use very large products of primes because the arithmetic is easy when the prime factors are known, while finding those factors from the product is difficult.

There are several details worth checking in exercises. The number one has totient one, even though it has no prime factors. Multiplicativity only applies when the two parts share no prime factor.

It cannot be used to claim that the totient of four times two equals the totient of four times the totient of two, since four and two are not coprime. In modular power problems, the base must be coprime to the modulus before Euler's theorem is applied. If that condition fails, reducing an exponent by the totient can give a wrong answer.

A useful habit is to write three short lines in order. Factor the modulus.

Check the greatest common divisor of the base and modulus. Then calculate the totient or identify the needed power cycle.

Sign in to save

Sign in to save

Euler's Totient Function Reference Cheat Sheet

Related Tools

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions

Understanding Euler's Totient Function Reference