Back to the on-screen lesson ·
Replacing a pair by a smaller pair with the same common divisors, why that terminates, and how running the lines backwards writes the answer as a combination.
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 the Euclidean algorithm to find a greatest common divisor, say why replacing a pair by the divisor and the remainder leaves the answer unchanged and why the process must stop, and get a least common multiple from the gcd by dividing the product. You will also be able to run the lines backwards to write the gcd as a combination of the two numbers, and say why that identity is what makes a modular inverse possible.
The division algorithm from lesson 24, which is the only fact this lesson uses, and the habit of unfolding $a \mid b$ into $b = ak$. The last faded example of lesson 24 showed that a divisor of $b$ and $c$ divides $xb + yc$ for any integers $x$ and $y$; this lesson is that observation used twice.
$\gcd(a, b)$ is the largest integer dividing both; $\operatorname{lcm}(a, b)$ is the smallest positive integer both divide. Two integers are coprime when their gcd is $1$. A linear combination of $a$ and $b$ is any $ax + by$ with $x$ and $y$ integers — both of which may be negative, which is the point.
The algorithm. To find $\gcd(a, b)$: divide $a$ by $b$, keep the remainder, and repeat with the pair $(b, r)$. Stop when the remainder is zero; the last non-zero remainder is the answer.
$$\gcd(48, 18): \quad 48 = 2 \cdot 18 + 12, \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0 \quad \Rightarrow \quad \gcd = 6$$
Why it works, in one observation. If $a = bq + r$ then a common divisor of $a$ and $b$ divides $r = a - bq$, and a common divisor of $b$ and $r$ divides $a = bq + r$. So $(a, b)$ and $(b, r)$ have exactly the same common divisors, and therefore the same greatest one. Each step replaces the problem by an equivalent smaller one.
Why it stops. The remainders strictly decrease and are never negative, so the sequence reaches zero. That is a complete termination argument, and it is worth noticing that it did not need to say how long the process takes.
What it avoids. Nothing is factorised. Finding $\gcd(a, b)$ by factorising both is correct and hopeless for large numbers, because factorisation is hard and this is not — the algorithm on two-hundred-digit numbers finishes in well under a thousand divisions.
Bézout's identity. There are integers $x$ and $y$ with $$ax + by = \gcd(a, b),$$ and running the algorithm backwards produces them. This is the theorem the rest of the unit needs: with $\gcd(a, m) = 1$ it gives $ax + my = 1$, so $ax \equiv 1 \pmod m$ and $x$ is the inverse of $a$ modulo $m$. It also proves Euclid's lemma — if a prime divides a product it divides a factor — which is what makes factorisation unique.
Another way: steps
To run the algorithm:
Another way: example
Backwards on $48$ and $18$: from the second line, $6 = 18 - 1 \cdot 12$. The first line gives $12 = 48 - 2 \cdot 18$. Substituting, $6 = 18 - (48 - 2 \cdot 18) = -48 + 3 \cdot 18$, so $x = -1$ and $y = 3$. Nothing was multiplied out, which is exactly why the answer is readable.
$$\gcd(a, b) \times \operatorname{lcm}(a, b) = ab$$
Prime by prime, the gcd takes the lower power and the lcm the higher, so between them they take each prime exactly as often as $ab$ does. That is the proof, and it is also the reason the identity is stated for positive integers only.
In practice it is used to get the lcm cheaply: find the gcd with Euclid, then divide the product by it. $\operatorname{lcm}(48, 18) = 48 \times 18 / 6 = 144$. Multiplying without dividing gives $864$, which is six times too large — every shared factor counted twice.
The same identity explains lesson 11's inclusion-and-exclusion trap. The numbers up to $60$ divisible by $3$ and by $4$ are the multiples of $\operatorname{lcm}(3, 4) = 12$; for $3$ and $6$ the lcm is $6$ and not $18$, and using the product there would have undercounted the overlap.
Keeping the quotient instead of the remainder. The quotients matter only when running backwards for Bézout.
Stopping one line early. The answer is the last non-zero remainder, not the zero.
Evaluating while running backwards. Substituting and simplifying to a single number destroys the identity you are trying to build; keep $a$ and $b$ as symbols.
Expecting $x$ and $y$ to be positive. They cannot both be, unless the gcd is one of the numbers. One of them is negative, always.
Expecting them to be unique. Adding $b/g$ to $x$ and subtracting $a/g$ from $y$ gives another pair, and there are infinitely many.
It is easy to treat Euclid's algorithm as a procedure that produces the gcd by fiat, and then to be surprised that a linear combination has anything to do with it. What the algorithm actually does is preserve the set of common divisors at every step, and the gcd is read off at the end because one entry is zero. Seeing it that way makes Bézout unsurprising: every remainder along the way was a combination of the two originals, so the last one is too.
$\gcd(105, 56)$. First: $105 = 1 \cdot 56 + 49$.
Divide, keep the remainder.
Then $56 = 1 \cdot 49 + 7$, and $49 = 7 \cdot 7 + 0$.
Each pair replaced by a smaller one.
The last non-zero remainder is $7$, so $\gcd(105, 56) = 7$. Three divisions, and neither number was factorised.
The answer, with no factorisation anywhere.
$\gcd(35, 12) = 1$, from $35 = 2 \cdot 12 + 11$, $12 = 1 \cdot 11 + 1$.
Forwards first, keeping the lines.
From the second line, $1 = 12 - 11$. From the first, $11 = 35 - 2 \cdot 12$. Substituting, $1 = 12 - (35 - 2 \cdot 12) = -35 + 3 \cdot 12$.
Substitute, and resist multiplying out.
So $x = -1$ and $y = 3$. Reading it modulo $35$: $3 \cdot 12 \equiv 1$, so $3$ is the inverse of $12$ modulo $35$ — which the next lesson will need and could not get any other way.
The identity is the inverse, read sideways.
$91 = 2 \cdot 35 + 21$; $35 = 1 \cdot 21 + 14$; $21 = 1 \cdot 14 + 7$; $14 = 2 \cdot 7 + 0$. So the gcd is $7$.
Forwards, keeping every line.
Backwards: $7 = 21 - 14$, and $14 = 35 - 21$, so $7 = 21 - (35 - 21) = 2 \cdot 21 - 35$.
One substitution at a time.
And $21 = 91 - 2 \cdot 35$, so $7 = 2(91 - 2 \cdot 35) - 35 = 2 \cdot 91 - 5 \cdot 35$. Check: $182 - 175 = 7$. Note that one coefficient came out negative, as one always must when the gcd is smaller than both numbers.
Run the Euclidean algorithm on $84$ and $30$. Give the quotient and remainder at each of the first three divisions.
| Quotient | Remainder | |
|---|---|---|
| $84$ divided by $30$ | ||
| $30$ divided by $24$ | ||
| $24$ divided by $6$ |
What is $\gcd(144, 60)$?
Answer:
Put in order the steps of the argument that the Euclidean algorithm gives the greatest common divisor.
Number the steps in order (write the number in the box):
$\gcd(48, 18) = 6$. What is $\operatorname{lcm}(48, 18)$?
Answer:
Running Euclid backwards writes $\gcd(26, 15) = 1$ as $26x + 15y$. Fill in $x$ and $y$.
$x = $x and $y = $y.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Run the Euclidean algorithm on $48$ and $18$. Give the quotient and remainder at each of the first three divisions.
| Quotient | Remainder | |
|---|---|---|
| $48$ divided by $18$ | ||
| $18$ divided by $12$ | ||
| $12$ divided by $6$ |
You can find a gcd by repeated division, explain why each replacement preserves the answer, and run the lines backwards for a combination. Say in your own words why the algorithm terminates, and why one of the two coefficients must be negative. Next: arithmetic done on remainders, where that combination becomes an inverse.
10. Your turn: find $\gcd(91, 35)$ and write it as a combination, step 3