Number TheoryDifficulty 45-9050 tagged problems

Euler's Phi Function

Euler's Phi Function is the habit of counting residues coprime to n and generalizing Fermat-style exponent reductions. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$a^{\varphi(n)} \equiv 1 \pmod{n} \ \text{ for } \gcd(a,n)=1, \qquad \varphi(n) = n \prod_{p \mid n}\left(1 - \tfrac{1}{p}\right)$$

Euler's totient $\varphi(n)$ counts integers in $1,\dots,n$ coprime to $n$, and any base coprime to $n$ raised to $\varphi(n)$ is $1$ modulo $n$ — Fermat generalized to composite moduli.

Why It Works

1
$\varphi$ is multiplicative on coprime factors, and $\varphi(p^e) = p^e - p^{e-1} = p^e(1 - 1/p)$, which combine into the product formula.
2
Let $r_1, \dots, r_{\varphi(n)}$ be the residues coprime to $n$; multiplying each by a unit $a$ permutes this set mod $n$.
3
Hence $\prod_i (a r_i) \equiv \prod_i r_i \pmod n$, i.e. $a^{\varphi(n)} \prod_i r_i \equiv \prod_i r_i$.
4
Each $r_i$ is invertible mod $n$, so cancel the product to obtain $a^{\varphi(n)} \equiv 1 \pmod n$.

Worked Examples

Example 1

Find the units digit of $7^{222}$.

1
The units digit is $7^{222} \bmod 10$; here $\gcd(7,10) = 1$.
2
Compute $\varphi(10) = 10\left(1 - \tfrac12\right)\left(1 - \tfrac15\right) = 10 \cdot \tfrac12 \cdot \tfrac45 = 4$, so $7^4 \equiv 1 \pmod{10}$.
3
Reduce the exponent mod $4$: $222 = 4 \cdot 55 + 2$, so $7^{222} \equiv 7^2 \pmod{10}$.
4
Then $7^2 = 49 \equiv 9 \pmod{10}$.

Answer:

$9$

Warm-up

Compute $\varphi(36)$.

1
Factor $36 = 2^2 \cdot 3^2$.
2
Use the product formula $\varphi(n) = n \prod_{p \mid n}\left(1 - \tfrac1p\right)$: $\varphi(36) = 36\left(1 - \tfrac12\right)\left(1 - \tfrac13\right)$.
3
Compute: $36 \cdot \tfrac12 \cdot \tfrac23 = 36 \cdot \tfrac13 = 12$.
4
Check via multiplicativity: $\varphi(4)\varphi(9) = 2 \cdot 6 = 12$. ✓

Answer:

$12$

Contest level

Find the last three digits of $7^{803}$.

1
The last three digits are $7^{803} \bmod 1000$, and $\gcd(7, 1000) = 1$.
2
Compute $\varphi(1000) = \varphi(2^3 \cdot 5^3) = 1000\left(1 - \tfrac12\right)\left(1 - \tfrac15\right) = 1000 \cdot \tfrac12 \cdot \tfrac45 = 400$, so $7^{400} \equiv 1 \pmod{1000}$.
3
Reduce the exponent mod $400$: $803 = 2 \cdot 400 + 3$, so $7^{803} \equiv 7^3 \pmod{1000}$.
4
Compute $7^3 = 343$.

Answer:

$343$

Olympiad / Challenge

Prove that $\sum_{d \mid n} \varphi(d) = n$ for every positive integer $n$ (the totient summation identity).

1
Partition the $n$ fractions $\tfrac{1}{n}, \tfrac{2}{n}, \dots, \tfrac{n}{n}$ according to the denominator each takes in lowest terms.
2
When $\tfrac{k}{n}$ is reduced to lowest terms, its denominator is some divisor $d$ of $n$, and the reduced numerator is coprime to $d$ with $1 \le (\text{numerator}) \le d$.
3
For a fixed divisor $d$, the fractions reducing to denominator $d$ are exactly $\tfrac{j}{d}$ with $\gcd(j, d) = 1$, $1 \le j \le d$ — and there are precisely $\varphi(d)$ of them.
4
Every one of the $n$ fractions falls into exactly one class, so summing the class sizes gives $\sum_{d \mid n}\varphi(d) = n$.

