---
title: "Euclid's Algorithm and Bezout's Identity"
description: "Find a greatest common divisor by repeated division instead of by factorising, then run the algorithm backwards to write it as a combination of the two numbers."
canonical: https://lightmysky.com/learn/mathematics/euclids-algorithm-and-bezouts-identity-mt_26hM0EnJpq
source: https://lightmysky.com/learn/mathematics/euclids-algorithm-and-bezouts-identity-mt_26hM0EnJpq.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Euclid's Algorithm and Bezout's Identity

Find a greatest common divisor by repeated division instead of by factorising, then run the algorithm backwards to write it as a combination of the two numbers.

Subject: Mathematics · Area: Number Theory · Ages 18 to 19
Page: https://lightmysky.com/learn/mathematics/euclids-algorithm-and-bezouts-identity-mt_26hM0EnJpq

## Ready when they can

- Run the algorithm on a large pair and explain why it terminates
- Back-substitute to express the gcd as an integer combination of the inputs
- Deduce Euclid's lemma and, from it, uniqueness of prime factorisation

## Lesson: Remainders down to the gcd

The Euclidean algorithm finds the largest number dividing both inputs through repeated remainders. Write the larger number with quotient and remainder, replace the pair by the smaller number and the remainder, and repeat until a zero remainder appears. For 270 and 192 the remainders run 78, 36, 6, 0, so the last nonzero remainder, 6, is the gcd.

**Example.** Try it on 1071 and 462: 1071 = 462 times 2 plus 147, then 462 = 147 times 3 plus 21, then 147 = 21 times 7 plus 0, so the gcd is 21. It always stops because the remainders keep shrinking, and shrinking whole numbers must reach 0. One division per step beats listing hundreds of divisors.

Back substitution turns the chain into a combination of the original pair, which is Bezout's identity. Each remainder can be rewritten from the line above it, so working backwards expresses the gcd with the two inputs. For 270 and 192 this gives 6 = 5 times 270 plus negative 7 times 192, and you can check that 1350 minus 1344 is indeed 6.

**Tip.** The same idea proves Euclid's lemma: a prime dividing a product must divide one of the factors. From the lemma follows the uniqueness of prime factorisation, so every whole number over 1 breaks into primes in exactly one way, such as 24 = 2 times 2 times 2 times 3.

**Recap.** Repeat division to the gcd, run it backwards for the combination, and let the lemma secure unique factorisation.

## Practice

14 questions on this page, each with its working shown.

## Needs first

- [Divisibility and the Division Algorithm](https://lightmysky.com/learn/mathematics/divisibility-and-the-division-algorithm-mt_UkQNs-6-40)
- [Factors, multiples, and primes (age 11+)](https://lightmysky.com/learn/mathematics/factors-multiples-and-primes-age-11-mt_xhoOWnhtHq)

## Opens up

- [Modular Arithmetic and Congruence Classes](https://lightmysky.com/learn/mathematics/modular-arithmetic-and-congruence-classes-mt_Lt4_Aazx2j)