Back to Contents

Chapter 1: Number Theory

Section 1.4 — Modular Arithmetic | AIMO Training Programme
In this section:
  1. 1.3 Review — Guided Problem Walkthroughs
  2. Congruence: Definition & Basic Properties
  3. Arithmetic of Congruences
  4. Warning: Division in Modular Arithmetic
  5. Using Mod to Test Divisibility
  6. Worked Examples
  7. Trick Box: Fermat's Little Theorem
  8. Trick Box: Last Digits
  9. Practice Problems (12 problems, graded difficulty)

0. Section 1.3 Review — Guided Problem Walkthroughs

Four problems revisiting GCD & LCM from Section 1.3. Try each step before opening the hint.

Review 1   Use the Euclidean algorithm to compute $\gcd(546, 234)$.

Key skills: Euclidean algorithm — repeated division
  1. First division. Compute $546 \div 234$ and find the remainder.
    Check
    $546 = 2 \times 234 + 78$. So $\gcd(546, 234) = \gcd(234, 78)$.
  2. Continue. Compute $234 \div 78$.
    Check
    $234 = 3 \times 78 + 0$. Remainder is $0$, so $\gcd(234, 78) = 78$.
  3. Conclude.
    Check
    $\gcd(546, 234) = \boxed{78}$.
    Verify: $546 = 78 \times 7$, $234 = 78 \times 3$, and $\gcd(7, 3) = 1$.
Review 2   Two numbers have $\gcd = 15$ and $\text{lcm} = 630$. If one number is $90$, find the other.

Key skills: The identity $\gcd(a,b) \times \text{lcm}(a,b) = ab$
  1. Apply the identity. $15 \times 630 = 90 \times b$.
    Check
    $b = \dfrac{15 \times 630}{90} = \dfrac{9450}{90} = 105$.
  2. Verify. Check $\gcd(90, 105) = 15$ and $\text{lcm}(90, 105) = 630$.
    Check
    $90 = 2 \times 3^2 \times 5$, $105 = 3 \times 5 \times 7$.
    $\gcd = 3 \times 5 = 15$ . $\text{lcm} = 2 \times 3^2 \times 5 \times 7 = 630$ . Answer: $\boxed{105}$.
Review 3   How many ordered pairs $(a, b)$ of positive integers satisfy $\gcd(a, b) = 6$ and $\text{lcm}(a, b) = 180$?

Key skills: The substitution $a = dm$, $b = dn$, $\gcd(m,n) = 1$; counting coprime factorisations
  1. Set up. Let $a = 6m$, $b = 6n$ with $\gcd(m,n) = 1$. Then $\text{lcm}(a,b) = 6mn = 180$, so $mn = ?$
    Check
    $mn = 30 = 2 \times 3 \times 5$.
  2. Count coprime pairs. Since $30 = 2 \times 3 \times 5$ is squarefree, each prime goes entirely to $m$ or $n$. How many ways?
    Check
    $3$ primes, each assigned to $m$ or $n$: $2^3 = 8$ ordered pairs.
    $(m,n) \in \{(1,30),(2,15),(3,10),(5,6),(6,5),(10,3),(15,2),(30,1)\}$.
  3. Answer.
    Check
    $\boxed{8}$ ordered pairs.
Review 4   Prove that for all positive integers $a, b$: $$\text{lcm}(a, b) = \frac{ab}{\gcd(a,b)}.$$ Then use this to show: if $\gcd(a, b) = 1$, then $\gcd(a, bc) = \gcd(a, c)$.

