Quant Academy Math · Probability · Quant Finance
Phase 19 - Lesson 19.1

Divisibility, GCD, and the Euclidean Algorithm

The arithmetic of the integers: division with remainder, greatest common divisors, and Bézout’s identity - the bedrock every later lesson stands on.

⏱ 50 min● Beginner🔗 Prereqs: 1.x proof by induction; basic Python
↖ Phase 19 hub
Builds on: Phase 1 gave you induction and proof discipline; here you use both on \(\Z\).
Leads to: 19.2 factorizes; 19.3 inverts mod n using extended Euclid; the Euler Lab’s Number Theory path drills these directly.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Key Vocabulary

Divides
\(d\mid n\) means \(n=dk\) for some integer \(k\). Note \(d\mid 0\) for every \(d\), and only \(0\mid 0\).
Division algorithm
For \(a\in\Z,\ b\gt 0\) there exist unique \(q,r\) with \(a=qb+r\) and \(0\le r\lt b\).
Greatest common divisor
The largest \(d\) dividing both \(a\) and \(b\); equivalently the non-negative generator of the ideal \(a\Z+b\Z\).
Bézout’s identity
There exist integers \(x,y\) with \(ax+by=\gcd(a,b)\); the gcd is the smallest positive integer combination of \(a\) and \(b\).
Coprime
\(\gcd(a,b)=1\). Coprimality is what makes modular inverses, CRT, and Farey/Pell arguments work.
Least common multiple
\(\operatorname{lcm}(a,b)=|ab|/\gcd(a,b)\) for nonzero \(a,b\) - compute the gcd first to avoid overflow in fixed-width languages.

Intuition & Motivation

Intuition
Everything in elementary number theory is downstream of one humble move: divide and keep the remainder. Repeat that move and the numbers collapse geometrically - two 60-digit integers reach their gcd in a few hundred steps, not \(10^{60}\). And if you record the bookkeeping while you collapse them, you get more than the gcd: you get the exact integer combination \(ax+by=g\) that produces it. That combination is the modular inverse, the Diophantine solver, and the CRT reconstruction, all in one.

Division with remainder

