Linked from

The 31 pages that link to Euclidean algorithm, each with the reason it gives.

• Rational numberRelated: It efficiently reduces a fraction to lowest terms.

• IntegerRelated: It reduces integer divisibility questions to a sequence of smaller remainders.

• DivisibilityRelated: It reduces common-divisor calculations to a sequence of divisibility checks.

• Number theoryRelated: It turns common-divisor questions into a finite sequence of exact divisions.

• Diophantine equationRelated: It solves linear integer equations and underlies many divisibility arguments.

• Greatest common divisorRelated: Repeated division computes the divisor without listing all factors.

• Continued fractionRelated: Repeated division converts a rational number into a finite continued fraction.

• Coprime integersRelated: It tests whether a pair is coprime without factoring either integer.

• Gaussian integerRelated: Using the Gaussian norm, it computes greatest common divisors in ℤ[i].

• Euclid's lemmaRelated: Its gcd calculations provide a route to the coprimality argument used in proofs of the lemma.

• Modular exponentiationRelated: It tests whether a base has a multiplicative inverse modulo the chosen modulus.

• Straightedge and compass constructionRelated: Its geometric analogue underlies constructions of lengths by subtraction and division.

• Least common multipleRelated: It computes the greatest common divisor used in the efficient two-number least-common-multiple formula.

• Even numberRelated: Its divisions expose remainders and parity can simplify particular inputs.

• Jacobi symbolRelated: Jacobi-symbol reciprocity reduces evaluation along remainder steps much like the Euclidean algorithm.

• Primitive recursive functionRelated: Its bounded arithmetic operations and recursion can be represented primitively recursively.

• Lowest termsRelated: It efficiently finds the common divisor needed to reduce large fractions.

• Repeating decimalRelated: Reducing the fraction behind a decimal helps determine its repeating block's length.

• Qin JiushaoRelated: Coprimality and divisibility govern whether Qin’s congruence combinations work.

• Divisibility ruleRelated: Repeated-remainder reasoning underlies some divisibility tests and explains why they preserve divisibility.