Greatest common divisor

The greatest positive integer that divides each of two or more integers without remainder. It captures their largest shared factor.

Euclidean algorithm: A procedure for finding the greatest common divisor by repeatedly replacing a pair with the smaller number and their remainder. Repeated division computes the divisor without listing all factors.
Divisibility: The relation in which one integer is a multiple of another integer. The greatest common divisor is defined by which integers divide every input.
Fraction reduction: The process of expressing a fraction with numerator and denominator divided by their greatest common divisor. The greatest common divisor removes every shared factor in one step.
Least common multiple: The smallest positive integer divisible by each of two or more given integers. It concerns shared multiples, whereas the greatest common divisor concerns shared divisors.
Bézout's identity: The theorem that the greatest common divisor of two integers is an integer linear combination of them. It characterizes the divisor through combinations, not just divisibility.
Integer: A whole number, including zero and the negative whole numbers. The definition applies to integers, with a positive result for nonzero inputs.
Modular arithmetic: Arithmetic in which integers are considered equivalent when they differ by a multiple of a fixed modulus. Coprimality with the modulus determines whether multiplication has an inverse.
Rational greatest common divisor: A generalized common-divisor notion for rational numbers, defined up to multiplication by a nonzero rational unit. For integer inputs, the conventional greatest common divisor is a positive integer with a fixed size.
Extended Euclidean algorithm: An extension of the Euclidean algorithm that also finds coefficients expressing the greatest common divisor as a linear combination. It turns the computation into explicit Bézout coefficients.
Factor (arithmetic): An integer that divides another integer without remainder. Common factors are the candidates from which the greatest is selected.

Linked from 38 pages