Back to Contents

Chapter 1: Number Theory

Section 1.5 — Linear Congruences | AIMO Training Programme
In this section:
  1. 1.4 Review — Guided Problem Walkthroughs
  2. Linear Congruences: $ax \equiv b \pmod{m}$
  3. Modular Inverse
  4. Multiple Solutions
  5. Chinese Remainder Theorem (CRT)
  6. Practice Problems (12 problems, graded difficulty)

0. Section 1.4 Review — Guided Problem Walkthroughs

Before we begin linear congruences, let's revisit key ideas from 1.4 and earlier sections with some new challenges.

Review 1   Let $S$ be the set of all positive integers $n$ such that $\gcd(n, 360) = 30$ and $n \le 720$. Find $|S|$ and the sum of all elements of $S$.

Key skills: Coprime decomposition + systematic counting
  1. Set up. If $\gcd(n, 360) = 30$, write $n = 30k$. What condition must $k$ satisfy in terms of $\gcd(k, ?)$? What is the range for $k$?
    Hint
    $360 = 30 \times 12$. So $\gcd(30k, 30 \times 12) = 30 \cdot \gcd(k, 12) = 30$, meaning $\gcd(k, 12) = 1$.
    Also $30k \le 720$ gives $k \le 24$.
  2. Count. List all $k \le 24$ with $\gcd(k, 12) = 1$. Use the fact that $12 = 2^2 \times 3$, so $k$ must be coprime to both 2 and 3.
    Hint
    Among $1$ to $12$: coprime to $12$ are $\{1, 5, 7, 11\}$, so $\varphi(12) = 4$.
    Among $13$ to $24$: same pattern shifted by $12$: $\{13, 17, 19, 23\}$.
    Total: $|S| = 8$.
  3. Sum. The qualifying $n$ values are $30k$ for each valid $k$. Compute the sum.
    Hint
    $k \in \{1, 5, 7, 11, 13, 17, 19, 23\}$. Sum of $k$'s $= 1+5+7+11+13+17+19+23 = 96$.
    Sum of $n$'s $= 30 \times 96 = 2880$.
    Answer: $|S| = 8$, sum $= 2880$.
Review 2   Find the remainder when $7^{100}$ is divided by $48$.

Key skills: Euler's theorem + order finding
  1. Check applicability. Is $\gcd(7, 48) = 1$? Compute $\varphi(48)$.
    Hint
    $\gcd(7, 48) = 1$ . $48 = 2^4 \times 3$, so $\varphi(48) = 48(1-\tfrac{1}{2})(1-\tfrac{1}{3}) = 16$.
    By Euler's theorem: $7^{16} \equiv 1 \pmod{48}$.
  2. Reduce the exponent. Write $100 = 16q + r$. What is $r$?
    Hint
    $100 = 16 \times 6 + 4$, so $7^{100} \equiv 7^4 \pmod{48}$.
  3. Compute $7^4 \pmod{48}$.
    Hint
    $7^2 = 49 \equiv 1 \pmod{48}$. So $7^4 = (7^2)^2 \equiv 1^2 = 1 \pmod{48}$.
    Answer: The remainder is $\mathbf{1}$.
    Note: The actual order of $7$ mod $48$ is $2$, much smaller than $\varphi(48) = 16$!
Review 3   Find all pairs $(a, b)$ of positive integers with $a < b$ such that $\gcd(a, b) = a - b + 11$ and $\text{lcm}(a, b) = 120$.

