Back to Contents

Chapter 1: Number Theory

Section 1.3 — GCD & LCM | AIMO Training Programme
In this section:
  1. 1.2 Review — Guided Problem Walkthroughs
  2. GCD: Definition & Basic Properties
  3. The Euclidean Algorithm
  4. Bézout's Identity
  5. LCM & the GCD–LCM Relationship
  6. Coprimality & Its Consequences
  7. Competition Strategy: GCD/LCM Toolkit
  8. Worked Examples
  9. Practice Problems (12 problems, graded difficulty)

0. Section 1.2 Review — Guided Problem Walkthroughs

Before new content, let's revisit four problems from 1.2 that use prime factorisation in different ways. Work through the guided steps to consolidate your skills.

How to Read These
Try each lettered step yourself first. Only open the hint/answer if you're stuck. The goal is to build the habit of asking yourself: "What tool fits here?"
Review 1 (1.2 P3)   How many positive divisors of $10!$ are perfect squares?

Key skills: Legendre's formula → prime factorisation of $n!$ → counting with even exponents
  1. Find the prime factorisation of $10!$. Use Legendre's formula: $v_p(n!) = \sum_{i=1}^{\infty} \lfloor n/p^i \rfloor$.
    Check
    $v_2(10!) = 5+2+1 = 8$.   $v_3(10!) = 3+1 = 4$.   $v_5(10!) = 2$.   $v_7(10!) = 1$.
    So $10! = 2^8 \times 3^4 \times 5^2 \times 7^1$.
  2. Set up the counting. A divisor $d = 2^a \times 3^b \times 5^c \times 7^e$ is a perfect square when...?
    Check
    All exponents must be even: $a, b, c, e$ all even.
  3. Count the choices. For each prime, list the valid even exponents and count.
    Check
    $a \in \{0,2,4,6,8\}$: 5 choices.   $b \in \{0,2,4\}$: 3 choices.   $c \in \{0,2\}$: 2 choices.   $e \in \{0\}$: 1 choice.
    Total: $5 \times 3 \times 2 \times 1 = 30$.
Takeaway: "Count divisors with property X" almost always reduces to "count valid exponent combinations" after prime factorisation. This is the most common application of FTA in competitions.
Review 2 (1.2 P6)   The number $2^{2025} \times 5^{2026}$ is written out in full. How many digits does it have?

Key skills: algebraic simplification → powers of 10
  1. Simplify. Rewrite $2^{2025} \times 5^{2026}$ by pairing up powers of 2 and 5.
    Check
    $2^{2025} \times 5^{2026} = 2^{2025} \times 5^{2025} \times 5 = 10^{2025} \times 5 = 5 \times 10^{2025}$.
  2. Count digits. $5 \times 10^{2025}$ is the digit 5 followed by how many zeros?
    Check
    2025 zeros. Total digits: $1 + 2025 = 2026$.
Takeaway: When you see $2^a \times 5^b$, immediately pair them into $10^{\min(a,b)}$. This converts a "how many digits" problem into trivial arithmetic. The number of digits of $N$ is $\lfloor \log_{10} N \rfloor + 1$.
Review 3 (1.2 P8)   Find the largest power of $12$ that divides $30!$.

Key skills: prime factorisation of base → Legendre's formula → bottleneck identification
  1. Factorise the base. $12 = ?$ So $12^k = ?$
    Check
    $12 = 2^2 \times 3$. So $12^k = 2^{2k} \times 3^k$.
  2. Find available exponents in $30!$. Compute $v_2(30!)$ and $v_3(30!)$.
    Check
    $v_2(30!) = 15 + 7 + 3 + 1 = 26$.   $v_3(30!) = 10 + 3 + 1 = 14$.
  3. Find the bottleneck. We need $2k \le 26$ and $k \le 14$. Which constraint is tighter?
    Check
    $2k \le 26 \Rightarrow k \le 13$. And $k \le 14$. The binding constraint is $k \le 13$.
    Answer: $12^{13}$.
Takeaway: "Largest power of $m$ dividing $n!$" is always a bottleneck problem. Factorise $m$, compute each prime's availability via Legendre, then find which prime runs out first. The bottleneck prime determines the answer.
Review 4 (1.2 P12)   Find all pairs $(a, b)$ of positive integers such that $a^2 b + a = b^3 + b$.

