Back to the on-screen lesson ·
Repeated division with remainder, the invariant that makes it a gcd, and why it never factorises anything.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run Euclid's algorithm on a pair of integers and read the greatest common divisor off the last non-zero remainder, state and prove the invariant $\gcd(a, b) = \gcd(b, r)$ that makes the run correct, say why the run must terminate and roughly how many divisions it takes, and extend the method to three or more numbers.
Lesson 1 turned divide and take the remainder into the equation $a = bq + r$ with $0 \le r < b$. That equation is about to be read in a way it was not written for.
Read left to right it says what $a$ is. Read as a statement about divisors it says something else: any number dividing $b$ and $r$ divides $bq + r$, which is $a$; and any number dividing $a$ and $b$ divides $a - bq$, which is $r$. The same one equation, used twice, in opposite directions.
A common divisor of $a$ and $b$ is an integer dividing both. The greatest common divisor $\gcd(a, b)$ is the largest of them, defined for all $a, b$ not both zero, with the convention $\gcd(a, 0) = |a|$.
Two numbers are coprime (relatively prime) when $\gcd(a, b) = 1$. That does not require either of them to be prime: $8$ and $9$ are coprime and neither is.
A run of the algorithm is its sequence of divisions. The last non-zero remainder is the answer, and the zero remainder is only the stopping signal.
The algorithm. To compute $\gcd(a, b)$ with $a \ge b > 0$: divide, keep the remainder, and repeat with the divisor and the remainder, until a remainder is $0$. The last non-zero remainder is the gcd.
Why it is right. The whole of it is one lemma: $$\gcd(a, b) = \gcd(b, r) \quad\text{where } a = bq + r.$$ Proof: if $d \mid b$ and $d \mid r$ then $d \mid (bq + r) = a$, so every common divisor of $(b, r)$ is one of $(a, b)$; and if $d \mid a$ and $d \mid b$ then $d \mid (a - bq) = r$, so the converse holds. The two pairs have the same set of common divisors, so the same greatest one.
That is stronger than it needs to be, and the strength gets used later: not only the gcd but the whole set of common divisors is preserved.
Why it stops. The remainders satisfy $b > r_1 > r_2 > \cdots \ge 0$, a strictly decreasing sequence of non-negative integers, which cannot be infinite. So the run terminates, and terminates with a remainder of $0$.
How fast. The remainder at least halves every two steps, so the number of divisions is $O(\log \min(a, b))$. Lamé's theorem sharpens it: no more than five times the number of decimal digits of the smaller number, and the worst case is a pair of consecutive Fibonacci numbers.
Another way: steps
Another way: example
$\gcd(252, 198)$: $252 = 1 \cdot 198 + 54$; $198 = 3 \cdot 54 + 36$; $54 = 1 \cdot 36 + 18$; $36 = 2 \cdot 18 + 0$. The gcd is $18$. Four divisions on numbers with three digits — and compare the alternative, which is factorising $252 = 2^2 \cdot 3^2 \cdot 7$ and $198 = 2 \cdot 3^2 \cdot 11$ and taking minimum exponents. That works here and stops working entirely at about eighty digits.
The gcd of two small numbers can be found by factorising both and taking the smaller exponent of each prime. So why is Euclid's algorithm in every course, and in every cryptographic library?
Because it does not factorise. Factorising a thousand-digit number is, as far as anyone knows, infeasible; running Euclid's algorithm on two thousand-digit numbers takes a few thousand divisions and finishes immediately. RSA depends on exactly this asymmetry — the arithmetic that sets up a key needs gcds and inverses, both of which Euclid supplies, and the arithmetic that would break it needs a factorisation, which nothing supplies.
There is a second reason, and it is the one this unit turns on. The run is reversible. Each line says $r_i = r_{i-2} - q_i r_{i-1}$, so the gcd at the bottom can be substituted upwards until it is written in terms of the two numbers you started with. That is Bézout's identity, and it is the next lesson. A method that only produced the gcd would be worth far less.
A practical note: the binary (or Stein's) algorithm replaces division by halving and subtraction, which is faster on hardware without a divider. It computes the same thing by the same invariant, so nothing here is lost — but it does not produce Bézout coefficients as directly, which is why the division form is the one taught.
It does not factorise. Nothing in the run knows a prime from a composite. A learner who checks an answer by factorising both numbers is doing more work than the algorithm did and using a method that does not scale.
The zero remainder is not the answer. The run ends when a remainder is $0$; the gcd is the remainder before it, which is the final divisor. Reporting $0$ is the single most common slip.
Order does not matter. Starting with the smaller number first simply produces $b = 0 \cdot a + b$, which swaps them, and the run continues as before. One wasted line, no wrong answer.
Coprimality is not a failure. When the numbers share nothing, the last non-zero remainder is $1$ and the gcd is $1$. That is an answer, not a breakdown, and it is the case that matters most in practice: it is exactly the case in which an inverse modulo $n$ exists.
One genuine limitation: as stated, the algorithm wants positive inputs. Work with $|a|$ and $|b|$ — the gcd is unaffected by sign, since $d \mid a$ exactly when $d \mid -a$.
$\gcd(1071, 462)$. $1071 = 2 \cdot 462 + 147$, so $\gcd(1071, 462) = \gcd(462, 147)$.
The pair changed; its common divisors did not.
$462 = 3 \cdot 147 + 21$, so this equals $\gcd(147, 21)$. Then $147 = 7 \cdot 21 + 0$.
Three divisions.
The last non-zero remainder is $21$, so $\gcd(1071, 462) = 21$. Check by the invariant chain: $\gcd(1071, 462) = \gcd(462, 147) = \gcd(147, 21) = \gcd(21, 0) = 21$.
Each equality is one use of the lemma.
$\gcd(13, 8)$: $13 = 1 \cdot 8 + 5$, $8 = 1 \cdot 5 + 3$, $5 = 1 \cdot 3 + 2$, $3 = 1 \cdot 2 + 1$, $2 = 2 \cdot 1 + 0$. Five divisions for two-digit numbers.
Every quotient is $1$, which is as slow as a step can be.
$13$ and $8$ are consecutive Fibonacci numbers, and that is not a coincidence: a quotient of $1$ means $r_{i-2} = r_{i-1} + r_i$, which is the Fibonacci recursion read backwards.
The slowest input is forced to be Fibonacci.
Since the Fibonacci numbers grow like $\varphi^n$, the number of steps grows like $\log_\varphi$ of the input — about $4.8$ times the digit count, which is Lamé's bound.
A worst case this good is why nothing has replaced it.
Run the algorithm on $n + 1$ and $n$: the first division is $n + 1 = 1 \cdot n + 1$.
One division is enough.
So $\gcd(n + 1, n) = \gcd(n, 1)$, and the next division leaves remainder $0$.
The invariant, applied twice.
The last non-zero remainder is $1$, so consecutive integers are coprime.
Put the lines of Euclid's algorithm for $62$ and $58$ into the order they are carried out, ending with the gcd.
Number the steps in order (write the number in the box):
What is $\gcd(209, 66)$?
Answer:
Run Euclid's algorithm on $120$ and $52$. Fill in the quotient and the remainder of each division.
| Quotient | Remainder | |
|---|---|---|
| $120 \div 52$ | ||
| $52 \div 16$ | ||
| $16 \div 4$ |
Is this true of Euclid's algorithm: the remainders strictly decrease, so the run must stop?
Euclid's algorithm on $74$ and $50$ produces two non-zero remainders before it stops. Give them, in the order they appear.
first remainder a, second remainder c
Euclid's algorithm takes two numbers. Use it twice to find $\gcd(136, 144, 132)$: give the gcd of the first two, then the gcd of that with the third.
| Value | |
|---|---|
| $\gcd(136, 144)$ | |
| $\gcd$ of that with $132$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put the lines of Euclid's algorithm for $120$ and $52$ into the order they are carried out, ending with the gcd.
Number the steps in order (write the number in the box):
You can compute a greatest common divisor by repeated division and say why each step leaves the answer unchanged. Say in your own words what the algorithm never does, and why that is the reason it is still used. Next: running the same divisions backwards, to write the gcd in terms of the two numbers.
9. Your turn: show that consecutive integers are always coprime, step 3