Key skills: Bézout's identity; fundamental GCD-LCM relationship
  1. Part 1. Let $d = \gcd(a,b)$, $a = dp$, $b = dq$, $\gcd(p,q) = 1$. Show $\text{lcm}(a,b) = dpq = ab/d$.
    Check
    $dpq$ is divisible by $a = dp$ and $b = dq$. If $m$ is any common multiple of $a$ and $b$, then $dp \mid m$ and $dq \mid m$. Write $m = dpk$; then $dq \mid dpk$ gives $q \mid pk$. Since $\gcd(p,q) = 1$, $q \mid k$, so $m \ge dpq$. Thus $\text{lcm} = dpq = \frac{d^2pq}{d} = \frac{ab}{d}$. ∎
  2. Part 2. Assume $\gcd(a,b) = 1$. By Bézout, $\exists\, x,y$ with $ax + by = 1$. Multiply by $c$: $acx + bcy = c$. Now consider any $d$ dividing both $a$ and $bc$...
    Check
    Let $d \mid a$ and $d \mid c$. Then $d \mid a$ and $d \mid bc$ (since $d \mid c$ implies $d \mid bc$). So every common divisor of $(a,c)$ divides $(a, bc)$.
    Conversely, let $d \mid a$ and $d \mid bc$. From $ax + by = 1$, multiply by $c$: $acx + bcy = c$. Since $d \mid a$ (hence $d \mid ac$) and $d \mid bc$, we get $d \mid c$.
    So common divisors of $(a,bc)$ = common divisors of $(a,c)$, hence $\gcd(a,bc) = \gcd(a,c)$. ∎
Takeaway: The identity $\gcd(a, bc) = \gcd(a, c)$ when $\gcd(a,b)=1$ is extremely powerful. It says: if $a$ is coprime to $b$, then $b$ is "invisible" to $a$ in any product. This is the key to many simplifications in number theory.
Pattern Summary from 1.3 Review
Problem TypeFirst MoveKey Tool
Compute $\gcd$ of specific numbersEuclidean algorithmRepeated division
Given $\gcd$ and $\text{lcm}$, find a numberUse $\gcd \times \text{lcm} = ab$Direct computation
Count pairs with given $\gcd$ & $\text{lcm}$$a = dm, b = dn$, $\gcd(m,n)=1$Count coprime factorisations of $\text{lcm}/\gcd$
Prove GCD identityBézout's identity or prime factorisationManipulate linear combinations

1. Congruence: Definition & Basic Properties

Definition. Let $m$ be a positive integer. We say $a$ is congruent to $b$ modulo $m$, written $$a \equiv b \pmod{m},$$ if $m \mid (a - b)$, i.e., $a - b$ is a multiple of $m$.

Equivalently: $a$ and $b$ have the same remainder when divided by $m$.
Examples.
Think of $\pmod{m}$ as a "clock with $m$ hours". On a mod-$m$ clock, the numbers $0, 1, 2, \ldots, m-1$ are the only positions. Every integer maps to exactly one position (its remainder mod $m$). Two numbers are congruent iff they land on the same position.

2. Arithmetic of Congruences

Theorem (Addition & Subtraction). If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then: $$a + c \equiv b + d \pmod{m} \qquad \text{and} \qquad a - c \equiv b - d \pmod{m}.$$
Theorem (Multiplication). If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then: $$ac \equiv bd \pmod{m}.$$
Theorem (Powers). If $a \equiv b \pmod{m}$, then for any positive integer $n$: $$a^n \equiv b^n \pmod{m}.$$

Proof sketch (Multiplication): $ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d)$. Since $m \mid (a-b)$ and $m \mid (c-d)$, we get $m \mid (ac - bd)$. The power rule follows by repeated application. ∎

Quick Calculations.

3. Warning: Division in Modular Arithmetic

Warning. You cannot simply "divide both sides" of a congruence.

Counterexample: $6 \equiv 0 \pmod{6}$. Dividing both sides by $2$: $3 \equiv 0 \pmod{6}$? False!

Correct rule: If $ca \equiv cb \pmod{m}$ and $\gcd(c, m) = 1$, then $a \equiv b \pmod{m}$.

More generally: if $ca \equiv cb \pmod{m}$ and $d = \gcd(c, m)$, then $a \equiv b \pmod{m/d}$.
Example. $12 \equiv 6 \pmod{6}$. We can write this as $2 \times 6 \equiv 2 \times 3 \pmod{6}$. Here $\gcd(2, 6) = 2$, so we can only conclude $6 \equiv 3 \pmod{3}$, i.e. $0 \equiv 0 \pmod{3}$.

