Sample · 09-Divisibility and GCD
Chapter 9 Overview
Book 3 — Olympiad Number Theory · CHAPTER 09: Divisibility and GCD
"Mathematics is the queen of the sciences, and number theory is the queen of mathematics." — Carl Friedrich Gauss (as reported by Sartorius von Waltershausen, 1856)
Welcome to Book 3. Number theory studies the integers — and it begins, as Euclid did, with a single relation: divisibility. We write \( d\mid n \) ("\( d \) divides \( n \)") when \( n=dk \) for some integer \( k \). Everything in this chapter grows from that one idea: greatest common divisors, coprimality, and the beautiful identities that let you compute the gcd of enormous expressions without ever factoring them.
The organising engine of the chapter is the Euclidean algorithm, pictured above. To find \( \gcd(12,8) \), tile a \( 12\times8 \) rectangle with the largest squares that fit: an \( 8\times8 \), then two \( 4\times4 \). The side of the smallest square is the gcd. That geometric picture is exactly the arithmetic of repeated division \( a=qb+r \) — and it powers everything from Bezout’s identity to the RSA cryptosystem.
The four sections below build in order: divisibility and factor structure (09.1), the gcd/lcm machinery of Euclid and Bezout (09.2), coprimality and its consequences (09.3), and the gcd identities for expressions and powers (09.4). Use the map to see where a problem lives.
📋 How this chapter works
The familiar rhythm, tuned for number theory.
| Section | What it gives you |
|---|---|
| 📋 Strategy Corner | the definitions, the key lemma, and the standard computation |
| Decision flowchart | the method as a procedure, with the self-check that confirms the answer |
| 🌍 Math in the Real World | where the idea powers cryptography, computing, and more |
| ⚠️ Common Trap | the specific way strong students lose the mark |
| Worked Example | a full solution, with the divisibility check that catches errors |
| 🚀 Challenge Yourself | a harder problem with a hint but no solution |
The golden rule of this chapter: when in doubt, reduce. The Euclidean step — replacing a pair by a smaller one with the same gcd — is the most reliable move in all of elementary number theory. Almost every identity here is that one idea in disguise.
09.1 Divisibility
09.1 Divisibility
An integer \( d \) divides \( n \), written \( d\mid n \), if \( n=dk \) for some integer \( k \). This single relation obeys a handful of rules that you will use constantly: if \( d\mid a \) and \( d\mid b \), then \( d\mid(a\pm b) \) and \( d\mid ka \) for any integer \( k \); and divisibility is transitive, \( a\mid b \) and \( b\mid c \) give \( a\mid c \).
The deepest fact about the integers — the Fundamental Theorem of Arithmetic — says every integer greater than \( 1 \) factors uniquely into primes. That unique factorisation is what turns divisibility questions into counting questions: once you know \( n=p_1^{e_1}\cdots p_k^{e_k} \), the entire divisor structure of \( n \) is determined.
📋 Strategy Corner — Divisibility Properties · Reading Factorisation
From \( n=p_1^{e_1}\cdots p_k^{e_k} \), the divisor data follows a formula:
Continue reading — 5 chapters, worked examples and practice.
Sign in to buy