Euclidean algorithm

Euclid's algorithmEuclideanEuclidEuclidean division
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.wikipedia
245 Related Articles

Algorithm

algorithmsalgorithm designcomputer algorithm
It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules,
Greek mathematicians later used algorithms in the sieve of Eratosthenes for finding prime numbers, and the Euclidean algorithm for finding the greatest common divisor of two numbers.

Extended Euclidean algorithm

Extended Euclidean algorithm § Simple algebraic field extensionsreversing the steps
By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252.
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

Greatest common divisor

gcdcommon factorgreatest common factor
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.
A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference.

Fraction (mathematics)

denominatorfractionsfraction
It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic.
The Euclidean algorithm gives a method for finding the greatest common divisor of any two positive integers.

Number theory

number theoristcombinatorial number theorytheory of numbers
Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations.
In particular, he gave an algorithm for computing the greatest common divisor of two numbers (the Euclidean algorithm; Elements, Prop.

Gaussian integer

Gaussian integersGaussian primeGaussian primes
The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers.
This makes the Gaussian integers a Euclidean domain, and implies that Gaussian integers share with integers and polynomials many important properties such as the existence of a Euclidean algorithm for computing greatest common divisors, Bézout's identity, the principal ideal property, Euclid's lemma, the unique factorization theorem, and the Chinese remainder theorem, all of which can be proved using only Euclidean division.

Gabriel Lamé

LaméG. LamèLamé, Gabriel
This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory.
He is also known for his running time analysis of the Euclidean algorithm, marking the beginning of computational complexity theory.

Coprime integers

coprimerelatively primepairwise coprime
If gcd(a, b) = 1, then a and b are said to be coprime (or relatively prime).
A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm and its faster variants such as binary GCD algorithm or Lehmer's GCD algorithm.

Euclidean division

Division theoremdividedivisible by two without remainder
The theorem which underlies the definition of the Euclidean division ensures that such a quotient and remainder always exist and are unique.
Euclidean division, and algorithms to compute it, are fundamental for many questions concerning integers, such as the Euclidean algorithm for finding the greatest common divisor of two integers, and modular arithmetic, for which only remainders are considered.

Euclid's Elements

ElementsEuclid's ''ElementsEuclid
It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c.

Euclid

Euclid of AlexandriaEuklidGreek Mathematician
It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c.
It considers the connection between perfect numbers and Mersenne primes (known as the Euclid–Euler theorem), the infinitude of prime numbers, Euclid's lemma on factorization (which leads to the fundamental theorem of arithmetic on uniqueness of prime factorizations), and the Euclidean algorithm for finding the greatest common divisor of two numbers.

Integer

integersintegralZ
By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252.
. The Euclidean algorithm for computing greatest common divisors works by a sequence of Euclidean divisions.

Irreducible fraction

lowest termsin lowest termsreduced fraction
It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic.
In order to find the greatest common divisor, the Euclidean algorithm or prime factorization can be used.

Integer relation algorithm

PSLQ algorithmFerguson–Forcade algorithminteger relation-finding algorithm
The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers.
For the case n = 2, an extension of the Euclidean algorithm can determine whether there is an integer relation between any two real numbers x 1 and x 2.

Division (mathematics)

divisiondividingdivided
It is used for reducing fractions to their simplest form and for performing division in modular arithmetic.

Remainder

in remainderlaver
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.

Principal ideal domain

PIDPrincipal Ideal Domainsprincipal
This GCD definition led to the modern abstract algebraic concepts of a principal ideal (an ideal generated by a single element) and a principal ideal domain (a domain in which every ideal is a principal ideal).
Principal ideal domains are thus mathematical objects that behave somewhat like the integers, with respect to divisibility: any element of a PID has a unique decomposition into prime elements (so an analogue of the fundamental theorem of arithmetic holds); any two elements of a PID have a greatest common divisor (although it may not be possible to find it using the Euclidean algorithm).

Computational complexity theory

computational complexitycomplexity theorycomplexity
This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory.
An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.

Natural number

natural numberspositive integerpositive integers
The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b.
. This Euclidean division is key to several other properties (divisibility), algorithms (such as the Euclidean algorithm), and ideas in number theory.

Eisenstein integer

Eisenstein integersEulerian integerZ'''[ω
In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers.
This algorithm implies the Euclidean algorithm, which proves Euclid's lemma and the unique factorization of Eisenstein integers into Eisenstein primes.

Binary GCD algorithm

Binary GCDbinary version
This is exploited in the binary version of Euclid's algorithm.
Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction.

Fibonacci number

Fibonacci sequenceFibonacci numbersFibonacci series
Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutive Fibonacci numbers.

Continued fraction

continued fractionsconvergentconvergents
The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers.
Continued fractions have a number of remarkable properties related to the Euclidean algorithm for integers or real numbers.

Rational number

rationalrational numbersrationals
The Euclidean algorithm can be used to arrange the set of all positive rational numbers into an infinite binary search tree, called the Stern–Brocot tree.
Every rational number a/b can be represented as a finite continued fraction, whose coefficients a n can be determined by applying the Euclidean algorithm to (a,b).

Modular multiplicative inverse

multiplicative inversemodular inverseinverse mod
In such a field with m numbers, every nonzero element a has a unique modular multiplicative inverse, a −1 such that aa −1 = a −1 a ≡ 1 mod m.
The Euclidean algorithm determines the greatest common divisor (gcd) of two integers, say a and m. If a has a multiplicative inverse modulo m, this gcd must be 1.