Key skills: Combining GCD/LCM identities with Diophantine reasoning
  1. Use the identity. Recall $\gcd(a,b) \cdot \text{lcm}(a,b) = ab$. Let $d = \gcd(a,b) = a - b + 11$. Express $ab$ in terms of $d$.
    Hint
    $ab = d \times 120 = 120(a - b + 11)$. Also $d \mid a$ and $d \mid b$.
  2. Set up. Write $a = dm$, $b = dn$, $\gcd(m,n) = 1$, $mn = 120/d$. Also $d = dm - dn + 11$, giving $d(m - n - 1) = -11$.
    Hint
    Since $d > 0$ and $11$ is prime: either $d = 1, m - n - 1 = -11$ or $d = 11, m - n - 1 = -1$.
    Case 1: $d = 1$, $m - n = -10$, $mn = 120$. Need $n - m = 10$ and $mn = 120$ with $\gcd(m,n) = 1$.
    Case 2: $d = 11$, $m - n = 0$, i.e. $m = n$. But $\gcd(m,n) = 1$ forces $m = n = 1$, then $\text{lcm} = 11 \neq 120$.
  3. Solve Case 1. $n = m + 10$, $m(m+10) = 120$, so $m^2 + 10m - 120 = 0$. Check $\gcd(m, m+10) = 1$.
    Hint
    Discriminant: $100 + 480 = 580$. $\sqrt{580} \approx 24.08$, not an integer.
    No solution! Wait — we assumed $a < b$, so $dm < dn$, meaning $m < n$. Re-check with $d(1 - m + n) = 11$.
    Correcting: $d = a - b + 11$ with $a < b$ means $d < 11$. So $d \in \{1, 2, 3, 4, 5, 6, 8, 10\}$ (divisors of 120 less than 11).
    Systematically check: $d = 1: mn = 120, n - m + 1 = 11/1$... This requires careful case analysis.
    Answer: $(a, b) = (8, 120)$ with $d = \gcd(8, 120) = 8$ and $8 - 120 + 11 = -101 \neq 8$. No valid pairs exist — this is a trick question that tests careful verification!
Quick Reference from Sections 1.1–1.4
ConceptKey FormulaWhen to Use
GCD/LCM identity$\gcd(a,b) \cdot \text{lcm}(a,b) = ab$Any problem linking gcd and lcm
Coprime decomp.$a = dm,\; b = dn,\; \gcd(m,n) = 1$When $\gcd(a,b) = d$ is given
Euler's totient$\varphi(p^k) = p^{k-1}(p-1)$; multiplicativeCounting coprimes, reducing powers
Euler's theorem$a^{\varphi(m)} \equiv 1 \pmod{m}$Large powers mod $m$
Fermat's Little$a^{p-1} \equiv 1 \pmod{p}$Large powers mod prime $p$

1. Linear Congruences: $ax \equiv b \pmod{m}$

Definition. A linear congruence is an equation of the form $$ax \equiv b \pmod{m}$$ where $a, b, m$ are given integers ($m > 0$) and $x$ is the unknown.

This means: find all integers $x$ such that $m \mid (ax - b)$.
Theorem (Existence of Solutions). The congruence $ax \equiv b \pmod{m}$ has a solution if and only if $$d = \gcd(a, m) \mid b.$$ When solutions exist:
Example 1. Solve $3x \equiv 7 \pmod{10}$.
Step 1: Check solvability. $\gcd(3, 10) = 1$, and $1 \mid 7$. Unique solution mod $10$.

Step 2: Find the solution. We need $3x \equiv 7 \pmod{10}$. Try $x = 0, 1, 2, \ldots, 9$:
$3 \times 9 = 27 \equiv 7 \pmod{10}$.

Answer: $x \equiv \boxed{9} \pmod{10}$.

Alternative: Multiply both sides by the inverse of $3$ mod $10$. Since $3 \times 7 = 21 \equiv 1 \pmod{10}$, the inverse of $3$ is $7$. So $x \equiv 7 \times 7 = 49 \equiv 9 \pmod{10}$.
No solution example: $6x \equiv 5 \pmod{9}$. Here $\gcd(6, 9) = 3$ but $3 \nmid 5$. No solution exists!

2. Modular Inverse

Definition. The modular inverse of $a$ modulo $m$, written $a^{-1} \pmod{m}$, is an integer $x$ such that $$ax \equiv 1 \pmod{m}.$$ It exists if and only if $\gcd(a, m) = 1$.
Three Methods to Find $a^{-1} \pmod{m}$.
  1. Trial (small $m$): Test $x = 1, 2, \ldots, m-1$ until $ax \equiv 1$.
  2. Extended Euclidean Algorithm: Find $x, y$ with $ax + my = 1$ (Bézout). Then $x$ is the inverse.
  3. Euler's Theorem: If $\gcd(a, m) = 1$, then $a^{\varphi(m)} \equiv 1 \pmod{m}$, so $a^{-1} \equiv a^{\varphi(m)-1} \pmod{m}$.
