Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is one of the oldest algorithms still in common use today. The Euclidean algorithm can help reduce fractions to their simplest form and is used in many other important calculations.

The algorithm works by repeatedly replacing the larger number with the difference between the two numbers, or more efficiently, with the remainder when the larger number is divided by the smaller one. This process continues until the two numbers become equal, and that number is the GCD. This method can also show how the GCD can be written as a combination of the two original numbers.

The Euclidean algorithm has many important uses. It helps simplify fractions, perform calculations in modular arithmetic, and is part of the cryptographic protocols that keep internet communications secure. It is also useful for solving certain types of equations and for constructing continued fractions. Over time, the algorithm has been expanded to work with more complex numbers, showing its lasting importance in mathematics.

Background: greatest common divisor

Main article: Greatest common divisor

The Euclidean algorithm is a smart way to find the greatest common divisor (GCD) of two numbers. The GCD is the biggest number that can divide both numbers perfectly, without any leftover. We can call this the greatest common factor, highest common factor, highest common divisor, or greatest common measure.

When the GCD of two numbers is 1, the numbers are called coprime, meaning they share no common factors except 1. For example, 6 and 35 are not prime numbers, but they are coprime because their only common factor is 1. The Euclidean algorithm helps find this easily, even for very large numbers, without needing to break the numbers into their prime factors.

Description

Procedure

Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.

The Euclidean algorithm is a smart way to find the greatest common divisor (GCD) of two numbers. The GCD is the largest number that can divide both numbers evenly, without leaving any remainder.

This method works by repeatedly subtracting smaller numbers from larger ones until we reach zero. The last non-zero number before we get to zero is the GCD. For example, to find the GCD of 1071 and 462, we subtract multiples of 462 from 1071, then multiples of the new remainder from the previous number, and continue this process until we reach zero. The steps show that the GCD of 1071 and 462 is 21.

Step k	Equation	Quotient and remainder
0	1071 = q₀ 462 + r₀	q₀ = 2 and r₀ = 147
1	462 = q₁ 147 + r₁	q₁ = 3 and r₁ = 21
2	147 = q₂ 21 + r₂	q₂ = 7 and r₂ = 0; algorithm ends

Mathematical applications

Bézout's identity

Bézout's identity explains how the greatest common divisor (GCD) of two numbers can be shown as a combination of those numbers. For any two numbers, there are always smaller numbers we can use to express their GCD.

The Euclidean algorithm helps find these smaller numbers by working backward through the steps of the algorithm. This idea can also be expanded to more complex mathematical settings.

Principal ideals and related problems

Bézout's identity gives another way to think about the GCD of two numbers. It connects to ideas in modern algebra, like principal ideals, which are sets of numbers generated by a single number.

This concept can solve practical problems, like measuring volumes with limited tools. If you have two measuring cups, you can use combinations of them to measure any volume that is a multiple of their GCD.

Extended Euclidean algorithm

The extended Euclidean algorithm builds on the basic Euclidean algorithm to efficiently find the numbers needed for Bézout's identity. It adds recursive steps to track these numbers through the algorithm.

This method shows how the GCD can be expressed as a combination of the original numbers, which is useful in various mathematical applications.

Matrix method

Another way to find the numbers for Bézout's identity uses matrices. This method organizes the steps of the Euclidean algorithm into matrix multiplication, making the process systematic and efficient.

Euclid's lemma and unique factorization

Bézout's identity helps prove important results in number theory, like the unique factorization of numbers into primes. It shows that if a prime number divides a product of two numbers, it must divide at least one of those numbers.

Linear Diophantine equations

Diophantine equations are equations where we look for integer solutions. The Euclidean algorithm helps solve these equations by finding combinations of numbers that equal a given total.

Multiplicative inverses and the RSA algorithm

In certain mathematical systems, every nonzero number has a multiplicative inverse — another number that, when multiplied together, gives one. The Euclidean algorithm helps find these inverses, which is important for encryption methods like the RSA algorithm.

Chinese remainder theorem

The Euclidean algorithm can help solve systems of equations where a number leaves different remainders when divided by several other numbers. This is useful in reconstructing a number from its remainders.

Stern–Brocot tree

The Euclidean algorithm can organize all positive fractions into a tree structure. Each step in the algorithm corresponds to moving left or right in this tree, allowing us to find any fraction by following a path from the root.

Continued fractions

The steps of the Euclidean algorithm relate closely to continued fractions, which are expressions where numbers are repeated in a specific pattern. This connection helps simplify and analyze fractions.

Factorization algorithms

Finding GCDs is a key step in many methods for factoring large numbers into primes. The Euclidean algorithm provides an efficient way to compute these GCDs, which is essential for these factorization techniques.

Algorithmic efficiency

Euclid's algorithm is a smart way to find the greatest common divisor (GCD) of two numbers. It has been studied a lot to understand how fast it works. The number of steps it takes depends on the size of the numbers.

One important discovery is that the number of steps needed is connected to the Fibonacci numbers. This helps us understand the worst-case scenario, where the algorithm might take the most steps.

Researchers have also looked at the average number of steps the algorithm takes. They have found ways to estimate this, which helps in understanding how efficient the algorithm is on average.

The speed of each step in the algorithm also matters. Dividing large numbers can take time, but there are ways to make this faster. Overall, Euclid's algorithm works well and is used in many places because it is efficient.

Generalizations

The Euclidean algorithm is mainly used to find the greatest common divisor of two whole numbers, but it can also be used with real numbers and other mathematical objects like polynomials. When used with real numbers, the algorithm helps find a number that both original numbers are multiples of. This shows a special property called unique factorization, meaning numbers can be broken down into smaller parts in only one way.

For polynomials, the Euclidean algorithm works similarly. It helps find the greatest common divisor of two polynomials by repeatedly dividing them until the remainder is zero. This process shows how polynomials can also be factored uniquely. The algorithm can also be used with complex numbers and other advanced mathematical structures, showing its wide range of uses in solving different kinds of problems.