Answer:

$\sum_{d \mid n} \varphi(d) = n$.

Going Deeper

Generalization: Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod n$ generalizes Fermat to any modulus when $\gcd(a,n) = 1$. The sharpest exponent is the Carmichael function $\lambda(n) \mid \varphi(n)$ (often strictly smaller), which gives the true universal period; $\varphi$ is always a valid but not always minimal exponent.
Where it appears: collapsing exponents for $a^N \bmod n$ with composite $n$ (last-$k$-digits problems use $n = 10^k$), power towers (Euler's theorem applied recursively up the tower), the RSA cryptosystem, and counting coprime residues / Farey fractions.
Pitfall: $a^{\varphi(n)} \equiv 1$ needs $\gcd(a, n) = 1$ — for example $\gcd(7,1000)=1$ makes the reduction valid, but you could NOT reduce the exponent of $10^{803} \bmod 1000$ this way. Also $\varphi$ is multiplicative only across COPRIME factors: $\varphi(p^2) = p^2 - p \neq \varphi(p)^2$, so apply the prime-power formula $\varphi(p^k) = p^k - p^{k-1}$, not $\varphi(p)^k$.

Spot the Signal

Look for problems where the key step is counting residues coprime to n and generalizing Fermat-style exponent reductions.
You can describe the hard part as counting residues coprime to n and generalizing Fermat-style exponent reductions, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for euler's phi function, then rewrite the givens around it.
Name the relation that makes Euler's Phi Function legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Euler's Phi Function just because the surface looks familiar; verify the required condition first.
Applying Euler's Phi Function because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let euler's phi function reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is counting residues coprime to n and generalizing Fermat-style exponent reductions.

Back to techniques

Number TheoryDifficulty 45-9050 tagged problems

Euler's Phi Function

Practice this technique Match my level

The Key Result

$$a^{\varphi(n)} \equiv 1 \pmod{n} \ \text{ for } \gcd(a,n)=1, \qquad \varphi(n) = n \prod_{p \mid n}\left(1 - \tfrac{1}{p}\right)$$

Euler's totient $\varphi(n)$ counts integers in $1,\dots,n$ coprime to $n$, and any base coprime to $n$ raised to $\varphi(n)$ is $1$ modulo $n$ — Fermat generalized to composite moduli.

Why It Works

1
$\varphi$ is multiplicative on coprime factors, and $\varphi(p^e) = p^e - p^{e-1} = p^e(1 - 1/p)$, which combine into the product formula.
2
Let $r_1, \dots, r_{\varphi(n)}$ be the residues coprime to $n$; multiplying each by a unit $a$ permutes this set mod $n$.
3
Hence $\prod_i (a r_i) \equiv \prod_i r_i \pmod n$, i.e. $a^{\varphi(n)} \prod_i r_i \equiv \prod_i r_i$.
4
Each $r_i$ is invertible mod $n$, so cancel the product to obtain $a^{\varphi(n)} \equiv 1 \pmod n$.

Worked Examples

Example 1

Find the units digit of $7^{222}$.

1
The units digit is $7^{222} \bmod 10$; here $\gcd(7,10) = 1$.
2
Compute $\varphi(10) = 10\left(1 - \tfrac12\right)\left(1 - \tfrac15\right) = 10 \cdot \tfrac12 \cdot \tfrac45 = 4$, so $7^4 \equiv 1 \pmod{10}$.
3
Reduce the exponent mod $4$: $222 = 4 \cdot 55 + 2$, so $7^{222} \equiv 7^2 \pmod{10}$.
4
Then $7^2 = 49 \equiv 9 \pmod{10}$.

Answer:

$9$

Warm-up

Compute $\varphi(36)$.

1
Factor $36 = 2^2 \cdot 3^2$.
2
Use the product formula $\varphi(n) = n \prod_{p \mid n}\left(1 - \tfrac1p\right)$: $\varphi(36) = 36\left(1 - \tfrac12\right)\left(1 - \tfrac13\right)$.
3
Compute: $36 \cdot \tfrac12 \cdot \tfrac23 = 36 \cdot \tfrac13 = 12$.
4
Check via multiplicativity: $\varphi(4)\varphi(9) = 2 \cdot 6 = 12$. ✓

Answer:

$12$

Contest level

Find the last three digits of $7^{803}$.

1
The last three digits are $7^{803} \bmod 1000$, and $\gcd(7, 1000) = 1$.
2
Compute $\varphi(1000) = \varphi(2^3 \cdot 5^3) = 1000\left(1 - \tfrac12\right)\left(1 - \tfrac15\right) = 1000 \cdot \tfrac12 \cdot \tfrac45 = 400$, so $7^{400} \equiv 1 \pmod{1000}$.
3
Reduce the exponent mod $400$: $803 = 2 \cdot 400 + 3$, so $7^{803} \equiv 7^3 \pmod{1000}$.
4
Compute $7^3 = 343$.

Answer:

$343$

Olympiad / Challenge

Prove that $\sum_{d \mid n} \varphi(d) = n$ for every positive integer $n$ (the totient summation identity).

1
Partition the $n$ fractions $\tfrac{1}{n}, \tfrac{2}{n}, \dots, \tfrac{n}{n}$ according to the denominator each takes in lowest terms.
2
When $\tfrac{k}{n}$ is reduced to lowest terms, its denominator is some divisor $d$ of $n$, and the reduced numerator is coprime to $d$ with $1 \le (\text{numerator}) \le d$.
3
For a fixed divisor $d$, the fractions reducing to denominator $d$ are exactly $\tfrac{j}{d}$ with $\gcd(j, d) = 1$, $1 \le j \le d$ — and there are precisely $\varphi(d)$ of them.
4
Every one of the $n$ fractions falls into exactly one class, so summing the class sizes gives $\sum_{d \mid n}\varphi(d) = n$.

Answer:

$\sum_{d \mid n} \varphi(d) = n$.

Going Deeper

Generalization: Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod n$ generalizes Fermat to any modulus when $\gcd(a,n) = 1$. The sharpest exponent is the Carmichael function $\lambda(n) \mid \varphi(n)$ (often strictly smaller), which gives the true universal period; $\varphi$ is always a valid but not always minimal exponent.
Where it appears: collapsing exponents for $a^N \bmod n$ with composite $n$ (last-$k$-digits problems use $n = 10^k$), power towers (Euler's theorem applied recursively up the tower), the RSA cryptosystem, and counting coprime residues / Farey fractions.
Pitfall: $a^{\varphi(n)} \equiv 1$ needs $\gcd(a, n) = 1$ — for example $\gcd(7,1000)=1$ makes the reduction valid, but you could NOT reduce the exponent of $10^{803} \bmod 1000$ this way. Also $\varphi$ is multiplicative only across COPRIME factors: $\varphi(p^2) = p^2 - p \neq \varphi(p)^2$, so apply the prime-power formula $\varphi(p^k) = p^k - p^{k-1}$, not $\varphi(p)^k$.

Spot the Signal

Look for problems where the key step is counting residues coprime to n and generalizing Fermat-style exponent reductions.
You can describe the hard part as counting residues coprime to n and generalizing Fermat-style exponent reductions, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for euler's phi function, then rewrite the givens around it.
Name the relation that makes Euler's Phi Function legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Euler's Phi Function just because the surface looks familiar; verify the required condition first.
Applying Euler's Phi Function because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let euler's phi function reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is counting residues coprime to n and generalizing Fermat-style exponent reductions.