But: $15 \equiv 35 \pmod{10}$, i.e. $5 \times 3 \equiv 5 \times 7 \pmod{10}$. Since $\gcd(5, 10) = 5$, we get $3 \equiv 7 \pmod{2}$, i.e. both are odd.
Safe division rule: You can cancel $c$ from $ca \equiv cb \pmod{m}$ only when $\gcd(c, m) = 1$. When in doubt, don't divide — multiply instead.

4. Using Mod to Test Divisibility

Strategy: Divisibility via Remainders
To prove "$m \mid f(n)$ for all $n$", show $f(n) \equiv 0 \pmod{m}$. Common moduli and what they detect:
ModWhat it detectsKey facts
$2$Even/odd$n \equiv 0$ or $1$
$3$ or $9$Digit sum divisibility$10 \equiv 1 \pmod{9}$, so $n \equiv$ digit sum $\pmod{9}$
$4$Last two digits$100 \equiv 0 \pmod{4}$
$5$ or $10$Last digit$10 \equiv 0 \pmod{5}$
$7$No simple digit ruleCompute directly or use $10^6 \equiv 1 \pmod{7}$
$11$Alternating digit sum$10 \equiv -1 \pmod{11}$
Example. Is $123456789$ divisible by $9$? By $11$?

Mod 9: Digit sum $= 1+2+3+4+5+6+7+8+9 = 45 \equiv 0 \pmod{9}$. Yes!

Mod 11: Alternating sum $= 9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5 \not\equiv 0 \pmod{11}$. No.

5. Worked Examples

Worked Example 1. Find $2^{100} \bmod 7$.
Method: Repeated squaring (find the cycle).

Compute powers of $2$ mod $7$:
$2^1 \equiv 2$,   $2^2 \equiv 4$,   $2^3 \equiv 8 \equiv 1 \pmod{7}$.

The cycle length is $3$: $2^3 \equiv 1 \pmod{7}$.
$100 = 3 \times 33 + 1$, so $2^{100} = (2^3)^{33} \times 2^1 \equiv 1^{33} \times 2 = \boxed{2} \pmod{7}$.

Verification: $2^6 = 64 = 63 + 1 \equiv 1 \pmod{7}$ (consistent with cycle length $3$, since $3 \mid 6$).
Worked Example 2. Prove that $n^3 - n$ is divisible by $6$ for every integer $n$.
Method: Show $2 \mid (n^3 - n)$ and $3 \mid (n^3 - n)$ separately, then use $\gcd(2,3)=1$.

Mod 2: Either $n \equiv 0$ or $n \equiv 1 \pmod{2}$. Mod 3: $n \equiv 0, 1,$ or $2 \pmod{3}$. Since $2 \mid (n^3 - n)$ and $3 \mid (n^3 - n)$ and $\gcd(2,3) = 1$, we conclude $6 \mid (n^3 - n)$. ∎

Alternative (elegant): $n^3 - n = n(n-1)(n+1) = (n-1) \cdot n \cdot (n+1)$, the product of three consecutive integers. Any three consecutive integers include a multiple of $2$ and a multiple of $3$, so the product is divisible by $6$.
Worked Example 3. (AIMO style) Find the remainder when $1! + 2! + 3! + \cdots + 100!$ is divided by $12$.
Key observation: For $n \ge 4$, $n!$ contains the factor $4 \times 3 = 12$, so $n! \equiv 0 \pmod{12}$.

Therefore: $$\sum_{k=1}^{100} k! \equiv 1! + 2! + 3! \pmod{12} = 1 + 2 + 6 = 9.$$
Answer: $\boxed{9}$.

Check: $4! = 24 \equiv 0 \pmod{12}$ . $5! = 120 \equiv 0 \pmod{12}$ . All higher factorials are divisible by $12$.

6. Trick Box: Fermat's Little Theorem

