The greatest common divisor of two or more integers is the largest positive integer that divides every one of them with no remainder. It is written (gcd(a,b)). The GCD is useful for reducing fractions, simplifying ratios, grouping objects into equal sets, and finding the largest tile or repeated interval that fits exact lengths.
Divisors explain what “greatest common” means
The positive divisors of 18 are 1, 2, 3, 6, 9, and 18. Those of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. Their common divisors are 1, 2, 3, and 6, so the greatest is 6. Listing works well for small numbers but becomes slow and error-prone as values grow.
Try two positive integers below. The calculation uses Euclid's algorithm and exposes each remainder rather than returning an unexplained answer.
Follow Euclid's algorithm
Each line divides the previous pair; the last nonzero remainder is the GCD.
Prime factorization keeps only shared powers
Factor each number into primes. For every prime appearing in all numbers, keep the smallest exponent and multiply those selected powers. This method shows the structure clearly and extends naturally to three or more integers, provided their prime factorizations are manageable.
For 84 and 126, the shared prime powers are one factor of 2, one of 3, and one of 7. Their product is 42. Check by division: 84 divided by 42 is 2, while 126 divided by 42 is 3. No larger common divisor is possible because at least one factorization lacks every extra prime power.
Euclid's algorithm scales to large integers
If (a>b>0), divide (a) by (b). Replace the pair by (b) and the remainder, then repeat. The common divisors do not change because any number dividing both (a) and (b) also divides the remainder (a-qb). When the remainder becomes zero, the last nonzero remainder is the GCD.
With 252 and 105, the successive remainders are 42 and 21, followed by zero. Therefore the GCD is 21. This takes only a few divisions and avoids fully factoring either number. If one input is zero, the standard convention is (gcd(a,0)=|a|); the pair (0,0) is commonly left undefined.
Identities provide useful checks
The GCD is unchanged when the numbers are swapped and is always positive under the usual convention. Dividing both inputs by their GCD produces coprime integers. The product of the positive GCD and least common multiple equals the absolute product of the two inputs, which supplies a useful check when both quantities are calculated.
Choosing the right real-world interpretation
Suppose a floor measures 252 cm by 105 cm and must be covered by the largest possible square tiles without cutting. The tile side must divide both lengths, so it is 21 cm. That gives 12 tiles along one side and 5 along the other, for 60 tiles in total.
The GCD applies only when the requirement is an exact shared division. If offcuts are allowed, dimensions are measured approximately, or a tolerance matters, the pure integer model may not answer the practical question. Convert all lengths to the same exact unit before using the algorithm.