Example 2. Find the inverse of $7$ modulo $11$.
Method 1 (Trial): $7 \times 1 = 7$, $7 \times 2 = 14 \equiv 3$, $7 \times 3 = 21 \equiv 10$, $7 \times 4 = 28 \equiv 6$, $7 \times 5 = 35 \equiv 2$, $7 \times 6 = 42 \equiv 9$, $7 \times 7 = 49 \equiv 5$, $7 \times 8 = 56 \equiv 1$.

So $7^{-1} \equiv \boxed{8} \pmod{11}$.

Method 2 (Extended Euclidean):
$11 = 1 \times 7 + 4$
$7 = 1 \times 4 + 3$
$4 = 1 \times 3 + 1$
Back-substitute: $1 = 4 - 1 \times 3 = 4 - 1 \times (7 - 4) = 2 \times 4 - 7 = 2(11 - 7) - 7 = 2 \times 11 - 3 \times 7$.
So $(-3) \times 7 \equiv 1 \pmod{11}$, i.e. $7^{-1} \equiv -3 \equiv 8 \pmod{11}$.

Method 3 (Euler/Fermat): $11$ is prime, so $7^{-1} \equiv 7^{11-2} = 7^9 \pmod{11}$.
$7^2 = 49 \equiv 5$, $7^4 \equiv 25 \equiv 3$, $7^8 \equiv 9$, $7^9 = 7^8 \times 7 \equiv 9 \times 7 = 63 \equiv 8 \pmod{11}$.
Using the inverse to solve: Once you know $a^{-1} \pmod{m}$, solving $ax \equiv b \pmod{m}$ is immediate: $x \equiv a^{-1} \cdot b \pmod{m}$.

3. Multiple Solutions

Theorem. If $d = \gcd(a, m)$ and $d \mid b$, then $ax \equiv b \pmod{m}$ has exactly $d$ solutions modulo $m$.

Method: Divide everything by $d$: solve $\dfrac{a}{d} \cdot x \equiv \dfrac{b}{d} \pmod{\dfrac{m}{d}}$. This gives one solution $x_0$. The $d$ solutions mod $m$ are: $$x_0, \quad x_0 + \frac{m}{d}, \quad x_0 + \frac{2m}{d}, \quad \ldots, \quad x_0 + \frac{(d-1)m}{d}.$$
Example 3. Solve $6x \equiv 4 \pmod{10}$.
Step 1: $d = \gcd(6, 10) = 2$. Check: $2 \mid 4$ . So there are $2$ solutions mod $10$.

Step 2: Divide by $2$: $3x \equiv 2 \pmod{5}$.
$\gcd(3, 5) = 1$, so unique solution mod $5$. Trial: $3 \times 4 = 12 \equiv 2 \pmod{5}$.
So $x_0 = 4$.

Step 3: The two solutions mod $10$ are: $$x \equiv 4 \pmod{10} \quad \text{and} \quad x \equiv 4 + 5 = 9 \pmod{10}.$$
Verify: $6 \times 4 = 24 \equiv 4 \pmod{10}$ . $6 \times 9 = 54 \equiv 4 \pmod{10}$ .
Answer: $x \equiv \boxed{4 \text{ or } 9} \pmod{10}$.

4. Chinese Remainder Theorem (CRT)

Chinese Remainder Theorem. If $m_1, m_2, \ldots, m_k$ are pairwise coprime (i.e. $\gcd(m_i, m_j) = 1$ for $i \ne j$), then 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$.
Example 4. Find $x$ if $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$.
Step-by-step substitution method:

Step 1: From the first congruence: $x = 3k + 2$ for some integer $k$.

Step 2: Substitute into the second: $3k + 2 \equiv 3 \pmod{5}$, so $3k \equiv 1 \pmod{5}$.
The inverse of $3$ mod $5$ is $2$ (since $3 \times 2 = 6 \equiv 1$). So $k \equiv 2 \pmod{5}$.

Step 3: $k = 5j + 2$, so $x = 3(5j + 2) + 2 = 15j + 8$.

Answer: $x \equiv \boxed{8} \pmod{15}$.

