Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is a way to find the greatest common divisor (GCD) of two integers. The GCD is the largest number that can divide both numbers evenly, with no remainder. It is named after the ancient Greek mathematician Euclid, who wrote about it in his Elements around 300 BC. This is one of the oldest methods still used today. The Euclidean algorithm can help make fractions easier to understand and is used in many important calculations.

The algorithm works by repeatedly taking the smaller number away from the larger one, or by dividing the larger number by the smaller one and using what is left over. This is done until both numbers become the same, and that number is the GCD.

The Euclidean algorithm has many useful purposes. It helps make fractions simpler, aids in modular arithmetic, and is part of the cryptographic protocols that protect internet communications. It is also helpful for solving some kinds of equations and creating continued fractions. Over time, the method has been adapted for more complex numbers, showing how important it is 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.

When the GCD of two numbers is 1, the numbers are called coprime. This means 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.

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 way to find the greatest common divisor (GCD) of two numbers. The GCD is the largest number that can divide both numbers evenly.

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 subtract multiples of the new remainder from the previous number, and continue this 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 shows how the greatest common divisor (GCD) of two numbers can be written as a mix of those numbers. The Euclidean algorithm helps find the smaller numbers needed for this.

Principal ideals and related problems

Bézout's identity links to ideas in algebra, like principal ideals. These are groups of numbers created from one number.

This idea can help solve real-world problems, like measuring with two cups. You can measure any amount that is a multiple of their GCD by using both cups.

Extended Euclidean algorithm

The extended Euclidean algorithm expands the basic Euclidean algorithm to find the numbers needed for Bézout's identity. It tracks these numbers through each step.

This method shows how the GCD can be written as a mix of the starting numbers. This is useful in many math problems.

Matrix method

We can also use matrices to find the numbers for Bézout's identity. This method organizes the steps of the Euclidean algorithm into matrix multiplication.

Euclid's lemma and unique factorization

Bézout's identity helps prove important facts in number theory. For example, it shows that if a prime number divides a product of two numbers, it must divide one of those numbers.

Linear Diophantine equations

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

Multiplicative inverses and the RSA algorithm

In some math systems, every nonzero number has a multiplicative inverse. This is another number that, when multiplied together, equals one. The Euclidean algorithm helps find these inverses. This is important for encryption methods like the RSA algorithm.

Chinese remainder theorem

The Euclidean algorithm can help solve sets of equations where a number leaves different remainders when divided by several numbers. This helps us find the original number from its remainders.

Stern–Brocot tree

The Euclidean algorithm can arrange all positive fractions into a tree structure. Each step in the algorithm moves left or right in this tree, helping us find any fraction by following a path from the start.

Continued fractions

The steps of the Euclidean algorithm connect closely to continued fractions. These are expressions where numbers repeat in a pattern. This link helps simplify and study fractions.

Factorization algorithms

Finding GCDs is a key step in many methods for breaking large numbers into primes. The Euclidean algorithm gives an efficient way to compute these GCDs, which is important for these techniques.

Algorithmic efficiency

Euclid's algorithm is a smart way to find the greatest common divisor (GCD) of two numbers. People have studied it to learn how fast it works. The number of steps it takes depends on how big the numbers are.

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. 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.

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 shows how polynomials can also be factored uniquely. The algorithm can also be used with complex numbers and other advanced mathematical structures.