Fermat's Little Theorem (FLT). If $p$ is prime and $\gcd(a, p) = 1$, then: $$a^{p-1} \equiv 1 \pmod{p}.$$ Equivalently: $a^p \equiv a \pmod{p}$ for all integers $a$ (including $a$ divisible by $p$).
Example. Find $3^{100} \bmod 7$.

Since $7$ is prime and $\gcd(3, 7) = 1$: $3^6 \equiv 1 \pmod{7}$ (FLT with $p = 7$).
$100 = 6 \times 16 + 4$, so $3^{100} = (3^6)^{16} \times 3^4 \equiv 1 \times 81 \equiv 81 \pmod{7}$.
$81 = 11 \times 7 + 4$, so $3^{100} \equiv \boxed{4} \pmod{7}$.
When to use FLT: Computing $a^n \bmod p$ where $p$ is prime and $n$ is large. Reduce the exponent: $a^n \equiv a^{n \bmod (p-1)} \pmod{p}$ (when $\gcd(a,p)=1$). This turns an enormous exponent into a small one.
Example. Find $2^{2023} \bmod 13$.

$13$ is prime, $\gcd(2, 13) = 1$, so $2^{12} \equiv 1 \pmod{13}$.
$2023 = 12 \times 168 + 7$, so $2^{2023} \equiv 2^7 = 128 \pmod{13}$.
$128 = 9 \times 13 + 11$, so $2^{2023} \equiv \boxed{11} \pmod{13}$.

7. Trick Box: Last Digits

Last Digit = mod 10. Last Two Digits = mod 100.

To find the last digit of $a^n$: compute $a^n \bmod 10$.
To find the last two digits: compute $a^n \bmod 100$.

Last-digit cycles (mod 10):
Base (mod 10)Cycle of last digitsCycle length
$0$$0, 0, 0, \ldots$$1$
$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$
Every last digit has cycle length dividing $4$. So for any base, the last digit of $a^n$ depends only on $n \bmod 4$ (with care for $n \bmod 4 = 0$).
Example. Last digit of $7^{2023}$?
Cycle for $7$: $7, 9, 3, 1$ (length $4$). $2023 = 4 \times 505 + 3$, so last digit $= 3$rd in cycle $= \boxed{3}$.
Example. Last two digits of $3^{2023}$?
We need $3^{2023} \bmod 100$. By Euler's theorem, $\phi(100) = 40$, so $3^{40} \equiv 1 \pmod{100}$ (since $\gcd(3, 100) = 1$).
$2023 = 40 \times 50 + 23$, so $3^{2023} \equiv 3^{23} \pmod{100}$.
Compute: $3^1 = 3$, $3^2 = 9$, $3^4 = 81$, $3^8 = 81^2 = 6561 \equiv 61$, $3^{16} \equiv 61^2 = 3721 \equiv 21$.
$3^{23} = 3^{16} \times 3^4 \times 3^2 \times 3^1 = 21 \times 81 \times 9 \times 3 \pmod{100}$.
$21 \times 81 = 1701 \equiv 1$. $1 \times 9 = 9$. $9 \times 3 = 27$.
Last two digits: $\boxed{27}$.

8. Practice Problems

Problems are graded to . This section is harder than previous ones — is the new baseline.

P1 Compute: (a) $247 \times 319 \pmod{6}$;   (b) $5^{20} \pmod{7}$;   (c) $11^{11} \pmod{3}$.
Solution
(a) $247 \equiv 1 \pmod{6}$, $319 \equiv 1 \pmod{6}$. So $247 \times 319 \equiv 1 \pmod{6}$.

(b) $5 \equiv 5 \pmod{7}$. $5^2 = 25 \equiv 4$. $5^3 \equiv 5 \times 4 = 20 \equiv 6 \equiv -1 \pmod{7}$.
$5^6 \equiv (-1)^2 = 1 \pmod{7}$. So $5^{20} = (5^6)^3 \times 5^2 \equiv 1 \times 4 = \boxed{4} \pmod{7}$.