Definition - Division algorithm
For any \(a\in\Z\) and \(b\gt 0\) there are unique \(q,r\in\Z\) with \(a=qb+r,\qquad 0\le r\lt b.\) Existence: take \(q=\lfloor a/b\rfloor\). Uniqueness: if \(qb+r=q'b+r'\) then \(b\mid (r-r')\) while \(|r-r'|\lt b\), forcing \(r=r'\).

In Python, a % b already returns the mathematician’s non-negative remainder for \(b\gt 0\) (unlike C, where -7 % 3 is -1). This is a small gift you should not take for granted when porting code.

The gcd and Euclid’s invariant

Theorem - Euclid’s invariant
For \(b\ne0\),
\[\gcd(a,b)=\gcd(b,\ a\bmod b).\] (19.1)
Consequently the iteration \((a,b)\mapsto(b,\ a\bmod b)\) preserves the gcd and terminates at \((g,0)\), where \(g=\gcd(a,b)\).
Proof
Write \(a=qb+r\). If \(d\mid a\) and \(d\mid b\) then \(d\mid a-qb=r\), so every common divisor of \((a,b)\) divides \((b,r)\). Conversely if \(d\mid b\) and \(d\mid r\) then \(d\mid qb+r=a\). The two pairs have identical common-divisor sets, hence the same greatest element. Termination: the second coordinate strictly decreases and is a non-negative integer, so by well-ordering the process halts.
Why it is fast
If \(a\gt b\) then \(a\bmod b\lt a/2\) whenever \(b\le a/2\), and otherwise \(a\bmod b=a-b\lt a/2\). Either way the larger argument at least halves every two steps, giving \(O(\log\min(a,b))\) iterations. The worst case is consecutive Fibonacci numbers (Lamé’s theorem) - a fact we re-derive in 19.6.

Extended Euclid and Bézout

Run the same recursion but carry the coefficients. Maintain the two invariants \(r_i = a x_i + b y_i\) for the running remainders \(r_i\); the last nonzero remainder is \(g\) and its coefficients are Bézout’s.

\[\gcd(a,b)=g \;\Longrightarrow\; \exists\,x,y\in\Z:\; ax+by=g,\qquad\text{and }\{ax+by\}=g\Z .\] (19.2)
Worked Example - Extended Euclid on \((240,46)\)
1
\(240 = 5\cdot 46 + 10\)  (q=5)
2
\(46 = 4\cdot 10 + 6\)  (q=4)
3
\(10 = 1\cdot 6 + 4\)  (q=1)
4
\(6 = 1\cdot 4 + 2\)  (q=1)
5
\(4 = 2\cdot 2 + 0\) → the last nonzero remainder is \(g=\gcd(240,46)=2\).
6
Back-substitute: \(2 = 6-1\cdot4 = 6-(10-6)=2\cdot 6-10 = 2(46-4\cdot10)-10 = 2\cdot46-9\cdot10\).
7
Finally \(10=240-5\cdot46\), so \(2 = 2\cdot 46 - 9(240-5\cdot 46)= -9\cdot 240 + 47\cdot 46\).
8
Check: \(-9(240)+47(46) = -2160+2162 = 2 = g\). ✓ So \((x,y)=(-9,47)\).
Key Idea
Bézout is the whole reason extended Euclid matters: \(x\) is the inverse of \(a\) modulo \(b\) whenever \(\gcd(a,b)=1\), because \(ax\equiv g=1\pmod b\). Lesson 19.3 cashes this in.

Coding workbench

Where this shows up

The Euler Lab’s Number Theory path is full of problems that reduce to a gcd in disguise: reduced fractions and Farey sequences, lattice-point counting on lines, cycle lengths of maps like \(x\mapsto x+k \bmod n\) (which visit \(n/\gcd(n,k)\) states), and totient computations. When a problem smells like “how many of these are in lowest terms?”, reach for gcd first.

Common Mistakes to Avoid
  • Assuming \(\gcd(0,0)\) is defined as a positive number - it is 0 by convention; guard it.
  • Recursive Euclid on adversarial inputs in languages with small stacks. The iterative form has no such risk.
  • Computing \(\operatorname{lcm}(a,b)=ab/\gcd\) as a*b//g in a fixed-width language: \(ab\) can overflow. Do a//g*b instead.
  • Reading Bézout coefficients as unique. They are only unique modulo \((b/g,\,a/g)\): \((x+kb/g,\ y-ka/g)\) works for every \(k\).
Quant Practitioner Tips
  • Python’s math.gcd is C-fast and handles arbitrary precision - use it in production and write your own only to understand it (and when you need the Bézout coefficients, which math.gcd does not give you).
  • The gcd is the cheapest primitive that lets you decide ‘are these two structures aligned?’ - periods, rotations, and step sizes all synchronise after \(\operatorname{lcm}\) steps.
  • Binary (Stein’s) gcd replaces division with shifts and subtraction; worth knowing when division is expensive, but in Python the built-in wins.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#1 Multiples of 3 or 5 (1%, tier A) #2 Even Fibonacci Numbers (1%, tier A) #7 10 001st Prime (1%, tier A) #20 Factorial Digit Sum (1%, tier A)

Applied:
#293 Pseudo-Fortunate Numbers (16%, tier B) #313 Sliding Game (16%, tier B) #357 Prime Generating Integers (16%, tier B)

Challenge:
#161 Triominoes (41%, tier C) #182 RSA Encryption (41%, tier C)

481 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Medium
Why does \(\gcd(a,b)=\gcd(b,a\bmod b)\) hold?
Because \(a\bmod b\) is always smaller than \(b\)
Because the pairs \((a,b)\) and \((b,a\bmod b)\) have exactly the same set of common divisors
Because gcd is commutative
Because \(b\mid a\) whenever \(a\gt b\)
Q2 Medium
Extended Euclid on \((a,b)\) with \(\gcd(a,b)=1\) returns \(x\) such that:
\(x=a^{-1}\bmod b\)
\(x=b^{-1}\bmod a\)
\(x=\operatorname{lcm}(a,b)\)
\(x\) is always positive
Q3 Medium
How many division steps does Euclid take on two numbers below \(10^{18}\)?
About \(10^9\)
About 90 - the arguments shrink geometrically
Exactly 18
It depends on how many prime factors they have

Practical Exercise

(a) Prove that \(\gcd(a,b)\) is the smallest positive element of the set \(S=\{ax+by: x,y\in\Z\}\cap\Z_{\gt 0}\). (b) Use it to show that the linear Diophantine equation \(ax+by=c\) has an integer solution if and only if \(\gcd(a,b)\mid c\), and describe all solutions.

▶ Show full solution

(a) Let \(d\) be the smallest positive element of \(S\), say \(d=ax_0+by_0\). Divide: \(a=qd+r\) with \(0\le r\lt d\). Then \(r=a-qd=a(1-qx_0)+b(-qy_0)\in a\Z+b\Z\). If \(r\gt 0\) it would be a positive element of \(S\) smaller than \(d\), contradiction; so \(r=0\) and \(d\mid a\). Symmetrically \(d\mid b\), so \(d\) is a common divisor. And any common divisor \(e\) of \(a,b\) divides \(ax_0+by_0=d\), hence \(e\le d\). Therefore \(d=\gcd(a,b)\).

(b) (\(\Rightarrow\)) If \(ax+by=c\) then \(g=\gcd(a,b)\) divides the left side, so \(g\mid c\). (\(\Leftarrow\)) If \(c=kg\), take Bézout \(ax_0+by_0=g\) and scale: \(a(kx_0)+b(ky_0)=c\).

All solutions: given one particular \((x_0,y_0)\) the general solution is

\[x = x_0 + t\cdot\frac{b}{g},\qquad y = y_0 - t\cdot\frac{a}{g},\qquad t\in\Z,\]
because the difference of any two solutions \((\Delta x,\Delta y)\) satisfies \(a\,\Delta x=-b\,\Delta y\), and dividing by \(g\) and using \(\gcd(a/g,b/g)=1\) forces \((b/g)\mid \Delta x\).

After the reveal, answer for yourself: Which step of (a) is exactly the division algorithm doing the work? Could you have proved it without well-ordering?

Lesson Summary

Division with remainder gives the gcd, and iterating \((a,b)\mapsto(b,a\bmod b)\) computes it in \(O(\log\min(a,b))\) steps because the arguments shrink geometrically. Carrying coefficients along the same recursion yields Bézout’s identity \(ax+by=\gcd(a,b)\), which is simultaneously a modular-inverse machine, a linear-Diophantine solver, and the engine behind CRT. Everything in Phase 19’s number-theory half is built on these two facts.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers
Q: State Euclid's invariant and why the algorithm terminates.
A: \(\gcd(a,b)=\gcd(b,a\bmod b)\) because both pairs share the same common divisors. It terminates because the second argument strictly decreases in \(\Z_{\ge0}\), and it is fast because the larger argument at least halves every two steps.
Q: What does extended Euclid give you that gcd alone does not?
A: The Bézout coefficients \(x,y\) with \(ax+by=\gcd(a,b)\). When \(\gcd(a,b)=1\) this \(x\) is \(a^{-1}\bmod b\), and scaling it solves any solvable \(ax+by=c\).

Completion Checklist

Confidence / mastery rating
Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

← 18.8Next: 19.2 →