Key skills: rearrangement → factoring out common term → sign analysis
  1. Rearrange. Move everything to one side: $a^2 b - b^3 + a - b = 0$. Group and factor.
    Check
    $b(a^2 - b^2) + (a - b) = 0$
    $b(a-b)(a+b) + (a-b) = 0$
    $(a-b)[b(a+b) + 1] = 0$.
  2. Analyse each factor. Is $b(a+b) + 1$ ever zero for positive integers?
    Check
    $b(a+b) + 1 \ge 1 \cdot 2 + 1 = 3 > 0$ for all positive $a, b$. Never zero.
  3. Conclude. The only possibility is $a - b = 0$, i.e. $a = b$.
    Check
    All solutions: $(a, b) = (n, n)$ for any positive integer $n$. ∎
Takeaway: When an equation involves symmetric-ish expressions in $a, b$, try factoring out $(a - b)$. If the other factor is always positive (or always negative), you immediately conclude $a = b$. This "sign analysis after factoring" trick appears frequently in Diophantine problems.
Pattern Summary from 1.2 Review
Problem TypeFirst MoveKey Tool
Count divisors with a propertyPrime factorise, count valid exponentsFTA + multiplication principle
"How many digits does $N$ have?"Pair $2^a \times 5^b$ into $10^k$$\lfloor \log_{10} N \rfloor + 1$
Largest power of $m$ dividing $n!$Factorise $m$, Legendre each primeBottleneck analysis
Diophantine equationRearrange, factor out $(a-b)$Sign analysis of remaining factor

1. GCD: Definition & Basic Properties

Definition. The greatest common divisor of integers $a$ and $b$ (not both zero), written $\gcd(a, b)$, is the largest positive integer that divides both $a$ and $b$.

Convention: $\gcd(a, 0) = |a|$ for any nonzero $a$.
Example 1. $\gcd(12, 18) = 6$.   $\gcd(35, 14) = 7$.   $\gcd(17, 5) = 1$.

GCD via Prime Factorisation (Review from 1.2)

Theorem. If $a = \prod p_i^{\alpha_i}$ and $b = \prod p_i^{\beta_i}$, then: $$\gcd(a,b) = \prod p_i^{\min(\alpha_i, \beta_i)}$$

This works perfectly for small numbers. But for large numbers (e.g. $\gcd(10403, 3901)$), factorisation is slow. We need a faster method.

Key Properties of GCD