(c) $11 \equiv 2 \pmod{3}$. $2^2 = 4 \equiv 1 \pmod{3}$. $11 = 2 \times 5 + 1$, so $2^{11} = (2^2)^5 \times 2 \equiv 1 \times 2 = \boxed{2} \pmod{3}$.
P2 What is the last digit (units digit) of $9^{2024}$?
Solution
Last-digit cycle of $9$: $9, 1, 9, 1, \ldots$ (cycle length $2$).
$2024$ is even, so $9^{2024}$ has the same last digit as $9^2 = 81$.
Last digit: $\boxed{1}$.
P3 Find $7^{2023} \bmod 5$.
Solution
$7 \equiv 2 \pmod{5}$. Powers of $2$ mod $5$:
$2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 3$, $2^4 \equiv 16 \equiv 1 \pmod{5}$.
Cycle length $4$. $2023 = 4 \times 505 + 3$.
$7^{2023} \equiv 2^3 = 8 \equiv \boxed{3} \pmod{5}$.

Alternative via FLT: $5$ is prime, $\gcd(7,5)=1$, so $7^4 \equiv 1 \pmod{5}$. Same reduction.
P4 Prove that $n^2 + 3n + 1$ is odd for every integer $n$.
Solution
We work mod $2$.

Case 1: $n$ even ($n \equiv 0 \pmod{2}$):
$n^2 + 3n + 1 \equiv 0 + 0 + 1 = 1 \pmod{2}$. Odd.

Case 2: $n$ odd ($n \equiv 1 \pmod{2}$):
$n^2 + 3n + 1 \equiv 1 + 3 + 1 = 5 \equiv 1 \pmod{2}$. Odd.

In both cases $n^2 + 3n + 1 \equiv 1 \pmod{2}$, so it is always odd. ∎
P5 (AIMO style) When $3^{2024} + 5^{2024}$ is divided by $4$, what is the remainder?
Solution
$3 \equiv -1 \pmod{4}$, so $3^{2024} \equiv (-1)^{2024} = 1 \pmod{4}$.
$5 \equiv 1 \pmod{4}$, so $5^{2024} \equiv 1 \pmod{4}$.
$3^{2024} + 5^{2024} \equiv 1 + 1 = \boxed{2} \pmod{4}$.
P6 (Scaffolded) Prove that $n^5 - n$ is divisible by $30$ for every integer $n$.
  1. Factor. Show $n^5 - n = n(n^4 - 1) = n(n^2-1)(n^2+1) = (n-1)n(n+1)(n^2+1)$.
    Check
    $n^5 - n = n(n^4 - 1) = n(n^2 - 1)(n^2 + 1) = n(n-1)(n+1)(n^2+1)$.
  2. Divisibility by $2$. $(n-1)n(n+1)$ contains three consecutive integers, so $2 \mid (n^5 - n)$.
    Check
    Among any two consecutive integers, one is even. So $2 \mid n(n-1)$, hence $2 \mid (n^5-n)$.
  3. Divisibility by $3$. Among $(n-1), n, (n+1)$, one is divisible by $3$.
    Check
    Three consecutive integers always include a multiple of $3$, so $3 \mid (n-1)n(n+1) \mid (n^5-n)$.
  4. Divisibility by $5$. Check all $5$ residues mod $5$.
    Check
    $n \equiv 0$: $n^5 - n \equiv 0$.
    $n \equiv 1$: $n^5 - n \equiv 1 - 1 = 0$.
    $n \equiv 2$: $n^5 - n \equiv 32 - 2 = 30 \equiv 0$.
    $n \equiv 3$: $n^5 - n \equiv 243 - 3 = 240 \equiv 0$.
    $n \equiv 4$: $n^5 - n \equiv 1024 - 4 = 1020 \equiv 0$.
    (Or: by FLT, $n^5 \equiv n \pmod{5}$ for all $n$.)
  5. Combine. Since $2, 3, 5$ are pairwise coprime, conclude $30 \mid (n^5 - n)$.
    Check
    $2 \mid (n^5-n)$, $3 \mid (n^5-n)$, $5 \mid (n^5-n)$, and $\gcd(2,3) = \gcd(2,5) = \gcd(3,5) = 1$.
    By the coprime product divisibility rule: $2 \times 3 \times 5 = 30 \mid (n^5-n)$. ∎
