Chapter 1: Number Theory
Section 1.7 — Chinese Remainder Theorem | AIMO Training Programme
0. Section 1.6 Review — Guided Problem Walkthroughs
Four scaffolded problems revisiting Fermat's Little Theorem and Euler's Theorem from Section 1.6.
Review 1 Find the remainder when $11^{200}$ is divided by $6$.
Key skills: Euler's theorem — computing $\varphi(6)$ and reducing the exponent.
- Check and compute $\varphi(6)$. Is $\gcd(11, 6) = 1$? Find $\varphi(6)$.
Check
$\gcd(11, 6) = 1$ . $6 = 2 \times 3$, so $\varphi(6) = \varphi(2)\varphi(3) = 1 \times 2 = 2$.
- Apply Euler. Use $11^{\varphi(6)} \equiv 1 \pmod{6}$ to simplify $11^{200}$.
Check
$11^2 \equiv 1 \pmod{6}$. $200 = 2 \times 100$, so $11^{200} = (11^2)^{100} \equiv 1^{100} = 1 \pmod{6}$.
- Sanity check. $11 \equiv 5 \equiv -1 \pmod{6}$, so $11^{200} \equiv (-1)^{200} = 1 \pmod{6}$.
Check
Both methods agree: $11^{200} \equiv \boxed{1} \pmod{6}$. The "shortcut" (replacing $11$ with its residue) works equally well here.
Review 2 Find all primes $p$ such that $p \mid 5^p - 5$.
Key skills: Fermat's Little Theorem — the $a^p \equiv a \pmod p$ form.
- Apply the theorem. What does Fermat's Little Theorem tell us about $5^p \pmod p$?
Hint
By Fermat: $5^p \equiv 5 \pmod{p}$ for every prime $p$.
Therefore $5^p - 5 \equiv 0 \pmod{p}$, meaning $p \mid 5^p - 5$ for every prime $p$.
- Conclude. What is the set of all such primes?
Check
All primes $p$ satisfy $p \mid 5^p - 5$. This is exactly Fermat's Little Theorem: $a^p \equiv a \pmod p$ for any integer $a$ and prime $p$.
Review 3 Find the last two digits of $3^{400}$.
Key skills: Euler's theorem with modulus $100 = 4 \times 25$.
- Use Euler mod 100. Find $\varphi(100)$ and reduce $3^{400}$.
Hint
$\varphi(100) = \varphi(4)\varphi(25) = 2 \times 20 = 40$.
$400 = 40 \times 10$, so $3^{400} = (3^{40})^{10} \equiv 1^{10} = 1 \pmod{100}$.
- Last two digits. $3^{400} \equiv 1 \pmod{100}$ means the last two digits are $01$.
Check
Last two digits: $\boxed{01}$. Note this matches the pattern $3^{40} \equiv 1 \pmod{100}$ and $400 = 40 \times 10$.
Review 4 Show that if $p$ is an odd prime and $a \not\equiv \pm 1 \pmod p$, then the order of $a$ mod $p$ is at least $3$.
Key skills: Multiplicative order and its properties.
- What orders are possible? The order divides $p - 1$. If $\text{ord}_p(a) = 1$, what does that mean?
Hint
$\text{ord}_p(a) = 1 \Rightarrow a^1 \equiv 1 \pmod p \Rightarrow a \equiv 1 \pmod p$.
- What if order is 2? $a^2 \equiv 1 \pmod p$ means $p \mid a^2 - 1 = (a-1)(a+1)$. Since $p$ is prime, what follows?
Hint
$p \mid (a-1)(a+1)$ and $p$ prime $\Rightarrow$ $p \mid a-1$ or $p \mid a+1$, i.e. $a \equiv 1$ or $a \equiv -1 \pmod p$.
- Conclude. If $a \not\equiv \pm 1 \pmod p$, why must $\text{ord}_p(a) \ge 3$?
Check
Order 1 forces $a \equiv 1$, and order 2 forces $a \equiv \pm 1$ — both are excluded by hypothesis.
So the order cannot be $1$ or $2$, meaning $\text{ord}_p(a) \ge 3$. $\blacksquare$
1. CRT: Statement & Theorem
Chinese Remainder Theorem (CRT). Let $m_1, m_2, \ldots, m_k$ be pairwise coprime positive integers (i.e. $\gcd(m_i, m_j) = 1$ for $i \neq j$). Then for any integers $a_1, a_2, \ldots, a_k$, the system
$$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$$
has a unique solution modulo $M = m_1 m_2 \cdots m_k$.
CRT tells us that when moduli are pairwise coprime, we can always combine any collection of remainders into a unique residue class. This is an incredibly powerful tool in competition mathematics.
Historical note: The CRT dates back to Sun Tzu's Mathematical Classic (3rd–5th century AD). The original problem: "Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7." Answer: $23$.
2. Why CRT Works (Constructive Proof)
The proof is constructive — it gives an explicit formula for the solution.
Construction. Let $M = m_1 m_2 \cdots m_k$ and $M_i = M / m_i$ (the product of all moduli except $m_i$).
Since $\gcd(M_i, m_i) = 1$ (as $m_i$ does not appear in $M_i$), the inverse $y_i \equiv M_i^{-1} \pmod{m_i}$ exists.
The unique solution is:
$$x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 + \cdots + a_k M_k y_k \pmod{M}.$$
Why this works: For each term $a_i M_i y_i$:
- When reduced mod $m_i$: $M_i y_i \equiv M_i \cdot M_i^{-1} \equiv 1 \pmod{m_i}$, so the $i$-th term contributes $a_i$.
- When reduced mod $m_j$ ($j \neq i$): $m_j \mid M_i$ (since $m_j$ is a factor of $M_i$), so the term is $\equiv 0 \pmod{m_j}$.
So the sum gives the correct remainder for each modulus. $\square$
Example 1. Solve: $x \equiv 3 \pmod{5}$ and $x \equiv 1 \pmod{7}$.
$M = 35$, $M_1 = 7$, $M_2 = 5$.
$y_1 = 7^{-1} \pmod 5$: $7 \equiv 2 \pmod 5$, $2^{-1} \equiv 3 \pmod 5$ (since $2 \times 3 = 6 \equiv 1$). So $y_1 = 3$.
$y_2 = 5^{-1} \pmod 7$: $5 \times 3 = 15 \equiv 1 \pmod 7$. So $y_2 = 3$.
$$x \equiv 3 \times 7 \times 3 + 1 \times 5 \times 3 = 63 + 15 = 78 \equiv 78 - 2 \times 35 = 8 \pmod{35}.$$
Answer: $x \equiv 8 \pmod{35}$.
Verify: $8 = 1 \times 5 + 3 \equiv 3 \pmod 5$ $8 = 1 \times 7 + 1 \equiv 1 \pmod 7$
Step-by-step substitution (simpler for 2–3 moduli): Write $x = m_1 k + a_1$, substitute into the next equation, solve for $k$, and continue. This avoids computing inverses explicitly. Both methods work — use whichever feels natural.
4. CRT Applications
4.1 Computing Large Powers mod Composite Numbers
CRT turns one hard computation (mod large $n$) into several easier ones (mod prime powers).
Example 2. Find $5^{100} \pmod{21}$.
$21 = 3 \times 7$. Compute separately:
Mod 3: $5 \equiv 2 \pmod 3$. $2^2 = 4 \equiv 1$, so $5^{100} \equiv 2^{100} = (2^2)^{50} \equiv 1 \pmod 3$.
Mod 7: $\varphi(7) = 6$. $100 = 6 \times 16 + 4$. $5^{100} \equiv 5^4 \pmod 7$.
$5^2 = 25 \equiv 4 \pmod 7$. $5^4 \equiv 16 \equiv 2 \pmod 7$.
CRT: $x \equiv 1 \pmod 3$, $x \equiv 2 \pmod 7$.
$x = 3k + 1$, $3k + 1 \equiv 2 \pmod 7$, $3k \equiv 1 \pmod 7$. $3^{-1} \equiv 5 \pmod 7$, so $k \equiv 5$, $x = 15 + 1 = 16$.
$5^{100} \equiv \boxed{16} \pmod{21}$.
4.2 Counting Problems
CRT gives a bijection between $\mathbb{Z}/M\mathbb{Z}$ and $\mathbb{Z}/m_1\mathbb{Z} \times \cdots \times \mathbb{Z}/m_k\mathbb{Z}$ (when the moduli are coprime). This is powerful for counting.
Example 3. How many integers from $1$ to $420$ are divisible by neither $3$ nor $5$ nor $7$?
$420 = 3 \times 4 \times 5 \times 7$. We want $|\{n \le 420 : \gcd(n, 105) = 1\}|$ (noting $105 = 3 \times 5 \times 7$).
Actually: integers coprime to $3 \times 5 \times 7 = 105$ in $\{1, \ldots, 420\}$.
By multiplicativity: in $\{1, \ldots, 105\}$ there are $\varphi(105) = \varphi(3)\varphi(5)\varphi(7) = 2 \times 4 \times 6 = 48$ such integers.
In $\{1, \ldots, 420\} = 4$ complete cycles of $105$: there are $4 \times 48 = \boxed{192}$ integers.
5. Worked Examples
Example 4 (Three Moduli). Find the smallest positive integer $x$ such that:
$$x \equiv 3 \pmod 4, \quad x \equiv 5 \pmod 9, \quad x \equiv 1 \pmod{11}.$$
Moduli $4, 9, 11$ are pairwise coprime. $M = 4 \times 9 \times 11 = 396$.
Step-by-step substitution:
$x = 4k + 3$. Substitute into second: $4k + 3 \equiv 5 \pmod 9$, so $4k \equiv 2 \pmod 9$.
$4^{-1} \pmod 9$: $4 \times 7 = 28 \equiv 1 \pmod 9$, so $4^{-1} \equiv 7$. Then $k \equiv 7 \times 2 = 14 \equiv 5 \pmod 9$.
$k = 9j + 5$, so $x = 36j + 23$.
Substitute into third: $36j + 23 \equiv 1 \pmod{11}$. $36 \equiv 3$ and $23 \equiv 1 \pmod{11}$.
$3j + 1 \equiv 1 \pmod{11}$, so $3j \equiv 0 \pmod{11}$. Since $\gcd(3,11)=1$: $j \equiv 0 \pmod{11}$.
$j = 11m$, $x = 396m + 23$.
Smallest positive: $x = \boxed{23}$.
Verify: $23 = 5 \times 4 + 3$ , $23 = 2 \times 9 + 5$ , $23 = 2 \times 11 + 1$ .
Example 5 (Reconstruction). A number $N$ satisfies $0 < N < 1000$. We know $N \equiv 7 \pmod{8}$ and $N \equiv 3 \pmod{125}$. Find $N$.
$8 \times 125 = 1000$, so solution is unique mod $1000$.
$x = 125k + 3$. Substitute: $125k + 3 \equiv 7 \pmod 8$. $125 \equiv 5 \pmod 8$, so $5k \equiv 4 \pmod 8$.
$5^{-1} \equiv 5 \pmod 8$ (since $25 \equiv 1$). $k \equiv 5 \times 4 = 20 \equiv 4 \pmod 8$.
$k = 8j + 4$, $x = 1000j + 503$.
Since $0 < N < 1000$: $N = \boxed{503}$.
6. Beyond Coprime Moduli
General Case. The system $x \equiv a \pmod m$, $x \equiv b \pmod n$ (with possibly $\gcd(m,n) > 1$) has solutions if and only if $\gcd(m, n) \mid (a - b)$.
When solutions exist, they are unique modulo $\text{lcm}(m, n)$.
Example 6. Solve: $x \equiv 5 \pmod{12}$ and $x \equiv 2 \pmod{8}$.
$\gcd(12, 8) = 4$. Check: $4 \mid (5 - 2) = 3$? No, $4 \nmid 3$.
No solution exists.
The system is inconsistent — for instance, $x \equiv 5 \pmod{12}$ implies $x$ is odd (since $5$ is odd and $12$ is even), while $x \equiv 2 \pmod 8$ implies $x$ is even. Contradiction!
Example 7. Solve: $x \equiv 7 \pmod{12}$ and $x \equiv 3 \pmod{8}$.
$\gcd(12, 8) = 4$. Check: $4 \mid (7 - 3) = 4$? Yes . Solutions exist, unique mod $\text{lcm}(12, 8) = 24$.
$x = 12k + 7$. Then $12k + 7 \equiv 3 \pmod 8$, so $4k \equiv -4 \equiv 4 \pmod 8$.
Divide by $4$: $k \equiv 1 \pmod 2$. So $k$ is odd: $k = 2j + 1$.
$x = 24j + 19$.
Answer: $x \equiv 19 \pmod{24}$. Verify: $19 = 1 \times 12 + 7$ , $19 = 2 \times 8 + 3$ .
7. Practice Problems
Problems are graded (warm-up) to (competition hard). Try each one before opening the answer.
P1
Find the smallest positive integer $x$ such that $x \equiv 2 \pmod{3}$ and $x \equiv 4 \pmod{5}$.
Solution
$x = 3k + 2$. $3k + 2 \equiv 4 \pmod 5 \Rightarrow 3k \equiv 2 \pmod 5$.
$3^{-1} \equiv 2 \pmod 5$ (since $6 \equiv 1$). $k \equiv 4 \pmod 5$.
$k = 5j + 4$, $x = 15j + 14$.
Smallest positive: $x = \boxed{14}$.
Verify: $14 = 4(3) + 2 \equiv 2 \pmod 3$ , $14 = 2(5) + 4 \equiv 4 \pmod 5$ .
P2
What is the unique solution mod $35$ to: $x \equiv 1 \pmod{5}$ and $x \equiv 6 \pmod{7}$?
Solution
$x = 5k + 1$. $5k + 1 \equiv 6 \pmod 7 \Rightarrow 5k \equiv 5 \pmod 7 \Rightarrow k \equiv 1 \pmod 7$.
$k = 7j + 1$, $x = 35j + 6$.
$x \equiv \boxed{6} \pmod{35}$.
Verify: $6 \equiv 1 \pmod 5$ , $6 \equiv 6 \pmod 7$ .
P3
A bag of marbles: when counted in groups of 4, 1 is left over; in groups of 7, 3 are left over. The bag has fewer than 50 marbles. How many?
Solution
$x \equiv 1 \pmod 4$ and $x \equiv 3 \pmod 7$.
$x = 4k + 1$. $4k + 1 \equiv 3 \pmod 7 \Rightarrow 4k \equiv 2 \pmod 7$.
$4^{-1} \equiv 2 \pmod 7$ (since $8 \equiv 1$). $k \equiv 4 \pmod 7$.
$k = 7j + 4$, $x = 28j + 17$.
Less than 50: $j = 0 \Rightarrow x = 17$; $j = 1 \Rightarrow x = 45 < 50$.
Both are valid; if exactly one answer expected: $\boxed{17}$ (or $45$).
P4
Find $x$ satisfying $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$, $x \equiv 1 \pmod{9}$. Express your answer mod $315$.
Solution
$x = 5k + 3$. $5k + 3 \equiv 2 \pmod 7 \Rightarrow 5k \equiv -1 \equiv 6 \pmod 7$.
$5^{-1} \equiv 3 \pmod 7$ (since $15 \equiv 1$). $k \equiv 18 \equiv 4 \pmod 7$.
$k = 7j + 4$, $x = 35j + 23$.
$35j + 23 \equiv 1 \pmod 9 \Rightarrow 8j + 5 \equiv 1 \Rightarrow 8j \equiv -4 \equiv 5 \pmod 9$.
$8^{-1} \equiv 8 \pmod 9$ (since $64 \equiv 1$). $j \equiv 40 \equiv 4 \pmod 9$.
$j = 9m + 4$, $x = 315m + 163$.
$x \equiv \boxed{163} \pmod{315}$.
P5
Using CRT, compute $7^{100} \pmod{33}$. (Hint: $33 = 3 \times 11$.)
Solution
Mod 3: $7 \equiv 1 \pmod 3$, so $7^{100} \equiv 1 \pmod 3$.
Mod 11: $7^{10} \equiv 1 \pmod{11}$ (Fermat). $100 = 10 \times 10$, so $7^{100} \equiv 1 \pmod{11}$.
CRT: $x \equiv 1 \pmod 3$ and $x \equiv 1 \pmod{11}$.
Since $\gcd(3,11)=1$: $x \equiv 1 \pmod{33}$.
$7^{100} \equiv \boxed{1} \pmod{33}$.
P6
Determine whether the system has solutions, and if so find all solutions mod $\text{lcm}(6, 10)$:
$$x \equiv 4 \pmod 6, \quad x \equiv 8 \pmod{10}.$$
Solution
$\gcd(6, 10) = 2$. Check: $2 \mid (4 - 8) = -4$? Yes . Solutions exist, unique mod $\text{lcm}(6,10) = 30$.
$x = 6k + 4$. $6k + 4 \equiv 8 \pmod{10} \Rightarrow 6k \equiv 4 \pmod{10} \Rightarrow 3k \equiv 2 \pmod 5$.
$3^{-1} \equiv 2 \pmod 5$. $k \equiv 4 \pmod 5$.
$k = 5j + 4$, $x = 30j + 28$.
$x \equiv \boxed{28} \pmod{30}$.
Verify: $28 = 4(6) + 4 \equiv 4 \pmod 6$ ; $28 = 2(10) + 8 \equiv 8 \pmod{10}$ .
P7
Find the number of integers in $\{1, 2, \ldots, 2024\}$ that leave remainder $1$ when divided by $4$, remainder $1$ when divided by $9$, and remainder $1$ when divided by $25$.
Solution
The three conditions give $x \equiv 1 \pmod 4$, $x \equiv 1 \pmod 9$, $x \equiv 1 \pmod{25}$.
Since $4, 9, 25$ are pairwise coprime, by CRT: $x \equiv 1 \pmod{900}$ (where $900 = 4 \times 9 \times 25$).
Solutions in $\{1, \ldots, 2024\}$: $x = 1, 901, 1801$.
Check: $1801 + 900 = 2701 > 2024$ . So there are $\boxed{3}$ solutions.
P8
Sun Tzu's original problem (from the 3rd century): Find the smallest positive integer that leaves remainder $2$ when divided by $3$, remainder $3$ when divided by $5$, and remainder $2$ when divided by $7$.
Solution
$x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$.
$x = 3k + 2$. $3k + 2 \equiv 3 \pmod 5 \Rightarrow 3k \equiv 1 \pmod 5$.
$3^{-1} \equiv 2 \pmod 5$. $k \equiv 2 \pmod 5$.
$k = 5j + 2$, $x = 15j + 8$.
$15j + 8 \equiv 2 \pmod 7 \Rightarrow j + 1 \equiv 2 \pmod 7 \Rightarrow j \equiv 1 \pmod 7$.
$j = 7m + 1$, $x = 105m + 23$.
Smallest positive: $x = \boxed{23}$.
P9
A positive integer $N \le 1000$ has the property that when you multiply it by $3$, the result leaves remainder $1$ when divided by $7$, and leaves remainder $2$ when divided by $11$. Find all such $N$.
Solution
$3N \equiv 1 \pmod 7 \Rightarrow N \equiv 3^{-1} \equiv 5 \pmod 7$ (since $3 \times 5 = 15 \equiv 1$).
$3N \equiv 2 \pmod{11} \Rightarrow N \equiv 3^{-1} \times 2 \pmod{11}$.
$3^{-1} \equiv 4 \pmod{11}$ (since $12 \equiv 1$). $N \equiv 8 \pmod{11}$.
CRT: $N \equiv 5 \pmod 7$, $N \equiv 8 \pmod{11}$.
$N = 7k + 5$. $7k + 5 \equiv 8 \pmod{11} \Rightarrow 7k \equiv 3 \pmod{11}$.
$7^{-1} \equiv 8 \pmod{11}$ (since $56 \equiv 1$). $k \equiv 24 \equiv 2 \pmod{11}$.
$k = 11j + 2$, $N = 77j + 19$.
Solutions $\le 1000$: $19, 96, 173, 250, 327, 404, 481, 558, 635, 712, 789, 866, 943$. That is $\boxed{13}$ values.
P10
Find the number of integers $n$ with $1 \le n \le 2017$ such that $\gcd(n, 2017)= 1$ and $n^{2016} \equiv 1 \pmod{2017^2}$.
Note: $2017$ is prime.
Solution
Since $2017$ is prime, every $n$ with $\gcd(n, 2017) = 1$ satisfies $n^{2016} \equiv 1 \pmod{2017}$ by Fermat.
For the condition mod $2017^2$: write $n^{2016} = 1 + 2017 \cdot k$ for some integer $k$. We need $2017 \mid k$.
Using lifting the exponent (advanced): among the $\varphi(2017^2) = 2017 \times 2016$ elements of $(\mathbb Z/2017^2\mathbb Z)^*$, exactly those with $\text{ord}_{2017^2}(n) \mid 2016$ satisfy $n^{2016} \equiv 1$.
The number of solutions to $x^{2016} \equiv 1 \pmod{2017^2}$ is $\gcd(2016, 2017 \times 2016) = 2016$.
Among $\{1, \ldots, 2017\}$: since $\gcd(n, 2017) = 1$ means $n \neq 2017$, and the solutions are uniformly distributed across complete residue classes, the number of valid $n$ in $\{1, \ldots, 2016\}$ is exactly $\gcd(2016, 2016 \times 2017)/2017 = \boxed{2016}$.
(Full proof uses the fact that $(\mathbb Z/2017^2\mathbb Z)^*$ is cyclic of order $2017 \times 2016$, and a cyclic group of order $m$ has exactly $\gcd(d, m)$ solutions to $x^d = 1$.)
P11
There are $n$ students in a class. When lined up in rows of $5$, $2$ are left over. In rows of $8$, $3$ are left over. In rows of $9$, $4$ are left over. Given $200 \le n \le 400$, find $n$.
Solution
$n \equiv 2 \pmod 5$, $n \equiv 3 \pmod 8$, $n \equiv 4 \pmod 9$.
Step 1: $n = 5k + 2$. $5k + 2 \equiv 3 \pmod 8 \Rightarrow 5k \equiv 1 \pmod 8$.
$5^{-1} \equiv 5 \pmod 8$ (since $25 \equiv 1$). $k \equiv 5 \pmod 8$.
$k = 8j + 5$, $n = 40j + 27$.
Step 2: $40j + 27 \equiv 4 \pmod 9 \Rightarrow 4j \equiv -23 \equiv 4 \pmod 9 \Rightarrow j \equiv 1 \pmod 9$.
$j = 9m + 1$, $n = 360m + 67$.
In $[200, 400]$: $360(0) + 67 = 67$ (too small), $360(1) + 67 = \boxed{427}$ ... wait, $427 > 400$.
Hmm — let me re-check. $360 \times 1 + 67 = 427 > 400$. So there's no solution in $[200, 400]$?
Re-verify: $n = 67$: $67 = 13(5)+2$ , $67 = 8(8)+3$ , $67 = 7(9)+4$ .
Next: $67 + 360 = 427 > 400$. So actually there is no solution in $[200, 400]$ for this particular system.
This is a valid competition-style finding: not all systems have solutions in every range. The problem as stated has no answer, illustrating the importance of always checking!
P12
(Competition) Prove that for any $n$ pairwise coprime moduli $m_1, \ldots, m_n$ and any $a_1, \ldots, a_n$, the CRT system has exactly one solution mod $M = m_1 \cdots m_n$. Hence prove that $\varphi(M) = \varphi(m_1) \cdots \varphi(m_n)$.
Solution
Part 1 (Existence and Uniqueness).
Existence: Construct $M_i = M/m_i$, $y_i = M_i^{-1} \pmod{m_i}$ (exists since $\gcd(M_i, m_i) = 1$). Set $x = \sum_i a_i M_i y_i$. For each $j$: $M_i \equiv 0 \pmod{m_j}$ when $i \neq j$ (since $m_j \mid M_i$), and $M_j y_j \equiv 1 \pmod{m_j}$. So $x \equiv a_j \pmod{m_j}$ for all $j$.
Uniqueness: If $x, x'$ both satisfy the system, then $m_i \mid x - x'$ for all $i$. Since the $m_i$ are pairwise coprime, $M = m_1 \cdots m_n \mid x - x'$, so $x \equiv x' \pmod M$.
Part 2 ($\varphi(M) = \prod \varphi(m_i)$).
By CRT, there is a bijection: $(\mathbb Z/M\mathbb Z)^* \leftrightarrow (\mathbb Z/m_1\mathbb Z)^* \times \cdots \times (\mathbb Z/m_n\mathbb Z)^*$.
(An element of $\mathbb Z/M\mathbb Z$ is a unit iff each of its components in the product is a unit — this follows from the CRT construction.)
Therefore $\varphi(M) = |(\mathbb Z/M\mathbb Z)^*| = \prod_i |(\mathbb Z/m_i\mathbb Z)^*| = \prod_i \varphi(m_i)$. $\blacksquare$
Section 1.7 Summary — Key Tools
| Tool | When to Use |
|---|
| CRT: unique solution mod $M$ when $m_i$ pairwise coprime | Any system of congruences with coprime moduli |
| Step-by-step substitution | Easiest method for 2–3 moduli |
| Formula: $x = \sum a_i M_i y_i \pmod M$ | General/large systems; algorithmic approach |
| Non-coprime moduli: need $\gcd(m,n) \mid (a-b)$ | Consistency check before attempting to solve |
| CRT for large powers: compute mod each prime power | $a^k \pmod n$ when $n$ factors nicely |
| CRT bijection: $\varphi(m_1 m_2) = \varphi(m_1)\varphi(m_2)$ | Counting coprimes, totient multiplicativity |