Chapter 1: Number Theory
Section 1.6 — Fermat's Little Theorem & Euler's Theorem | AIMO Training Programme
0. Section 1.5 Review — Guided Problem Walkthroughs
Four scaffolded problems revisiting Linear Congruences & CRT from Section 1.5. Try each step before opening the hint.
Review 1 Solve the linear congruence $14x \equiv 21 \pmod{35}$.
Key skills: Checking solvability, reducing by GCD, listing all solutions.
- Solvability. Compute $d = \gcd(14, 35)$. Does $d$ divide $21$?
Check
$\gcd(14, 35) = 7$. Does $7 \mid 21$? Yes, $21 = 3 \times 7$. So there are exactly $d = 7$ solutions mod $35$.
- Reduce. Divide through by $d = 7$: solve $2x \equiv 3 \pmod{5}$.
Check
Dividing: $14/7 = 2$, $21/7 = 3$, $35/7 = 5$. New equation: $2x \equiv 3 \pmod{5}$.
$\gcd(2, 5) = 1$, so unique solution mod 5. $2^{-1} \equiv 3 \pmod{5}$ (since $2 \times 3 = 6 \equiv 1$).
$x_0 \equiv 3 \times 3 = 9 \equiv 4 \pmod{5}$.
- List all solutions mod 35. Using $x_0 = 4$ and spacing $35/7 = 5$.
Check
The 7 solutions mod 35 are: $x \equiv 4, 9, 14, 19, 24, 29, 34 \pmod{35}$.
Verify P1: $14 \times 4 = 56 = 35 + 21 \equiv 21 \pmod{35}$
Review 2 Solve the system of congruences:
$$x \equiv 2 \pmod{5}, \quad x \equiv 3 \pmod{7}, \quad x \equiv 1 \pmod{8}.$$
Key skills: Chinese Remainder Theorem — step-by-step substitution.
- Combine first two. From $x \equiv 2 \pmod{5}$, write $x = 5k + 2$. Substitute into the second congruence and find $k$.
Check
$5k + 2 \equiv 3 \pmod{7} \Rightarrow 5k \equiv 1 \pmod{7}$.
$5^{-1} \equiv 3 \pmod{7}$ (since $5 \times 3 = 15 \equiv 1$).
$k \equiv 3 \pmod{7}$, so $k = 7j + 3$, giving $x = 35j + 17$.
Combined: $x \equiv 17 \pmod{35}$.
- Combine with the third. Substitute $x = 35j + 17$ into $x \equiv 1 \pmod{8}$.
Check
$35j + 17 \equiv 1 \pmod{8} \Rightarrow 3j + 1 \equiv 1 \pmod{8} \Rightarrow 3j \equiv 0 \pmod{8}$.
Since $\gcd(3, 8) = 1$: $j \equiv 0 \pmod{8}$.
$j = 8m$, so $x = 280m + 17$.
Answer: $x \equiv \boxed{17} \pmod{280}$.
- Verify. Check $17$ satisfies all three original congruences.
Check
$17 = 3 \times 5 + 2 \equiv 2 \pmod{5}$ $17 = 2 \times 7 + 3 \equiv 3 \pmod{7}$ $17 = 2 \times 8 + 1 \equiv 1 \pmod{8}$
Review 3 Find all integers $x$ such that $x \equiv 3 \pmod{4}$ and $x \equiv 5 \pmod{6}$. What is the smallest positive such $x$?
Key skills: CRT with non-coprime moduli — checking consistency.
- Check consistency. $\gcd(4, 6) = 2$. For a solution to exist, what condition must $3$ and $5$ satisfy?
Hint
When moduli are not coprime, the system $x \equiv a \pmod{m}$, $x \equiv b \pmod{n}$ is solvable iff $\gcd(m,n) \mid (a - b)$.
Here: $\gcd(4,6) = 2$ and $a - b = 3 - 5 = -2$. Since $2 \mid -2$ , solutions exist.
- Solve. Write $x = 4k + 3$ and substitute.
Check
$4k + 3 \equiv 5 \pmod{6} \Rightarrow 4k \equiv 2 \pmod{6}$.
Divide by $\gcd(4,6)=2$: $2k \equiv 1 \pmod{3}$. $2^{-1} \equiv 2 \pmod{3}$, so $k \equiv 2 \pmod{3}$.
$k = 3j + 2$, $x = 12j + 11$.
Answer: $x \equiv 11 \pmod{12}$. Smallest positive: $x = 11$.
- Verify. Check $x = 11$: $11 \div 4 = 2$ R $3$ , $11 \div 6 = 1$ R $5$ .
Check
$11 \equiv 3 \pmod{4}$ and $11 \equiv 5 \pmod{6}$ . Correct!
Review 4 Find the remainder when $3^{100}$ is divided by $7$ using modular inverses.
Key skills: Cyclic powers, pattern recognition.
- Find the pattern. Compute $3^1, 3^2, 3^3, \ldots \pmod{7}$ until it repeats.
Check
$3^1 \equiv 3$, $3^2 \equiv 2$, $3^3 \equiv 6$, $3^4 \equiv 4$, $3^5 \equiv 5$, $3^6 \equiv 1 \pmod{7}$.
The cycle has period $6$.
- Reduce the exponent. Write $100 = 6q + r$ and find $r$.
Check
$100 = 6 \times 16 + 4$, so $r = 4$. Thus $3^{100} \equiv 3^4 \equiv 4 \pmod{7}$.
- State the answer and connection to Fermat. Why is the period $6$ predictable from Fermat's Little Theorem?
Check
Fermat's Little Theorem: $3^{7-1} = 3^6 \equiv 1 \pmod{7}$. The period (order) of $3$ mod $7$ must divide $6 = p - 1$.
The period turns out to be exactly $6$, meaning $3$ is a primitive root mod $7$.
Answer: $3^{100} \equiv \boxed{4} \pmod{7}$.
1. Euler's Totient Function $\varphi(n)$
Definition. For a positive integer $n$, Euler's totient function $\varphi(n)$ counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$:
$$\varphi(n) = \#\{k : 1 \le k \le n,\; \gcd(k, n) = 1\}.$$
Computing $\varphi(n)$. If $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$, then:
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = p_1^{a_1-1}(p_1-1)\, p_2^{a_2-1}(p_2-1) \cdots p_r^{a_r-1}(p_r-1).$$
Special cases:
- $\varphi(p) = p - 1$ for prime $p$.
- $\varphi(p^k) = p^{k-1}(p-1)$.
- $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m, n) = 1$ (multiplicative).
- $\sum_{d \mid n} \varphi(d) = n$ (useful identity).
Example 1. Compute $\varphi(60)$ and $\varphi(100)$.
$\varphi(60)$: $60 = 2^2 \times 3 \times 5$.
$$\varphi(60) = 60 \times \left(1 - \tfrac{1}{2}\right)\left(1 - \tfrac{1}{3}\right)\left(1 - \tfrac{1}{5}\right) = 60 \times \tfrac{1}{2} \times \tfrac{2}{3} \times \tfrac{4}{5} = 16.$$
$\varphi(100)$: $100 = 2^2 \times 5^2$.
$$\varphi(100) = \varphi(4) \times \varphi(25) = 2 \times 20 = 40.$$
Check: $\varphi(4) = 4(1 - \tfrac{1}{2}) = 2$ . $\varphi(25) = 25(1 - \tfrac{1}{5}) = 20$ .
Quick check: $\varphi(p^k) = p^{k-1}(p-1)$. For $\varphi(8) = \varphi(2^3) = 4$, $\varphi(9) = \varphi(3^2) = 6$.
2. Euler's Theorem
Euler's Theorem. If $\gcd(a, n) = 1$, then:
$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$
This is the cornerstone theorem for reducing large powers modulo $n$. It generalises Fermat's Little Theorem (which applies only when $n$ is prime).
Example 2. Find the remainder when $7^{200}$ is divided by $100$.
$\gcd(7, 100) = 1$ . $\varphi(100) = 40$.
By Euler's Theorem: $7^{40} \equiv 1 \pmod{100}$.
$200 = 40 \times 5 + 0$, so $7^{200} = (7^{40})^5 \equiv 1^5 = \boxed{1} \pmod{100}$.
So the last two digits of $7^{200}$ are $01$.
Example 3. Find $2^{1000} \pmod{15}$.
$\gcd(2, 15) = 1$ . $15 = 3 \times 5$, $\varphi(15) = \varphi(3)\varphi(5) = 2 \times 4 = 8$.
By Euler: $2^8 \equiv 1 \pmod{15}$. Let's verify: $2^8 = 256 = 17 \times 15 + 1$ .
$1000 = 8 \times 125 + 0$, so $2^{1000} = (2^8)^{125} \equiv 1 \pmod{15}$.
Warning. Euler's theorem requires $\gcd(a, n) = 1$. If $p \mid a$, you cannot apply it. For example, $2^4 \not\equiv 1 \pmod{8}$ (since $\gcd(2,8) = 2 \neq 1$).
3. Fermat's Little Theorem
Fermat's Little Theorem. Let $p$ be a prime and $a$ an integer with $p \nmid a$. Then:
$$a^{p-1} \equiv 1 \pmod{p}.$$
Equivalently, for any integer $a$: $a^p \equiv a \pmod{p}$.
Example 4. Find $3^{2025} \pmod{13}$.
$13$ is prime and $13 \nmid 3$. By Fermat: $3^{12} \equiv 1 \pmod{13}$.
$2025 = 12 \times 168 + 9$, so $3^{2025} \equiv 3^9 \pmod{13}$.
Compute: $3^2 = 9$, $3^3 = 27 \equiv 1 \pmod{13}$.
Wait — $3^3 = 27 = 2 \times 13 + 1 \equiv 1 \pmod{13}$! So the order of $3$ mod $13$ is $3$.
$3^9 = (3^3)^3 \equiv 1^3 = \boxed{1} \pmod{13}$.
Key insight: Fermat gives the upper bound $p - 1$ on the period. The actual period (order) may be a proper divisor of $p - 1$. Always look for shortcuts!
Example 5. Show that $n^7 - n$ is divisible by $42$ for every integer $n$.
$42 = 2 \times 3 \times 7$. We show $2$, $3$, $7$ each divide $n^7 - n = n(n^6 - 1) = n(n-1)(n^2+n+1)(n+1)(n^2-n+1)$.
Actually it's cleanest via Fermat directly:
- Mod 7: By Fermat, $n^7 \equiv n \pmod{7}$, so $7 \mid n^7 - n$.
- Mod 3: $n^3 \equiv n \pmod{3}$, so $n^7 = n \cdot (n^3)^2 \equiv n \cdot n^2 = n^3 \equiv n \pmod{3}$, so $3 \mid n^7 - n$.
- Mod 2: $n^2 \equiv n \pmod{2}$, so $n^7 = n \cdot (n^2)^3 \equiv n \cdot n^3 = n^4 \equiv n \pmod{2}$, so $2 \mid n^7 - n$.
Since $2, 3, 7$ are pairwise coprime and each divides $n^7 - n$, we get $42 \mid n^7 - n$. $\blacksquare$
4. Multiplicative Order
Definition. Let $\gcd(a, n) = 1$. The multiplicative order of $a$ modulo $n$, written $\text{ord}_n(a)$, is the smallest positive integer $k$ such that:
$$a^k \equiv 1 \pmod{n}.$$
Order Properties.
- $\text{ord}_n(a)$ always divides $\varphi(n)$ (by Euler's theorem).
- $a^m \equiv 1 \pmod{n}$ if and only if $\text{ord}_n(a) \mid m$.
- The order divides $p - 1$ when $n = p$ is prime (Fermat).
Strategy: To find $\text{ord}_n(a)$, check divisors of $\varphi(n)$ in increasing order.
Example 6. Find $\text{ord}_{11}(2)$.
$\varphi(11) = 10$. Divisors of $10$: $1, 2, 5, 10$.
$2^1 = 2 \not\equiv 1$.
$2^2 = 4 \not\equiv 1$.
$2^5 = 32 \equiv 10 \equiv -1 \not\equiv 1$.
$2^{10} \equiv (-1)^2 = 1$.
So $\text{ord}_{11}(2) = 10$. (2 is a primitive root mod 11.)
Primitive root: When $\text{ord}_p(g) = p - 1$, $g$ is called a primitive root mod $p$. Every prime $p$ has primitive roots, and they generate all non-zero residues.
5. Worked Examples
Example 7. What are the last three digits of $17^{256}$?
Last three digits means we need $17^{256} \pmod{1000}$.
$1000 = 8 \times 125$. Use CRT.
Mod 8: $17 \equiv 1 \pmod{8}$, so $17^{256} \equiv 1 \pmod{8}$.
Mod 125: $\varphi(125) = 100$. $\gcd(17, 125) = 1$.
By Euler: $17^{100} \equiv 1 \pmod{125}$.
$256 = 100 \times 2 + 56$, so $17^{256} \equiv 17^{56} \pmod{125}$.
Compute $17^{56}$ by repeated squaring:
$17^2 = 289 \equiv 39 \pmod{125}$
$17^4 \equiv 39^2 = 1521 = 12 \times 125 + 21 \equiv 21 \pmod{125}$
$17^8 \equiv 21^2 = 441 = 3 \times 125 + 66 \equiv 66 \pmod{125}$
$17^{16} \equiv 66^2 = 4356 = 34 \times 125 + 106 \equiv 106 \equiv -19 \pmod{125}$
$17^{32} \equiv (-19)^2 = 361 = 2 \times 125 + 111 \equiv 111 \equiv -14 \pmod{125}$
$17^{56} = 17^{32} \times 17^{16} \times 17^8 \equiv (-14)(-19)(66) \pmod{125}$
$(-14)(-19) = 266 = 2 \times 125 + 16 \equiv 16 \pmod{125}$
$16 \times 66 = 1056 = 8 \times 125 + 56 \equiv 56 \pmod{125}$
CRT: $x \equiv 1 \pmod{8}$ and $x \equiv 56 \pmod{125}$.
Write $x = 125k + 56$. Then $125k + 56 \equiv 1 \pmod{8}$, i.e. $5k \equiv -55 \equiv 1 \pmod{8}$.
$5^{-1} \equiv 5 \pmod{8}$ (since $5 \times 5 = 25 \equiv 1$). So $k \equiv 5 \pmod{8}$.
$x = 125(8j + 5) + 56 = 1000j + 681$.
The last three digits of $17^{256}$ are $\boxed{681}$.
6. Trick Boxes
Trick: Wilson's Theorem. For any prime $p$:
$$(p-1)! \equiv -1 \pmod{p}.$$
Use it to: Identify primes (if $n > 1$ and $(n-1)! \equiv -1 \pmod n$, then $n$ is prime), simplify factorial expressions modulo a prime.
Example: Find $20! \pmod{23}$.
$22! \equiv -1 \pmod{23}$ by Wilson. Also $22! = 22 \times 21 \times 20!$.
$22 \equiv -1$ and $21 \equiv -2 \pmod{23}$, so $22 \times 21 \equiv 2 \pmod{23}$.
Thus $2 \times 20! \equiv -1 \pmod{23}$, giving $20! \equiv -1 \times 2^{-1} \equiv -1 \times 12 \equiv -12 \equiv 11 \pmod{23}$.
Trick: Last Digit Cycles. Powers of any integer $a$ are eventually periodic mod $10$.
| Last digit of $a$ | Cycle of last digits | Period |
|---|
| $1$ | $1, 1, 1, \ldots$ | $1$ |
| $2$ | $2, 4, 8, 6, 2, 4, 8, 6, \ldots$ | $4$ |
| $3$ | $3, 9, 7, 1, 3, 9, 7, 1, \ldots$ | $4$ |
| $4$ | $4, 6, 4, 6, \ldots$ | $2$ |
| $5$ | $5, 5, 5, \ldots$ | $1$ |
| $6$ | $6, 6, 6, \ldots$ | $1$ |
| $7$ | $7, 9, 3, 1, 7, 9, 3, 1, \ldots$ | $4$ |
| $8$ | $8, 4, 2, 6, 8, 4, 2, 6, \ldots$ | $4$ |
| $9$ | $9, 1, 9, 1, \ldots$ | $2$ |
For last two digits: use $\varphi(100) = 40$ with Euler's theorem (for $\gcd(a, 10) = 1$).
7. Practice Problems
Problems are graded (warm-up) to (competition hard). Try each one before opening the answer.
P1
Compute $\varphi(36)$, $\varphi(48)$, and $\varphi(72)$.
Solution
$36 = 2^2 \times 3^2$: $\varphi(36) = \varphi(4)\varphi(9) = 2 \times 6 = \boxed{12}$.
$48 = 2^4 \times 3$: $\varphi(48) = \varphi(16)\varphi(3) = 8 \times 2 = \boxed{16}$.
$72 = 2^3 \times 3^2$: $\varphi(72) = \varphi(8)\varphi(9) = 4 \times 6 = \boxed{24}$.
P2
Find the remainder when $5^{101}$ is divided by $13$.
Solution
By Fermat: $5^{12} \equiv 1 \pmod{13}$.
$101 = 12 \times 8 + 5$, so $5^{101} \equiv 5^5 \pmod{13}$.
$5^2 = 25 \equiv 12 \equiv -1 \pmod{13}$.
$5^4 \equiv (-1)^2 = 1 \pmod{13}$.
$5^5 = 5^4 \times 5 \equiv 1 \times 5 = \boxed{5} \pmod{13}$.
P3
What is the last digit of $7^{2026}$?
Solution
Powers of $7$ cycle with period $4$: $7, 9, 3, 1, 7, 9, 3, 1, \ldots$
$2026 = 4 \times 506 + 2$, so $7^{2026}$ has the same last digit as $7^2 = 49$.
Last digit: $\boxed{9}$.
P4
Find $2^{300} \pmod{7}$.
Solution
By Fermat: $2^6 \equiv 1 \pmod{7}$.
$300 = 6 \times 50$, so $2^{300} = (2^6)^{50} \equiv 1^{50} = \boxed{1} \pmod{7}$.
P5
Find $\text{ord}_{13}(2)$.
Solution
$\varphi(13) = 12$. Divisors of $12$: $1, 2, 3, 4, 6, 12$.
$2^1 = 2$, $2^2 = 4$, $2^3 = 8$, $2^4 = 16 \equiv 3$, $2^6 = 64 \equiv 12 \equiv -1 \pmod{13}$.
Since $2^6 \equiv -1$, $2^{12} \equiv 1$ but $2^6 \not\equiv 1$.
None of $2^1, 2^2, 2^3, 2^4, 2^6 \equiv 1$, so $\text{ord}_{13}(2) = \boxed{12}$.
$2$ is a primitive root mod $13$.
P6
Show that $n^5 \equiv n \pmod{5}$ for every integer $n$.
Solution
This is the $a^p \equiv a \pmod{p}$ form of Fermat's Little Theorem with $p = 5$.
Direct proof: If $5 \nmid n$, then $n^{5-1} = n^4 \equiv 1 \pmod{5}$, so $n^5 \equiv n \pmod{5}$.
If $5 \mid n$, then both sides are $\equiv 0 \pmod{5}$.
Both cases give $n^5 \equiv n \pmod{5}$. $\blacksquare$
P7
Find the last two digits of $3^{100}$.
Solution
Need $3^{100} \pmod{100}$. Use CRT with $100 = 4 \times 25$.
Mod 4: $3 \equiv -1 \pmod{4}$, so $3^{100} \equiv (-1)^{100} = 1 \pmod{4}$.
Mod 25: $\varphi(25) = 20$. By Euler: $3^{20} \equiv 1 \pmod{25}$.
$100 = 20 \times 5$, so $3^{100} = (3^{20})^5 \equiv 1 \pmod{25}$.
CRT: $x \equiv 1 \pmod{4}$ and $x \equiv 1 \pmod{25}$.
Since $\gcd(4, 25) = 1$: $x \equiv 1 \pmod{100}$.
Last two digits of $3^{100}$: $\boxed{01}$.
P8
Using Wilson's Theorem, find $15! \pmod{17}$.
Solution
$17$ is prime, so $16! \equiv -1 \pmod{17}$ (Wilson).
$16! = 16 \times 15!$. Now $16 \equiv -1 \pmod{17}$.
$(-1) \times 15! \equiv -1 \pmod{17}$
$15! \equiv 1 \pmod{17}$, so $15! \equiv \boxed{1} \pmod{17}$.
P9
Find the remainder when $\underbrace{111\cdots1}_{100 \text{ ones}}$ is divided by $41$.
Solution
The repunit $R_{100} = \frac{10^{100} - 1}{9}$. We need $R_{100} \pmod{41}$.
First, $\gcd(9, 41) = 1$, so $R_{100} \equiv 9^{-1}(10^{100} - 1) \pmod{41}$.
Find $10^{100} \pmod{41}$: $\varphi(41) = 40$. By Fermat: $10^{40} \equiv 1 \pmod{41}$.
$100 = 40 \times 2 + 20$, so $10^{100} \equiv 10^{20} \pmod{41}$.
$10^2 = 100 \equiv 18$, $10^4 \equiv 18^2 = 324 = 7 \times 41 + 37 \equiv 37 \equiv -4$.
$10^8 \equiv 16$, $10^{16} \equiv 256 = 6 \times 41 + 10 \equiv 10$.
$10^{20} = 10^{16} \times 10^4 \equiv 10 \times (-4) = -40 \equiv 1 \pmod{41}$.
So $10^{100} \equiv 1 \pmod{41}$, meaning $10^{100} - 1 \equiv 0 \pmod{41}$.
$R_{100} = \frac{10^{100}-1}{9} \equiv \frac{0}{9} \equiv \boxed{0} \pmod{41}$.
(More precisely: $41 \mid 10^{100} - 1$, so $41 \times 9 \mid 9(10^{100}-1)$... we need $41 \mid R_{100}$.)
Since $41 \mid 10^{100} - 1$ and $\gcd(9, 41) = 1$, we get $41 \mid R_{100}$. Remainder is $\boxed{0}$.
P10
Find all primes $p$ such that $p \mid 2^p + 1$.
Solution
By Fermat's Little Theorem, $2^{p-1} \equiv 1 \pmod p$ for prime $p \neq 2$.
So $2^p = 2^{p-1} \times 2 \equiv 2 \pmod p$.
Thus $2^p + 1 \equiv 3 \pmod p$.
For $p \mid 2^p + 1$, we need $p \mid 3$, so $p = 3$.
Check $p = 2$: $2^2 + 1 = 5$. $2 \nmid 5$.
Check $p = 3$: $2^3 + 1 = 9 = 3 \times 3$. $3 \mid 9$.
The only prime is $p = \boxed{3}$.
P11
Prove that $\varphi(n) \ge \sqrt{n/2}$ for all $n \ge 1$.
Solution
It suffices to show $\varphi(n)^2 \ge n/2$, i.e. $2\varphi(n)^2 \ge n$.
Write $n = 2^{a_0} p_1^{a_1} \cdots p_k^{a_k}$ (odd primes $p_i$). Then:
$$\varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right).$$
We bound each factor: $(1 - 1/p) \ge 1/\sqrt{p}$ is
not quite right...
A cleaner approach: Since $\varphi(n) \ge \sqrt{n}$ fails for $n = 2$ (where $\varphi(2) = 1 < \sqrt{2}$), we use the weaker bound.
For $n = p^k$: $\varphi(p^k) = p^{k-1}(p-1) \ge p^{k-1} \ge \sqrt{p^k}/\sqrt{p} \cdot \sqrt{p-1}$...
Key cases:
- If $n = 1$: $\varphi(1) = 1 \ge \sqrt{1/2}$ .
- If $n = 2^a$: $\varphi(2^a) = 2^{a-1} \ge \sqrt{2^a/2} = 2^{(a-1)/2}$. This holds iff $2^{a-1} \ge 2^{(a-1)/2}$, i.e. $(a-1) \ge (a-1)/2$ for $a \ge 1$.
- If $n$ has an odd prime factor $p$: $\varphi(n) \ge \varphi(p) \cdot \ldots \ge (p-1)(\ldots) \ge \frac{p-1}{p} \cdot \frac{n}{2}$ ... the full proof uses $\prod (1 - 1/p_i) \ge 1/\sqrt{2n}$.
(Full proof by induction or via multiplicativity is standard; this gives the key ideas.) $\blacksquare$
P12
(Competition) Find the last three digits of $7^{9999}$.
Solution
Need $7^{9999} \pmod{1000}$. Use CRT: $1000 = 8 \times 125$.
Mod 8: $7 \equiv -1 \pmod{8}$, so $7^{9999} \equiv (-1)^{9999} = -1 \equiv 7 \pmod{8}$.
Mod 125: $\varphi(125) = 100$. $9999 = 100 \times 99 + 99$, so $7^{9999} \equiv 7^{99} \pmod{125}$.
Compute by squaring: $7^2 = 49$, $7^4 = 2401 = 19 \times 125 + 26 \equiv 26$,
$7^8 \equiv 26^2 = 676 = 5 \times 125 + 51 \equiv 51$,
$7^{16} \equiv 51^2 = 2601 = 20 \times 125 + 101 \equiv 101 \equiv -24$,
$7^{32} \equiv (-24)^2 = 576 = 4 \times 125 + 76 \equiv 76$,
$7^{64} \equiv 76^2 = 5776 = 46 \times 125 + 26 \equiv 26$.
$99 = 64 + 32 + 2 + 1$, so $7^{99} = 7^{64} \times 7^{32} \times 7^2 \times 7^1$.
$\equiv 26 \times 76 \times 49 \times 7 \pmod{125}$.
$26 \times 76 = 1976 = 15 \times 125 + 101 \equiv 101 \equiv -24$.
$(-24) \times 49 = -1176 = -9 \times 125 - 51 \equiv -51 \equiv 74$.
$74 \times 7 = 518 = 4 \times 125 + 18 \equiv 18$.
So $7^{9999} \equiv 18 \pmod{125}$.
CRT: $x \equiv 7 \pmod{8}$ and $x \equiv 18 \pmod{125}$.
$x = 125k + 18$. $125k + 18 \equiv 7 \pmod{8} \Rightarrow 5k + 2 \equiv 7 \Rightarrow 5k \equiv 5 \pmod{8}$.
$k \equiv 1 \pmod{8}$ (divide by $5$; $5^{-1} \equiv 5 \pmod 8$, so $k \equiv 5 \times 5 = 25 \equiv 1$).
$k = 8j + 1$, $x = 1000j + 143$.
The last three digits of $7^{9999}$ are $\boxed{143}$.
Section 1.6 Summary — Key Tools
| Tool | When to Use |
|---|
| $\varphi(p^k) = p^{k-1}(p-1)$; multiplicative | Computing totient for any $n$ |
| Euler: $a^{\varphi(n)} \equiv 1 \pmod{n}$ (if $\gcd(a,n)=1$) | Reducing large powers mod $n$ |
| Fermat: $a^{p-1} \equiv 1 \pmod{p}$ ($p$ prime, $p\nmid a$) | Powers mod a prime |
| Multiplicative order $\text{ord}_n(a)$: divides $\varphi(n)$ | Finding exact period; $a^m \equiv 1$ iff $\text{ord}\mid m$ |
| Wilson: $(p-1)! \equiv -1 \pmod{p}$ | Factorials mod prime, primality characterisation |
| Last digits: period 4 for $a \in \{2,3,7,8\}$ | Last digit / last two digits problems |
| CRT + Euler: break $1000 = 8 \times 125$ | Last three digits of large powers |