P7 (Scaffolded) Find all integers $n$ with $1 \le n \le 100$ such that $n^2 \equiv 1 \pmod{24}$.
  1. Rewrite. $n^2 \equiv 1 \pmod{24}$ means $24 \mid (n^2 - 1) = (n-1)(n+1)$.
    Check
    We need $24 \mid (n-1)(n+1)$ where $24 = 8 \times 3$.
  2. Mod 3. $3 \mid (n-1)(n+1)$ iff $n \not\equiv 0 \pmod{3}$, i.e. $n \equiv 1$ or $2 \pmod{3}$.
    Check
    If $n \equiv 0 \pmod 3$: $(n-1)(n+1) \equiv (-1)(1) = -1 \equiv 2 \pmod{3}$. Not divisible.
    If $n \equiv 1$: $(0)(2) = 0$. . If $n \equiv 2$: $(1)(0) = 0$. .
    So we need $\gcd(n, 3) = 1$, i.e. $3 \nmid n$.
  3. Mod 8. Check all residues $n \bmod 8$:
    Check
    $n \equiv 0$: $(n-1)(n+1) \equiv (-1)(1) = -1 \equiv 7 \pmod{8}$.
    $n \equiv 1$: $(0)(2) = 0$.
    $n \equiv 2$: $(1)(3) = 3$.
    $n \equiv 3$: $(2)(4) = 8 \equiv 0$.
    $n \equiv 4$: $(3)(5) = 15 \equiv 7$.
    $n \equiv 5$: $(4)(6) = 24 \equiv 0$.
    $n \equiv 6$: $(5)(7) = 35 \equiv 3$.
    $n \equiv 7$: $(6)(8) = 48 \equiv 0$.
    So $n \equiv 1, 3, 5, 7 \pmod{8}$, i.e. $n$ is odd.
  4. Combine. $n$ must be odd and not divisible by $3$. By CRT (or just listing): $n \equiv 1, 5, 7, 11, 13, 17, 19, 23 \pmod{24}$, i.e. $8$ residues per period of $24$.
    Check
    In $\{1, 2, \ldots, 24\}$: odd numbers are $\{1,3,5,7,9,11,13,15,17,19,21,23\}$ (12 of them). Remove multiples of 3: $\{3, 9, 15, 21\}$ (4 removed). Leaves $8$ values: $\{1, 5, 7, 11, 13, 17, 19, 23\}$.

    In $\{1, \ldots, 100\}$: $4$ complete periods of $24$ give $4 \times 8 = 32$ values. Remaining $\{97, 98, 99, 100\}$: only $97 \equiv 1 \pmod{24}$ qualifies.
    Total: $32 + 1 = \boxed{33}$.
P8 (AIMO adapted) Find the remainder when $1^5 + 2^5 + 3^5 + \cdots + 99^5 + 100^5$ is divided by $4$.
Solution
Reduce each term mod $4$. The residues $n \bmod 4$ cycle as $1, 2, 3, 0, 1, 2, 3, 0, \ldots$ among $n = 1, 2, \ldots, 100$ (exactly $25$ complete cycles).

Fifth powers mod $4$:
$0^5 \equiv 0$, $1^5 \equiv 1$, $2^5 = 32 \equiv 0$, $3^5 = 243 \equiv 3 \pmod{4}$.

In each block of $4$ consecutive integers starting at $4k+1$: the sum of fifth powers $\equiv 1 + 0 + 3 + 0 = 4 \equiv 0 \pmod{4}$.

There are $25$ such blocks ($n = 1$ to $100$), each contributing $0 \pmod{4}$.
Total $\equiv 25 \times 0 = \boxed{0} \pmod{4}$.
P9 Find the smallest positive integer $x$ satisfying the system: $$x \equiv 2 \pmod{3}, \qquad x \equiv 3 \pmod{5}, \qquad x \equiv 4 \pmod{7}.$$
Solution
Method: Chinese Remainder Theorem (construct the solution step by step).