Properties.
  1. $\gcd(a, b) = \gcd(b, a)$   (commutative)
  2. $\gcd(a, b) = \gcd(a, b - a)$   (subtraction property)
  3. $\gcd(a, b) = \gcd(a, b \bmod a)$   (reduction property — the heart of Euclid's algorithm)
  4. $\gcd(a, 0) = a$
  5. $\gcd(ka, kb) = k \cdot \gcd(a, b)$ for any positive integer $k$
  6. If $d = \gcd(a, b)$, then $\gcd(a/d, \, b/d) = 1$

Property 3 is the most powerful — it lets us compute GCD without knowing the prime factorisation.

Property 6 is extremely useful: after dividing by the GCD, the quotients are always coprime. This appears constantly in competition problems about fractions, ratios, and Diophantine equations.

2. The Euclidean Algorithm

The Euclidean Algorithm. To compute $\gcd(a, b)$ with $a > b > 0$:
Repeatedly replace $(a, b)$ with $(b, \, a \bmod b)$ until the remainder is $0$. The last nonzero remainder is $\gcd(a, b)$.
Example 2. Compute $\gcd(252, 105)$. $$252 = 2 \times 105 + 42$$ $$105 = 2 \times 42 + 21$$ $$42 = 2 \times 21 + 0$$ So $\gcd(252, 105) = 21$.
Example 3. Compute $\gcd(10403, 3901)$. $$10403 = 2 \times 3901 + 2601$$ $$3901 = 1 \times 2601 + 1300$$ $$2601 = 2 \times 1300 + 1$$ $$1300 = 1300 \times 1 + 0$$ So $\gcd(10403, 3901) = 1$. They are coprime! (And we didn't need to factorise either number.)
The Euclidean algorithm is fast: it takes at most $\approx 2.4 \log_{10} \min(a,b)$ steps. For $a, b < 10^6$, that's at most ~15 divisions. In a competition, this takes under a minute by hand.

Why Does It Work?

The key insight: any common divisor of $a$ and $b$ also divides $a - qb$ (for any integer $q$). Since $a \bmod b = a - \lfloor a/b \rfloor \cdot b$, we have:

$$\{d : d \mid a \text{ and } d \mid b\} = \{d : d \mid b \text{ and } d \mid (a \bmod b)\}$$

So the set of common divisors doesn't change at each step — and therefore the greatest common divisor stays the same.

GCD of Algebraic Expressions

The Euclidean algorithm also works for algebraic expressions. This is a powerful competition technique:

Example 4. Let $a_n = 2^n - 1$. What is $\gcd(a_m, a_n)$?

Claim: $\gcd(2^m - 1, \, 2^n - 1) = 2^{\gcd(m,n)} - 1$.

Key step: If $m > n$, then $2^m - 1 = 2^n(2^{m-n} - 1) + (2^n - 1)$.
So $\gcd(2^m - 1, \, 2^n - 1) = \gcd(2^n - 1, \, 2^{m-n} - 1)$.
(We used that $\gcd(2^n - 1, \, 2^n) = 1$ since $2^n - 1$ is odd.)
This mirrors the Euclidean algorithm on the exponents! So the GCD of the exponents determines the answer.
Competition Trick. $\gcd(a^m - 1, \, a^n - 1) = a^{\gcd(m,n)} - 1$ for any integer $a \ge 2$.
This generalises to: $\gcd(a^m - b^m, \, a^n - b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)}$ when $\gcd(a, b) = 1$.
Memorise the first form — it appears in AIMO and AMO problems regularly.

3. Bézout's Identity

Theorem (Bézout's Identity). For any integers $a, b$ (not both zero), there exist integers $x, y$ such that: $$ax + by = \gcd(a, b)$$ Moreover, $\gcd(a, b)$ is the smallest positive integer expressible in this form.

This is one of the most important theorems in number theory. It says the GCD is a linear combination of $a$ and $b$.

Example 5. Find integers $x, y$ such that $252x + 105y = 21$.

Work backwards from the Euclidean algorithm (Example 2):
$21 = 105 - 2 \times 42$
$42 = 252 - 2 \times 105$
Substitute: $21 = 105 - 2(252 - 2 \times 105) = 5 \times 105 - 2 \times 252$.
So $x = -2, \, y = 5$:   $252(-2) + 105(5) = -504 + 525 = 21$.

This "back-substitution" process is called the Extended Euclidean Algorithm.

Key Consequences of Bézout

Corollary 1. $\gcd(a, b) = 1$ if and only if there exist integers $x, y$ with $ax + by = 1$.
Corollary 2. The equation $ax + by = c$ has integer solutions if and only if $\gcd(a, b) \mid c$.

Corollary 2 is the gateway to solving linear Diophantine equations — a major topic in competition maths.

Example 6. Does $15x + 21y = 100$ have integer solutions?
$\gcd(15, 21) = 3$. Does $3 \mid 100$? No. So no solution exists.

Does $15x + 21y = 99$ have integer solutions?
$3 \mid 99$? Yes. So solutions exist. Divide through by 3: $5x + 7y = 33$.
By inspection (or extended Euclidean): $5(1) + 7(4) = 33$, so $x_0 = 1, y_0 = 4$ is one solution.
General solution: $x = 1 + 7t, \, y = 4 - 5t$ for any integer $t$.
Solving $ax + by = c$:
  1. Check $\gcd(a,b) \mid c$. If not, no solution.
  2. Divide through by $\gcd(a,b)$ to get $a'x + b'y = c'$ with $\gcd(a', b') = 1$.
  3. Find one solution $(x_0, y_0)$ using the extended Euclidean algorithm (or by inspection).
  4. General solution: $x = x_0 + b't, \; y = y_0 - a't$ for integer $t$.

4. LCM & the GCD–LCM Relationship

Definition. The least common multiple of positive integers $a$ and $b$, written $\text{lcm}(a, b)$, is the smallest positive integer divisible by both $a$ and $b$.
The Fundamental Identity. $$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$ for all positive integers $a, b$.

Why? Using prime factorisations: $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$ for each prime. Multiply across all primes and you get $\gcd \times \text{lcm} = ab$.

Example 7. $\gcd(12, 18) = 6$ and $\text{lcm}(12, 18) = 36$. Check: $6 \times 36 = 216 = 12 \times 18$.
Example 8 (Competition classic). If $\gcd(a, b) = 12$ and $\text{lcm}(a, b) = 360$, find $ab$.
$ab = \gcd \times \text{lcm} = 12 \times 360 = 4320$.

LCM via Prime Factorisation

Theorem. $\text{lcm}(a,b) = \prod p_i^{\max(\alpha_i, \beta_i)}$.

LCM of More Than Two Numbers

For three or more numbers, the identity $\gcd \times \text{lcm} = ab$ does not generalise directly. Instead:

Multi-number LCM. $\text{lcm}(a, b, c) = \text{lcm}(\text{lcm}(a, b), c)$.
And $\text{lcm}(a_1, \ldots, a_n) = \prod p^{\max(\alpha_1, \ldots, \alpha_n)}$ over all primes $p$.
Example 9. $\text{lcm}(12, 15, 20)$.
$12 = 2^2 \times 3$,   $15 = 3 \times 5$,   $20 = 2^2 \times 5$.
$\text{lcm} = 2^2 \times 3 \times 5 = 60$.

5. Coprimality & Its Consequences

Definition. Integers $a$ and $b$ are coprime (or relatively prime) if $\gcd(a, b) = 1$.

Coprimality is arguably the most important concept in number theory. Here's why:

Key Properties of Coprime Integers.
  1. Euclid's Lemma (extended): If $\gcd(a, c) = 1$ and $a \mid bc$, then $a \mid b$.
  2. Bézout characterisation: $\gcd(a, b) = 1$ iff $\exists \, x, y \in \mathbb{Z}$ with $ax + by = 1$.
  3. Multiplicativity of coprime LCM: If $\gcd(a, b) = 1$, then $\text{lcm}(a, b) = ab$.
  4. CRT setup: If $\gcd(m, n) = 1$, the system $x \equiv a \pmod{m}$, $x \equiv b \pmod{n}$ always has a solution.
  5. Coprime product divisibility: If $\gcd(a, b) = 1$ and $a \mid n$ and $b \mid n$, then $ab \mid n$.

Property 5 is the one you'll use most often in competition problems. It says: if two coprime numbers both divide $n$, then their product also divides $n$. This fails spectacularly when they're not coprime: $4 \mid 12$ and $6 \mid 12$, but $24 \nmid 12$.

Example 10. Show that if $n^2$ is divisible by 12, then $n$ is divisible by 6.

$12 = 4 \times 3$ and $\gcd(4, 3) = 1$.
$4 \mid n^2 \Rightarrow 2^2 \mid n^2 \Rightarrow 2 \mid n$ (by Euclid's Lemma). So $4 \mid n^2$ means $n$ is even, so $2 \mid n$.
Actually we need more: $4 \mid n^2$ and $n$ even means $n = 2k$, so $n^2 = 4k^2$, and $4 \mid 4k^2$ always — this just says $n$ is even.
$3 \mid n^2 \Rightarrow 3 \mid n$ (since 3 is prime).
Since $\gcd(2, 3) = 1$ and $2 \mid n$ and $3 \mid n$, we get $6 \mid n$. ∎

Reducing Fractions & Ratios

Key Fact. Any fraction $\frac{a}{b}$ can be written in lowest terms as $\frac{a/d}{b/d}$ where $d = \gcd(a, b)$. The resulting numerator and denominator are coprime.

Competition problems often say "express $\frac{m}{n}$ in lowest terms and find $m + n$". This always means: divide by $\gcd(m, n)$.

6. Competition Strategy: GCD/LCM Toolkit

Decision Flowchart
  1. "Find $\gcd(a, b)$ for specific numbers" → Euclidean algorithm (fast, no factorisation needed).
  2. "Find $\gcd$ for algebraic expressions" → Use properties: $\gcd(a,b) = \gcd(a, b \bmod a)$, or the $\gcd(a^m - 1, a^n - 1)$ trick.
  3. "$\gcd(a,b) = d$ and $\text{lcm}(a,b) = l$, find..." → Use $dl = ab$. Write $a = dm$, $b = dn$ with $\gcd(m,n) = 1$ and $mn = l/d$.
  4. "Solve $ax + by = c$ in integers" → Check $\gcd(a,b) \mid c$, then extended Euclidean.
  5. "If $\gcd(a,b) = 1$, prove..." → Use Bézout ($ax + by = 1$) or Euclid's Lemma.
  6. "How many pairs $(a,b)$ with $\gcd = d$, $\text{lcm} = l$?" → Factor $l/d$, count coprime pairs $(m,n)$ with $mn = l/d$.
The $a = dm, b = dn$ Substitution. When a problem gives $\gcd(a,b) = d$, always write $a = dm$, $b = dn$ where $\gcd(m, n) = 1$. This simplifies everything:
• $\text{lcm}(a,b) = dmn$
• $ab = d^2 mn$
• The coprime condition $\gcd(m,n) = 1$ is your main constraint.

This is the single most useful substitution in GCD/LCM competition problems.

7. Worked Examples

Worked Example 1. (AIMO style) Find the number of ordered pairs $(a, b)$ of positive integers with $\gcd(a, b) = 5$ and $\text{lcm}(a, b) = 300$.
Write $a = 5m$, $b = 5n$ with $\gcd(m, n) = 1$.
$\text{lcm}(a, b) = 5mn = 300$, so $mn = 60$.
We need coprime pairs $(m, n)$ with $mn = 60 = 2^2 \times 3 \times 5$.

Since $\gcd(m, n) = 1$ and $mn = 60$, each prime power in $60$ goes entirely to $m$ or to $n$:
$2^2$ → $m$ or $n$: 2 choices.   $3$ → $m$ or $n$: 2 choices.   $5$ → $m$ or $n$: 2 choices.
$2^3 = 8$ coprime factorisations: $(1, 60), (3, 20), (4, 15), (5, 12), (12, 5), (15, 4), (20, 3), (60, 1)$.

Answer: $\boxed{8}$ ordered pairs.
Worked Example 2. Prove that $\gcd(n, n+1) = 1$ for all positive integers $n$.
Method 1 (Euclidean): $\gcd(n, n+1) = \gcd(n, 1) = 1$. ∎

Method 2 (Bézout): $1 \cdot (n+1) + (-1) \cdot n = 1$. Since $1$ is a linear combination of $n$ and $n+1$, $\gcd(n, n+1) \mid 1$, so $\gcd = 1$. ∎
Worked Example 3. (AMC/AIMO) Find $\gcd(2^{40} - 1, \, 2^{24} - 1)$.
Using our trick: $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n)} - 1$.
$\gcd(40, 24)$: $40 = 1 \times 24 + 16$, $24 = 1 \times 16 + 8$, $16 = 2 \times 8 + 0$. So $\gcd(40, 24) = 8$.
Answer: $2^8 - 1 = \boxed{255}$.
Worked Example 4. (Competition classic) Prove that for any positive integer $n$: $$\gcd\!\left(\binom{2n}{n}, \, n+1\right) = 1 \quad \Longleftrightarrow \quad n+1 \text{ is prime}.$$
($\Leftarrow$): If $n + 1 = p$ is prime, then $\binom{2n}{n} = \binom{2p-2}{p-1}$. We need $\gcd\!\left(\binom{2p-2}{p-1}, p\right) = 1$.
By Kummer's theorem, $v_p\!\left(\binom{2p-2}{p-1}\right)$ equals the number of carries when adding $p-1$ and $p-1$ in base $p$.
$p - 1$ in base $p$ is the single digit $(p-1)$. Adding: $(p-1) + (p-1) = 2p - 2$. In base $p$: $2p - 2 = 1 \cdot p + (p-2)$. One carry.
Wait — that gives $v_p = 1$, not 0. Let me reconsider...

Actually, the cleaner result is: $\frac{1}{n+1}\binom{2n}{n}$ is an integer (the $n$-th Catalan number $C_n$) if and only if... it's always an integer! But $\gcd\!\left(\binom{2n}{n}, n+1\right) = n + 1$ iff $n + 1$ divides $\binom{2n}{n}$, which always happens: $C_n = \frac{1}{n+1}\binom{2n}{n} \in \mathbb{Z}$.

The correct statement is: $(n+1) \mid \binom{2n}{n}$ always (Catalan numbers), and $(n+1)^2 \mid \binom{2n}{n}$ iff $n + 1$ is not prime. This is more subtle and beyond our current scope.

Key lesson: always verify the statement before proving it! If something feels off, test small cases.
The above "Worked Example 4" deliberately shows what happens when you try to prove a statement that needs more careful formulation. In competitions, always test with small cases first (e.g., $n = 1, 2, 3, 4, 5$) before attempting a proof.
Worked Example 5. Find all positive integers $n$ such that $\gcd(n, 36) + \text{lcm}(n, 36) = n + 36$.
Let $d = \gcd(n, 36)$, so $n = dm$, $36 = dk$ with $\gcd(m, k) = 1$ and $\text{lcm}(n, 36) = dmk$.
The equation becomes: $d + dmk = dm + dk$, i.e. $d(1 + mk) = d(m + k)$, i.e. $1 + mk = m + k$.
Rearrange: $mk - m - k + 1 = 0 \Rightarrow (m-1)(k-1) = 0$.
So $m = 1$ or $k = 1$.

$m = 1$: $n = d$ and $36 = dk$, so $n \mid 36$. All divisors of 36 work: $1, 2, 3, 4, 6, 9, 12, 18, 36$.
$k = 1$: $36 = d$ and $n = 36m$. So $36 \mid n$, i.e. $n$ is a multiple of 36: $36, 72, 108, \ldots$

Combining (removing the duplicate $n = 36$): $n \in \{1, 2, 3, 4, 6, 9, 12, 18\} \cup \{36k : k \ge 1\}$.
That is: all divisors of 36, plus all multiples of 36.

8. Practice Problems

Problems are graded (warm-up) to (competition hard). Try each one before opening the answer.

P1 Find $\gcd(252, 180)$ and $\operatorname{lcm}(252, 180)$ using prime factorisation.
Hint & Solution
$252 = 2^2 \times 3^2 \times 7$ and $180 = 2^2 \times 3^2 \times 5$.
$\gcd = 2^{\min(2,2)} \times 3^{\min(2,2)} = 2^2 \times 3^2 = \boxed{36}$.
$\operatorname{lcm} = 2^{\max(2,2)} \times 3^{\max(2,2)} \times 5^1 \times 7^1 = 4 \times 9 \times 5 \times 7 = \boxed{1260}$.

Check: $\gcd \times \operatorname{lcm} = 36 \times 1260 = 45360 = 252 \times 180$.
P2 Use the Euclidean algorithm to find $\gcd(1071, 462)$.
Hint & Solution
Apply the algorithm step by step: $$\gcd(1071, 462)$$ $1071 = 2 \times 462 + 147$, so $\gcd(1071,462) = \gcd(462,147)$.
$462 = 3 \times 147 + 21$, so $\gcd(462,147) = \gcd(147,21)$.
$147 = 7 \times 21 + 0$, so $\gcd(147,21) = \gcd(21,0) = 21$.

$\gcd(1071, 462) = \boxed{21}$.
P3 Two buses leave a terminal at the same time. Bus A departs every $36$ minutes, Bus B every $48$ minutes. After how many minutes will they next depart at the same time? How many times will this happen in the first $12$ hours?
Hint & Solution
The buses coincide every $\operatorname{lcm}(36, 48)$ minutes.
$36 = 2^2 \times 3^2$, $\quad 48 = 2^4 \times 3$.
$\operatorname{lcm} = 2^4 \times 3^2 = 144$ minutes.

In 12 hours $= 720$ minutes: they coincide $720 \div 144 = \boxed{5}$ times (at $t = 144, 288, 432, 576, 720$).
Note: the initial departure at $t=0$ is not counted as a "next" coincidence.
P4 The GCD of two positive integers is $12$ and their LCM is $360$. If one of the integers is $60$, find the other.
Hint & Solution
Use the identity $\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b$: $$12 \times 360 = 60 \times b \implies b = \frac{4320}{60} = \boxed{72}.$$ Verify: $\gcd(60, 72) = 12$ and $\operatorname{lcm}(60, 72) = 360$ .
P5 Prove that for any positive integers $a$ and $b$, $$\gcd(a, b) = \gcd(a,\, b - a).$$ Hence show that $\gcd(n^2 + n + 1,\; n + 1) = 1$ for every positive integer $n$.
Solution
Part 1. Let $d = \gcd(a, b)$. Then $d \mid a$ and $d \mid b$, so $d \mid (b - a)$. Thus $d$ is a common divisor of $a$ and $b - a$. Conversely, any common divisor of $a$ and $b - a$ also divides $a + (b-a) = b$. So the sets of common divisors are equal, and in particular the greatest is equal. $\square$

Part 2. Applying the GCD subtraction rule repeatedly: $$\gcd(n^2+n+1,\; n+1) = \gcd\!\big((n^2+n+1) - n(n+1),\; n+1\big) = \gcd(1,\; n+1) = 1.$$ (We subtracted $n$ times the second argument from the first.) $\square$
P6 Find all pairs of positive integers $(a, b)$ with $a \le b$ such that $\gcd(a,b) + \operatorname{lcm}(a,b) = 54$.
[Hint: Write $a = dm$, $b = dn$ with $\gcd(m,n)=1$.]
Hint & Solution
Let $d = \gcd(a,b)$, $a = dm$, $b = dn$ with $\gcd(m,n) = 1$ and $1 \le m \le n$.
Then $\operatorname{lcm}(a,b) = dmn$, so the equation becomes $d + dmn = 54$, i.e. $d(1 + mn) = 54$.
Factor pairs $(d, 1+mn)$ of $54 = 2 \times 3^3$:
$d$$1+mn$$mn$$(m,n)$ with $\gcd=1$$(a,b)$
15453$(1,53)$$(1,53)$
22726$(1,26)$? No, $\gcd(1,26)=1$; $(2,13)$$(2,52)$, $(4,26)$
31817$(1,17)$$(3,51)$
698$(1,8)$$(6,48)$
965$(1,5)$$(9,45)$
1832$(1,2)$$(18,36)$
2721$(1,1)$$(27,27)$
5410—invalid
All valid pairs: $(1,53),(2,52),(4,26),(3,51),(6,48),(9,45),(18,36),(27,27)$.
P7 Prove: for any positive integers $a$ and $b$, $$\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b.$$
Solution
Let $d = \gcd(a,b)$. Write $a = dp$, $b = dq$ where $\gcd(p,q) = 1$.
Then $a \times b = d^2 pq$.
We claim $\operatorname{lcm}(a,b) = dpq$. Indeed $dpq$ is a common multiple of $a = dp$ and $b = dq$. If $m$ is any common multiple, write $m = ak = dpk$; since $b = dq \mid m$, we have $dq \mid dpk$, so $q \mid pk$. Since $\gcd(p,q)=1$, we get $q \mid k$, so $m = dpk \ge dpq$. Thus $\operatorname{lcm}(a,b) = dpq$ and $$\gcd(a,b) \times \operatorname{lcm}(a,b) = d \times dpq = d^2 pq = a \times b. \quad\square$$
P8 (Scaffolded) (AIMO-style) Find all positive integers $n$ such that $n \mid (n+6)$ and $n \mid (n^2 - 12)$.
  1. Show that $n \mid (n+6)$ implies $n \mid 6$. List all positive divisors of $6$.
  2. For each candidate $n$, check whether $n \mid (n^2 - 12)$. Note $n^2 - 12 \equiv -12 \pmod{n}$.
  3. Write down all values of $n$ that satisfy both conditions.
Solution
(a) $n \mid n$ always, so $n \mid (n+6) \Rightarrow n \mid 6$. Divisors of $6$: $1, 2, 3, 6$.

(b) $n \mid (n^2 - 12) \Leftrightarrow n \mid 12$ (since $n \mid n^2$, so $n \mid n^2 - (n^2-12) = 12$). Check each: (c) All four values work. Answers: $n \in \{\boxed{1, 2, 3, 6}\}$.
P9 (Scaffolded) (Adapted from AIMO 2018) Let $\gcd(a, b) = 8$ and $\operatorname{lcm}(a, b) = 240$. How many ordered pairs $(a, b)$ of positive integers satisfy these conditions?
  1. Write $a = 8m$, $b = 8n$ with $\gcd(m, n) = 1$. What must $mn$ equal?
  2. Factorise $mn$ and list all ways to split it into coprime factors $m \le n$.
  3. Remember $(a,b)$ is ordered: count each unordered pair twice (unless $a = b$).
Solution
(a) $\operatorname{lcm}(a,b) = 8mn = 240 \Rightarrow mn = 30$.

(b) $30 = 2 \times 3 \times 5$. Coprime pairs $(m,n)$ with $m \le n$ and $mn = 30$: We need $\gcd(m,n) = 1$. Since $30 = 2 \times 3 \times 5$ is squarefree, each prime goes entirely to $m$ or $n$. Possible splits of $\{2,3,5\}$ between $m$ and $n$: So 4 unordered pairs.

(c) None has $m = n$ (since $30$ is not a perfect square). Each gives 2 ordered pairs. Total: $4 \times 2 = \boxed{8}$ ordered pairs.
P10 (AIMO 2019, adapted) Find the number of positive integers $n \le 1000$ such that $\operatorname{lcm}(n, 12) = 12n / \gcd(n,12)$.
[Source: adapted from AIMO 2019 Q3]
Hint & Solution
Let $d = \gcd(n, 12)$, $n = dm$, $12 = dk$ with $\gcd(m,k)=1$.
$\operatorname{lcm}(n,12) = dmk$ and $12n/\gcd(n,12) = 12n/d = dk \cdot dm/d = dmk$.
So the equation $\operatorname{lcm}(n,12) = 12n/\gcd(n,12)$ becomes $dmk = dmk$, which is always true!

Wait — let's re-examine. Using $\operatorname{lcm}(a,b) = ab/\gcd(a,b)$: $$\operatorname{lcm}(n,12) = \frac{12n}{\gcd(n,12)}.$$ This identity holds for all positive integers $n$. So every $n \le 1000$ works.

Answer: $\boxed{1000}$.

Lesson: The equation is just the standard identity $\operatorname{lcm}(a,b) = ab/\gcd(a,b)$ in disguise. Recognising standard identities prevents over-complicating competition problems!
P11 (Scaffolded) (AIMO 2022, adapted) Find all positive integer solutions to $$\frac{1}{x} + \frac{1}{y} = \frac{1}{12}.$$
  1. Multiply through by $12xy$ to get $12y + 12x = xy$. Rearrange to $(x-12)(y-12) = k$ for some constant $k$.
  2. List all positive factor pairs of $k$ to find valid $(x,y)$ pairs with $x \le y$.
  3. How many ordered pairs $(x,y)$ are there in total?
Solution
(a) $12y + 12x = xy \Rightarrow xy - 12x - 12y = 0 \Rightarrow (x-12)(y-12) = 144$.

(b) $144 = 2^4 \times 3^2$. The number of positive divisors of $144$ is $(4+1)(2+1) = 15$. Factor pairs $(s,t)$ with $s \le t$ and $st = 144$, giving $x = 12+s$, $y = 12+t$:
$(1,144),(2,72),(3,48),(4,36),(6,24),(8,18),(9,16),(12,12)$ — that's $8$ unordered pairs.

(c) The pair $(12,12)$ gives $x=y=24$ (one ordered pair). The other $7$ pairs each give $2$ ordered pairs. Total ordered pairs: $7 \times 2 + 1 = \boxed{15}$.

Key insight: The factorisation trick $(x-a)(y-a) = a^2$ (here $a = 12$) is standard for $1/x + 1/y = 1/a$. The number of solutions equals the number of positive divisors of $a^2$.
P12 (AIMO 2023, adapted) Let $a$ and $b$ be positive integers with $\gcd(a,b) = 1$. Prove that $\gcd(a+b,\; a^2 + b^2) \in \{1, 2\}$. Hence determine when each case occurs.
[Source: adapted from AIMO 2023 Q5]
Solution
Let $d = \gcd(a+b,\; a^2 + b^2)$.

Step 1: Show $d \mid 2$.  Note: $$a^2 + b^2 = (a+b)^2 - 2ab.$$ Since $d \mid (a+b)$, we have $d \mid (a+b)^2$, so $d \mid (a^2+b^2) - (a+b)^2 = -2ab$, i.e., $d \mid 2ab$.

Also $d \mid (a+b)$, and since $\gcd(a,b)=1$, we have $\gcd(a+b, a) = \gcd(b, a) = 1$ and similarly $\gcd(a+b, b) = 1$. Thus $\gcd(a+b, ab) = 1$, so $d \mid \gcd(2ab, a+b)$... let's use a cleaner path:

Since $d \mid 2ab$ and $\gcd(d, a) \mid \gcd(a+b, a) = \gcd(b,a) = 1$, so $\gcd(d,a)=1$. Similarly $\gcd(d,b)=1$. Hence $\gcd(d, ab) = 1$, and from $d \mid 2ab$ we get $d \mid 2$.

Step 2: So $d = 1$ or $d = 2$.
$d = 2$ iff $2 \mid (a+b)$, i.e., $a$ and $b$ have the same parity. Since $\gcd(a,b)=1$, they cannot both be even. So $d = 2$ iff both $a$ and $b$ are odd, and $d = 1$ iff $a$ and $b$ have opposite parity. $\square$
Section 1.3 Summary — Key Tools
ToolWhen to Use
Euclidean AlgorithmComputing $\gcd$ of specific numbers — fast, no factorisation needed
$\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$GCD of exponential expressions
Bézout's Identity $ax+by=\gcd(a,b)$Proving coprimality, solving linear Diophantine equations
$\gcd \times \text{lcm} = ab$Any problem involving both GCD and LCM
$a = dm, b = dn, \gcd(m,n)=1$The universal GCD substitution — use it everywhere
Coprime product: $\gcd(a,b)=1$, $a \mid n$, $b \mid n \Rightarrow ab \mid n$Combining divisibility conditions
Linear Diophantine: $ax+by=c$ solvable iff $\gcd(a,b) \mid c$Existence of integer solutions
← Section 1.2: Primes & Prime Factorisation Section 1.4: Base Conversion →