Verify: $8 = 2 \times 3 + 2$ . $8 = 1 \times 5 + 3$ .
CRT in practice: For two congruences, the substitution method is fastest. Write $x = m_1 k + a_1$, substitute into the second equation, solve for $k$, then express $x$.
Example 5 (Three congruences). Find the smallest positive $x$ with $x \equiv 1 \pmod{2}$, $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$.
Step 1: $x = 2k + 1$ (odd).
Step 2: $2k + 1 \equiv 2 \pmod{3} \Rightarrow 2k \equiv 1 \pmod{3} \Rightarrow k \equiv 2 \pmod{3}$ (since $2^{-1} \equiv 2 \pmod{3}$).
So $k = 3j + 2$, $x = 2(3j+2)+1 = 6j + 5$. Thus $x \equiv 5 \pmod{6}$.
Step 3: $6j + 5 \equiv 3 \pmod{5} \Rightarrow 6j \equiv -2 \equiv 3 \pmod{5} \Rightarrow j \equiv 3 \pmod{5}$ (since $6 \equiv 1 \pmod{5}$).
So $j = 5m + 3$, $x = 6(5m+3)+5 = 30m + 23$.

Smallest positive: $x = \boxed{23}$.
Verify: $23$ is odd , $23 = 7 \times 3 + 2$ , $23 = 4 \times 5 + 3$ .

5. Practice Problems

12 problems, graded from to .

P1 Solve $5x \equiv 3 \pmod{7}$.
Solution
$\gcd(5, 7) = 1$, so unique solution mod $7$.
Trial: $5 \times 2 = 10 \equiv 3 \pmod{7}$.
Answer: $x \equiv \boxed{2} \pmod{7}$.

Or: $5^{-1} \equiv 3 \pmod{7}$ (since $5 \times 3 = 15 \equiv 1$). So $x \equiv 3 \times 3 = 9 \equiv 2 \pmod{7}$.
P2 Solve $4x \equiv 6 \pmod{14}$.
Solution
$d = \gcd(4, 14) = 2$. Check: $2 \mid 6$ . Two solutions mod $14$.
Divide by $2$: $2x \equiv 3 \pmod{7}$. $\gcd(2,7) = 1$.
$2^{-1} \equiv 4 \pmod{7}$ (since $2 \times 4 = 8 \equiv 1$). So $x \equiv 4 \times 3 = 12 \equiv 5 \pmod{7}$.
Two solutions mod $14$: $x \equiv 5$ and $x \equiv 5 + 7 = 12 \pmod{14}$.

Verify: $4 \times 5 = 20 \equiv 6 \pmod{14}$ . $4 \times 12 = 48 \equiv 6 \pmod{14}$ .
Answer: $x \equiv \boxed{5 \text{ or } 12} \pmod{14}$.
P3 Find the inverse of $13$ modulo $20$.
Solution
We need $13x \equiv 1 \pmod{20}$. $\gcd(13, 20) = 1$ .

Extended Euclidean:
$20 = 1 \times 13 + 7$
$13 = 1 \times 7 + 6$
$7 = 1 \times 6 + 1$
Back-substitute: $1 = 7 - 6 = 7 - (13 - 7) = 2 \times 7 - 13 = 2(20 - 13) - 13 = 2 \times 20 - 3 \times 13$.
So $(-3) \times 13 \equiv 1 \pmod{20}$, i.e. $13^{-1} \equiv -3 \equiv \boxed{17} \pmod{20}$.

Verify: $13 \times 17 = 221 = 11 \times 20 + 1 \equiv 1 \pmod{20}$ .
P4 Determine whether $9x \equiv 12 \pmod{15}$ has solutions. If so, find all solutions modulo $15$.
Solution
$d = \gcd(9, 15) = 3$. Check: $3 \mid 12$ . Three solutions mod $15$.
Divide by $3$: $3x \equiv 4 \pmod{5}$. $\gcd(3,5)=1$.
$3^{-1} \equiv 2 \pmod{5}$. So $x \equiv 2 \times 4 = 8 \equiv 3 \pmod{5}$.
Three solutions mod $15$: $x \equiv 3, 8, 13 \pmod{15}$.

Verify: $9 \times 3 = 27 \equiv 12$ . $9 \times 8 = 72 \equiv 12$ . $9 \times 13 = 117 \equiv 12$ .
Answer: $x \equiv \boxed{3, 8, \text{ or } 13} \pmod{15}$.
P5 Using Euler's theorem, find $3^{-1} \pmod{40}$.
Solution
$\gcd(3, 40) = 1$ . $\varphi(40) = 40(1 - \tfrac{1}{2})(1 - \tfrac{1}{5}) = 16$.
By Euler's theorem: $3^{16} \equiv 1 \pmod{40}$, so $3^{-1} \equiv 3^{15} \pmod{40}$.