Step 1. $x \equiv 2 \pmod{3}$, so $x = 3k + 2$ for some integer $k$.

Step 2. Substitute into $x \equiv 3 \pmod{5}$:
$3k + 2 \equiv 3 \pmod{5}$, so $3k \equiv 1 \pmod{5}$.
Multiply by $2$ (the inverse of $3$ mod $5$, since $3 \times 2 = 6 \equiv 1$): $k \equiv 2 \pmod{5}$.
So $k = 5j + 2$, hence $x = 3(5j + 2) + 2 = 15j + 8$. So $x \equiv 8 \pmod{15}$.

Step 3. Substitute into $x \equiv 4 \pmod{7}$:
$15j + 8 \equiv 4 \pmod{7}$, so $15j \equiv -4 \pmod{7}$, i.e. $j \equiv -4 \pmod{7}$ (since $15 \equiv 1 \pmod{7}$).
$j \equiv 3 \pmod{7}$, so $j = 7m + 3$.
$x = 15(7m + 3) + 8 = 105m + 53$.

Smallest positive: $\boxed{53}$.

Verify: $53 = 17 \times 3 + 2$ . $53 = 10 \times 5 + 3$ . $53 = 7 \times 7 + 4$ .
P10 (Scaffolded) Find the remainder when $2^{2023}$ is divided by $37$.
  1. Apply FLT. Since $37$ is prime and $\gcd(2, 37) = 1$, what does FLT give?
    Check
    $2^{36} \equiv 1 \pmod{37}$.
  2. Reduce the exponent. Compute $2023 \bmod 36$.
    Check
    $2023 = 36 \times 56 + 7$. So $2023 \equiv 7 \pmod{36}$.
  3. Compute $2^7 \bmod 37$.
    Check
    $2^7 = 128 = 3 \times 37 + 17$. So $2^{2023} \equiv \boxed{17} \pmod{37}$.
P11 Find the last three digits of $7^{999}$ (i.e. find $7^{999} \bmod 1000$).
[Hint: $1000 = 8 \times 125$. Use CRT: compute mod $8$ and mod $125$ separately.]
Solution
Mod 8: $7 \equiv -1 \pmod{8}$, so $7^{999} \equiv (-1)^{999} = -1 \equiv 7 \pmod{8}$.

