Linked from

The 38 pages that link to Greatest common divisor, each with the reason it gives.

• Prime numberRelated: A prime's restricted divisors make common-divisor calculations especially simple.

• Rational numberRelated: Dividing numerator and denominator by it gives a fraction in lowest terms.

• Modular arithmeticRelated: Coprimality with the modulus determines whether a residue has a multiplicative inverse.

• Diophantine equationRelated: Common divisors determine when linear equations in integers can be solved.

• Prime factorizationRelated: Shared prime factors determine the greatest common divisor.

• Chinese remainder theoremRelated: Pairwise greatest common divisors determine whether prescribed remainders agree.

• Fundamental theorem of arithmeticRelated: Coprimality, expressed through greatest common divisors, helps explain why prime factors cannot be redistributed.

• Aspect ratioRelated: Reducing pixel dimensions to simplest terms reveals their ratio.

• Integer factorizationRelated: Computing a greatest common divisor can expose a shared nontrivial factor.

• Congruence (number theory)Related: It determines whether a coefficient can be cancelled or inverted modulo the modulus.

• Coprime integersRelated: Coprimality is defined by this value being 1.

• Euler's totient functionRelated: Testing whether gcd(k,n) equals 1 determines which integers contribute to φ(n).

• Diophantine approximationRelated: Reducing a fraction to coprime numerator and denominator makes denominator bounds meaningful.

• Composite numberRelated: Computing gcds can expose nontrivial factors of a composite number.

• Empirical formulaRelated: Once atom ratios are whole numbers, dividing by their common divisor simplifies them.

• Euclid's lemmaRelated: The proof uses a greatest common divisor of the prime and an undivided factor.

• Pythagorean tripleRelated: It distinguishes primitive triples from triples that share a common scale factor.

• InfimumRelated: In divisibility order, a greatest common divisor is an infimum.

• Rational root theoremRelated: A rational root is in lowest terms when its numerator and denominator have greatest common divisor one.

• RemainderRelated: Repeated remainders provide the standard algorithm for finding it.

• Shor's algorithmRelated: Classical postprocessing uses greatest common divisors to turn a suitable order into factors.

• Least common multipleRelated: For positive integers, multiplying the inputs and dividing by their greatest common divisor gives their least common multiple.

• Unique factorizationRelated: Prime exponents reveal the greatest common divisor by taking their shared minima.

• Jacobi symbolRelated: A zero Jacobi symbol occurs exactly when numerator and denominator are not relatively prime.

• Lowest termsRelated: Dividing both parts of a fraction by this number produces its lowest terms.

• Wilson's theoremRelated: Invertibility modulo n depends on having greatest common divisor one with n.

• Sturm's theoremRelated: A shared factor of a polynomial and its derivative signals repeated roots and can end the remainder sequence early.

• Star polygonRelated: The divisor of the vertex count and step size predicts whether a construction closes as one circuit.

• Lifting-the-exponent lemmaRelated: Coprimality conditions often ensure the lemma applies without shared prime factors.

• Beal's conjectureRelated: A shared prime factor is equivalent to the bases having a greatest common divisor greater than one.