GCD and the Euclidean Algorithm

How do one share 252 candies among 105 children so everyone gets an equal share and nothing is left over? one need to find how many each child gets: that's 252/105. But one need to simplify the fraction! GCD is the key to simplifying fractions and solving many problems.

• **Cryptography:** RSA encryption uses GCD
• **Music:** harmonic intervals and rhythms
• **Engineering:** calculating gear ratios and transmissions

An Algorithm 2,300 Years Old

Euclid described this algorithm in Book VII of his Elements: perhaps the most influential mathematical text in history. The algorithm was known before Euclid, but he was the one who gave it rigorous justification.

What is asserted without proof can be dismissed without proof.

Today the Euclidean algorithm is the foundation of RSA cryptography, which protects every bank transaction on the internet. Without it, there would be no secure online payments.

What is GCD

one need to cut a 12×18 cm board into identical squares with no waste. What is the maximum square size? This is a **GCD** problem: greatest common divisor.

**GCD(a, b)**: the largest number that divides both a and b without a remainder. GCD(12, 18) = 6 Because 6 is the largest divisor common to both 12 and 18.

If GCD(a, b) = 1, the numbers are called **coprime**. For example, GCD(8, 15) = 1, even though neither 8 nor 15 is a prime number.

The Euclidean Algorithm

Factorization works, but it's slow for large numbers. 2,300 years ago, Euclid devised a brilliantly simple method: the **Euclidean algorithm**.

**Efficiency of the Euclidean Algorithm:** For numbers up to one million: at most ~30 steps! This is one of the oldest algorithms, and it is still used in cryptography today.

The Euclidean algorithm is an example of recursive thinking: we reduce a large problem to a smaller one of the same type, until we reach a trivial base case.

Applications of GCD

GCD is not just a mathematical abstraction. It's needed for reducing fractions, solving equations, and even encrypting data.

**GCD of multiple numbers:** GCD(a, b, c) = GCD(GCD(a, b), c) Example: GCD(12, 18, 24) = GCD(GCD(12, 18), 24) = GCD(6, 24) = 6

Checking for coprimality is important in cryptography. RSA encryption requires certain numbers to be coprime: this is verified using the Euclidean algorithm.

Linear Representation of GCD

A surprising fact: GCD(a, b) can always be expressed as **ax + by** for some integers x and y. This is called the **linear representation of GCD**.

**When does ax + by = c have a solution?** Only when GCD(a, b) divides c. 15x + 10y = 25: has a solution (GCD(15,10)=5 divides 25) 15x + 10y = 17: has no solution (5 does not divide 17)

The extended Euclidean algorithm automatically finds x and y. This is the foundation for computing modular inverses in modular arithmetic and cryptography.

Key Ideas

• GCD(a, b): greatest common divisor
• Euclidean algorithm: GCD(a, b) = GCD(b, a mod b)
• Bézout's theorem: ax + by = GCD(a, b) is always solvable
• Coprime numbers: GCD = 1

Related Topics

GCD is a central concept in number theory:

• LCM — LCM × GCD = a × b
• Modular Arithmetic — Modular inverses
• Cryptography — RSA and keys

Вопросы для размышления

• Why does the Euclidean algorithm work faster than factorization?
• How is GCD related to geometry (the tiling problem)?
• Why is checking for coprimality important in cryptography?

Связанные уроки

• crypto-03-number-theory