Mod 125: $\phi(125) = 100$, so $7^{100} \equiv 1 \pmod{125}$ (Euler's theorem).
$999 = 100 \times 9 + 99$, so $7^{999} \equiv 7^{99} \pmod{125}$.

Compute $7^{99} \bmod 125$ by repeated squaring:
$7^1 = 7$
$7^2 = 49$
$7^4 = 49^2 = 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$:
$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$.
$101 \times 49 = 4949 = 39 \times 125 + 74 \equiv 74$.
$74 \times 7 = 518 = 4 \times 125 + 18 \equiv 18$.
So $7^{999} \equiv 18 \pmod{125}$.

CRT: Find $x$ with $x \equiv 7 \pmod{8}$ and $x \equiv 18 \pmod{125}$.
$x = 125k + 18$. Need $125k + 18 \equiv 7 \pmod{8}$, i.e. $5k + 2 \equiv 7 \pmod{8}$, so $5k \equiv 5 \pmod{8}$, i.e. $k \equiv 1 \pmod{8}$ (since $5 \times 5 = 25 \equiv 1 \pmod{8}$, inverse of $5$ is $5$; $5 \times 5 = 25 \equiv 1$, so $k \equiv 5 \times 5 = 25 \equiv 1 \pmod 8$).
$k = 1$: $x = 125 + 18 = 143$.

Last three digits of $7^{999}$: $\boxed{143}$.

Verify mod 8: $143 = 17 \times 8 + 7$ . Mod 125: $143 = 1 \times 125 + 18$ .
P12 Prove: if $p$ is an odd prime, then $1^2 + 2^2 + 3^2 + \cdots + (p-1)^2 \equiv 0 \pmod{p}$.
[Hint: Pair $k$ with $p - k$.]
Solution
Method 1 (Pairing).
Note that $k^2 \equiv (p-k)^2 \pmod{p}$, since $(p-k)^2 = p^2 - 2pk + k^2 \equiv k^2 \pmod{p}$.

So we can pair the terms: $\{1, p-1\}$, $\{2, p-2\}$, $\ldots$, $\{(p-1)/2, (p+1)/2\}$.
There are $(p-1)/2$ such pairs, and each pair contributes $k^2 + k^2 = 2k^2$ to the sum.

$$S = \sum_{k=1}^{p-1} k^2 = 2 \sum_{k=1}^{(p-1)/2} k^2.$$
Method 2 (Formula). Use the closed form: $$S = \sum_{k=1}^{p-1} k^2 = \frac{(p-1)p(2p-1)}{6}.$$
We need to show $p \mid S$. Since $p$ appears as a factor in the numerator: $S = \frac{(p-1) \cdot p \cdot (2p-1)}{6}$.
So $S/p = \frac{(p-1)(2p-1)}{6}$. We need this to be an integer (which it is, as the formula always gives integers), and then $p \mid S$ follows immediately since $S = p \cdot \frac{(p-1)(2p-1)}{6}$.

Why is $\frac{(p-1)(2p-1)}{6}$ an integer? $(p-1)(2p-1)$: since $p$ is odd, $p - 1$ is even, so $2 \mid (p-1)$. Also, among $p-1$ and $2p-1$, one is divisible by $3$:
• If $p \equiv 1 \pmod{3}$: $p - 1 \equiv 0 \pmod{3}$.
• If $p \equiv 2 \pmod{3}$: $2p - 1 \equiv 4 - 1 = 3 \equiv 0 \pmod{3}$.
• If $p = 3$: $(p-1)(2p-1) = 2 \times 5 = 10$, and $10/6$ is... not an integer? But $S = 1 + 4 = 5$, and $3 \nmid 5$?

Wait — let's check $p = 3$: $S = 1^2 + 2^2 = 1 + 4 = 5$. Is $3 \mid 5$? No!

So the statement is false for $p = 3$. Let me re-examine...

Actually, $S = \frac{(p-1)p(2p-1)}{6}$. For $p = 3$: $\frac{2 \times 3 \times 5}{6} = 5$. Indeed $3 \nmid 5$.

The correct statement requires $p \ge 5$ (or $p > 3$). For $p \ge 5$: $p$ is coprime to $6$ (since $p$ is prime and $p \ge 5$), so $6 \mid (p-1)(2p-1)$ is what we need. As shown above: $2 \mid (p-1)$ and $3 \mid (p-1)(2p-1)$ when $p \ne 3$.

Corrected conclusion: For any prime $p \ge 5$: $$1^2 + 2^2 + \cdots + (p-1)^2 = \frac{(p-1)p(2p-1)}{6} = p \cdot \frac{(p-1)(2p-1)}{6} \equiv 0 \pmod{p}. \quad\square$$ For $p = 3$, the sum is $5 \not\equiv 0 \pmod 3$. So the result holds for all odd primes $p \ge 5$.

Lesson: Always test small cases! A pairing argument alone doesn't immediately give divisibility — you need to verify the formula.
Section 1.4 Summary — Key Tools
ToolWhen to Use
$a \equiv b \pmod{m}$ means $m \mid (a-b)$Foundation of all modular problems
Add / multiply congruences freelySimplify expressions mod $m$
$a^n \bmod m$: find the cycleCompute remainders of large powers
FLT: $a^{p-1} \equiv 1 \pmod{p}$Reduce huge exponents when mod is prime
Last digit = mod 10, last two digits = mod 100"Find the last $k$ digits" problems
Check cases mod $m$ for small $m$Prove divisibility / parity results
CRT: solve $x \equiv a_i \pmod{m_i}$Systems of congruences with coprime moduli
No division unless $\gcd(c,m) = 1$Avoid the most common modular error
← Section 1.3: GCD & LCM Contents Section 1.5: Linear Congruences →