# GCD and the Euclidean Algorithm

Mathematics I · Arithmetic and Number Theory · https://tryals.app/learn/mathematics-i/gcd-and-the-euclidean-algorithm

The **greatest common divisor** $\gcd(a, b)$ is the largest positive integer dividing both $a$ and $b$. Its partner, the **least common multiple** $\operatorname{lcm}(a, b)$, is the smallest positive integer that both $a$ and $b$ divide.

Factoring is slow for large numbers. The **Euclidean algorithm** finds $\gcd(a, b)$ instantly using the rule:
$$\gcd(a, b) = \gcd(b, r)$$
where $r$ is the remainder of $a \div b$.

| Step | Division | Remainder ($r$) |
| --- | --- | --- |
| 1 | $48 = 2 \cdot 18 + 12$ | $12$ |
| 2 | $18 = 1 \cdot 12 + 6$ | $6$ |
| 3 | $12 = 2 \cdot 6 + 0$ | $0$ |

Repeatedly replace $(a, b)$ with $(b, r)$ until $r = 0$. The last nonzero remainder is the gcd. Here, $\gcd(48, 18) = 6$.

## Coprime and the LCM Link

Two numbers are **coprime** (relatively prime) when $\gcd(a, b) = 1$, meaning they share no prime factors. This is essential for finding multiplicative inverses in modular arithmetic.

You can find the lcm instantly without factoring using the identity:
$$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b$$
Rearranging gives $\operatorname{lcm}(a, b) = \frac{ab}{\gcd(a,b)}$.

**Common Pitfall:** Never confuse the two terms:

| Property | GCD | LCM |
| --- | --- | --- |
| Meaning | Divisor of both | Multiple of both |
| Bound | At most the smaller | At least the larger |
| Example | $\gcd(12, 18) = 6$ | $\operatorname{lcm}(12, 18) = 36$ |

## Practice questions

4 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Order the lines of the Euclidean algorithm computing gcd(1071, 462).

**Answer:**

1. 1071 = 2 x 462 + 147
2. 462 = 3 x 147 + 21
3. 147 = 7 x 21 + 0
4. The last nonzero remainder is 21, so gcd(1071, 462) = 21

**Why:** Each step replaces the pair (a, b) by (b, r), and the remainders shrink fast: 462, 147, 21, 0. The answer is the LAST NONZERO remainder, 21, taking the final 0, or the final divisor's remainder, is the usual slip. No factoring was needed anywhere.

Page: https://tryals.app/practice/mathematics-i/gcd-and-the-euclidean-algorithm/order-the-lines-of-the-euclidean-algorithm-computing-gcd-1071-462

### 2. Select every TRUE statement about gcd and lcm for the numbers 12 and 18.

A. gcd(12, 18) = 6
B. lcm(12, 18) = 216
C. gcd(12, 18) = 36
D. The gcd is never larger than the smaller of the two numbers
E. The lcm is never smaller than the larger of the two numbers
F. lcm(12, 18) = 36

**Answer:** A. gcd(12, 18) = 6; D. The gcd is never larger than the smaller of the two numbers; E. The lcm is never smaller than the larger of the two numbers; F. lcm(12, 18) = 36

**Why:** gcd(12, 18) = 6 and lcm = (12 x 18)/6 = 36. The size rules follow from the definitions: a common DIVISOR is at most the smaller number, a common MULTIPLE is at least the larger. 216 is just 12 x 18, which is only the lcm when the two are coprime.

Page: https://tryals.app/practice/mathematics-i/gcd-and-the-euclidean-algorithm/select-every-true-statement-about-gcd-and-lcm-for-the-numbers-12-and

### 3. The Euclidean algorithm's worst case is a pair of consecutive **Fibonacci** numbers. Why would the slowest input be those in particular?

A. Because the algorithm was designed using Fibonacci numbers as a test case
B. Because consecutive Fibonacci numbers make every quotient 1
C. Because their ratio is irrational, preventing the algorithm from terminating cleanly
D. Because Fibonacci numbers are all prime, maximising the work

**Answer:** B. Because consecutive Fibonacci numbers make every quotient 1

**Why:** Every quotient comes out 1, so each step replaces (a, b) with (b, a−b), the least progress the algorithm can make. Lamé used exactly this to bound the running time, giving the first worst-case complexity analysis of any algorithm, centuries before the term existed.

Page: https://tryals.app/practice/mathematics-i/gcd-and-the-euclidean-algorithm/the-euclidean-algorithms-worst-case-is-a-pair-of-consecutive

### 4. The Euclidean algorithm finds gcd(84, 30) by factorising both numbers and comparing their prime powers.

**Answer:** False

**Why:** False. It takes repeated remainders — $84 = 2(30) + 24$, then $30 = 1(24) + 6$, then $24 = 4(6)$, giving 6 — and never factorises anything. That is exactly why it is preferred: remainders take logarithmically many steps, while factoring a large number has no known efficient method, an asymmetry RSA depends on.

Page: https://tryals.app/practice/mathematics-i/gcd-and-the-euclidean-algorithm/the-euclidean-algorithm-finds-gcd-84-30-by-factorising-both-numbers