Compute by repeated squaring:
$3^2 = 9$, $3^4 = 81 \equiv 1 \pmod{40}$.
Oh! $3^4 \equiv 1 \pmod{40}$. So $3^{-1} \equiv 3^3 = 27 \pmod{40}$.

Verify: $3 \times 27 = 81 = 2 \times 40 + 1 \equiv 1 \pmod{40}$ .
Answer: $3^{-1} \equiv \boxed{27} \pmod{40}$.
P6 (Scaffolded) Solve the system: $x \equiv 3 \pmod{4}$ and $x \equiv 5 \pmod{7}$.
  1. Express $x$ from the first congruence.
    Hint
    $x = 4k + 3$ for some integer $k$.
  2. Substitute into the second congruence and solve for $k$.
    Hint
    $4k + 3 \equiv 5 \pmod{7} \Rightarrow 4k \equiv 2 \pmod{7}$.
    $4^{-1} \equiv 2 \pmod{7}$ (since $4 \times 2 = 8 \equiv 1$). So $k \equiv 2 \times 2 = 4 \pmod{7}$.
  3. Write the final answer.
    Hint
    $k = 7j + 4$, so $x = 4(7j + 4) + 3 = 28j + 19$.
    $x \equiv \boxed{19} \pmod{28}$.
    Verify: $19 = 4 \times 4 + 3$ . $19 = 2 \times 7 + 5$ .
P7 (AIMO style) A number leaves remainder $2$ when divided by $3$, remainder $3$ when divided by $5$, and remainder $2$ when divided by $7$. What is the smallest such positive number?
Solution
System: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.

Step 1: $x = 3k + 2$. Substitute: $3k + 2 \equiv 3 \pmod{5} \Rightarrow 3k \equiv 1 \pmod{5} \Rightarrow k \equiv 2 \pmod{5}$.
So $k = 5j + 2$, $x = 15j + 8$.

Step 2: $15j + 8 \equiv 2 \pmod{7} \Rightarrow 15j \equiv -6 \pmod{7} \Rightarrow j \equiv -6 \pmod{7}$ (since $15 \equiv 1 \pmod{7}$).
$j \equiv 1 \pmod{7}$. So $j = 7m + 1$, $x = 15(7m + 1) + 8 = 105m + 23$.

Smallest positive: $\boxed{23}$.
Verify: $23 = 7 \times 3 + 2$ , $23 = 4 \times 5 + 3$ , $23 = 3 \times 7 + 2$ .
P8 (Scaffolded) Find all $x$ with $0 \le x < 30$ satisfying $10x \equiv 20 \pmod{30}$.
  1. Check solvability. $d = \gcd(10, 30) = ?$ Does $d \mid 20$?
    Hint
    $d = 10$. $10 \mid 20$ . So there are $10$ solutions mod $30$.
  2. Simplify. Divide by $10$: what reduced congruence do you get?
    Hint
    $x \equiv 2 \pmod{3}$.
  3. List all solutions.
    Hint
    $x \equiv 2 \pmod{3}$, so $x \in \{2, 5, 8, 11, 14, 17, 20, 23, 26, 29\}$.
    That's $\boxed{10}$ solutions: all numbers $\equiv 2 \pmod{3}$ in $\{0, 1, \ldots, 29\}$.
P9 If $a \equiv 3 \pmod{7}$ and $ab \equiv 1 \pmod{7}$, find $b \pmod{7}$.
Solution
We need $3b \equiv 1 \pmod{7}$.
$3 \times 5 = 15 \equiv 1 \pmod{7}$. So $b \equiv \boxed{5} \pmod{7}$.
P10 (AIMO adapted) Find the smallest positive integer $n$ such that $n \equiv 1 \pmod{2}$, $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{5}$, and $n \equiv 4 \pmod{7}$.
Solution
Notice: $n \equiv -1 \pmod{2}$, $n \equiv -1 \pmod{3}$, $n \equiv -2 \pmod{5}$, $n \equiv -3 \pmod{7}$.
Hmm, not all $-1$. Let's just solve step by step.

Step 1: $n$ is odd. $n = 2k + 1$.
Step 2: $2k + 1 \equiv 2 \pmod{3} \Rightarrow 2k \equiv 1 \pmod{3} \Rightarrow k \equiv 2 \pmod{3}$. So $k = 3j + 2$, $n = 6j + 5$.
Step 3: $6j + 5 \equiv 3 \pmod{5} \Rightarrow j \equiv -2 \equiv 3 \pmod{5}$. So $j = 5i + 3$, $n = 30i + 23$.
Step 4: $30i + 23 \equiv 4 \pmod{7} \Rightarrow 2i + 2 \equiv 4 \pmod{7} \Rightarrow 2i \equiv 2 \pmod{7} \Rightarrow i \equiv 1 \pmod{7}$.
So $i = 7m + 1$, $n = 210m + 53$.

Smallest positive: $\boxed{53}$.
Verify: $53$ odd , $53 = 17 \times 3 + 2$ , $53 = 10 \times 5 + 3$ , $53 = 7 \times 7 + 4$ .
P11 (Scaffolded) Solve $17x \equiv 13 \pmod{100}$ using the Extended Euclidean Algorithm.
  1. Verify solvability. $\gcd(17, 100) = ?$
    Hint
    $100 = 5 \times 17 + 15$, $17 = 1 \times 15 + 2$, $15 = 7 \times 2 + 1$. So $\gcd(17, 100) = 1$. Unique solution.
  2. Back-substitute to find $17^{-1} \pmod{100}$.
    Hint
    $1 = 15 - 7 \times 2 = 15 - 7(17 - 15) = 8 \times 15 - 7 \times 17 = 8(100 - 5 \times 17) - 7 \times 17$
    $= 8 \times 100 - 47 \times 17$.
    So $(-47) \times 17 \equiv 1 \pmod{100}$. $17^{-1} \equiv -47 \equiv 53 \pmod{100}$.
  3. Solve. $x \equiv 53 \times 13 \pmod{100}$.
    Hint
    $53 \times 13 = 689 \equiv 89 \pmod{100}$.
    $x \equiv \boxed{89} \pmod{100}$.
    Verify: $17 \times 89 = 1513 = 15 \times 100 + 13 \equiv 13 \pmod{100}$ .
P12 (Competition) There are between $100$ and $200$ students in a school. When they line up in rows of $3$, $1$ is left over. In rows of $5$, $3$ are left over. In rows of $7$, $2$ are left over. How many students are there?
Solution
System: $n \equiv 1 \pmod{3}$, $n \equiv 3 \pmod{5}$, $n \equiv 2 \pmod{7}$.

Step 1: $n = 3k + 1$. $3k + 1 \equiv 3 \pmod{5} \Rightarrow 3k \equiv 2 \pmod{5}$.
$3^{-1} \equiv 2 \pmod{5}$, so $k \equiv 4 \pmod{5}$. $k = 5j + 4$, $n = 15j + 13$.

Step 2: $15j + 13 \equiv 2 \pmod{7} \Rightarrow j + 6 \equiv 2 \pmod{7} \Rightarrow j \equiv 3 \pmod{7}$.
$j = 7m + 3$, $n = 105m + 58$.

Solutions: $n = 58, 163, 268, \ldots$
In $[100, 200]$: $n = \boxed{163}$.

Verify: $163 = 54 \times 3 + 1$ , $163 = 32 \times 5 + 3$ , $163 = 23 \times 7 + 2$ .
Section 1.5 Summary — Key Tools
ToolWhen to Use
$ax \equiv b \pmod{m}$ solvable iff $\gcd(a,m) \mid b$First check before solving any linear congruence
Modular inverse $a^{-1}$: exists when $\gcd(a,m)=1$Solve $ax \equiv b$ via $x \equiv a^{-1}b$
Extended Euclidean AlgorithmFind inverse for larger moduli
Euler/Fermat: $a^{-1} \equiv a^{\varphi(m)-1}$Alternative inverse method (good for prime $m$)
$d = \gcd(a,m) > 1$: divide by $d$, get $d$ solutionsMultiple-solution cases
CRT: solve systems with coprime moduliStep-by-step substitution method
Always verify your answer!Plug back into the original congruence(s)
← Section 1.4: Modular Arithmetic Contents Section 1.6: Fermat & Euler →