GCD, LCM, and Euclid's Algorithm
Throughout this lesson, all inputs are nonnegative integers.
The greatest common divisor, , is the largest positive integer dividing both and , provided at least one is nonzero.
Every positive integer divides zero. Therefore, when , the common divisors of and are exactly the divisors of , giving . We also set by convention; in that case, there is no largest positive common divisor.
We can reduce the numbers without changing their common divisors. For , divide by and write , where is the quotient and is the remainder.
Any number dividing both and also divides . Conversely, any number dividing both and divides . Thus the pairs and have exactly the same common divisors:
Euclid's algorithm repeatedly applies this replacement. Each new second argument is smaller than the previous one, so eventually it becomes zero. The first argument is then the answer.
The diagram follows the pair . Each row splits the first number into complete copies of the second number and a remainder. The blue remainder becomes the second argument in the next row.
The second argument need not halve in one step: above, it first decreases from to . However, it at least halves within two steps.
If , the first step swaps the two numbers. Once , let :
The algorithm therefore uses remainder operations, including the zero-input cases.
It preserves the GCD: when , the pairs and have the same common divisors. The other case is symmetric. Both numbers stay positive and their sum decreases, so the process reaches equal numbers; their common value is the original GCD.
The iteration bound is different. Starting with requires subtractions. Euclid's remainder operation removes all complete copies at once, so it finishes this case in one step.
While the GCD measures shared divisors, the least common multiple, , is the smallest positive integer divisible by both positive inputs. If either input is zero, we define the LCM to be zero, including .
To relate the two operations, consider prime factorization. A prime is an integer at least with no positive divisors other than and itself. Every positive integer has a unique prime factorization; has no prime factors.
For a prime , let and be its exponents in and , using zero when is absent. A common divisor can contain at most copies of , and the GCD uses exactly that many. A common multiple needs at least copies, and the LCM uses exactly that many.
Multiplying the GCD and LCM adds these exponents. Since their sum is for every prime, the product is . Hence, for positive ,
Compute the division before the multiplication. The product might overflow even when the LCM fits, whereas is an integer no larger than .
The final product can still be too large. Let be the largest value of long long, given by LLONG_MAX, and set . For , multiplying by is safe exactly when
Check this inequality before multiplying. Handle zero inputs first so that neither this check nor the GCD division can divide by zero.
Both operations are associative: grouping the elements differently does not change the answer. A number divides every element exactly when it divides their GCD, and a number is a common multiple of every element exactly when it is a multiple of their LCM. These descriptions do not depend on grouping. The zero conventions preserve associativity as well.
For the GCD of a nonempty list , start with and process each element using
The initial zero works because . Once , further elements cannot change it.
For the LCM, first check whether the list contains zero. If it does, the answer is zero. Otherwise, start with and repeatedly combine with the next element, checking for overflow each time. Every new LCM is a positive multiple of the previous one. Therefore, if a partial result exceeds the limit, the final result must also exceed it.
Checking for zero first is essential when stopping at the first overflow: a zero later in the list would make the final answer zero instead.
Take , , and . Their GCD is , but their LCM is , whereas . No prime divides all three numbers, yet each prime factor is shared by a pair.
The equality holds exactly when every pair has GCD : the numbers are pairwise coprime. If their prime factors are disjoint, the largest exponent of each prime equals its exponent in the product. If a prime divides two numbers, its exponent in the product is strictly greater than its largest exponent in any one number, so the product exceeds the LCM.
Both arguments must fit in long long and be nonnegative. The function returns if the LCM exceeds LLONG_MAX.
For positive and , consider repeatedly subtracting the smaller number from the larger one until they become equal. Does this procedure preserve the GCD? Does it have the same logarithmic bound on the number of iterations? Justify both answers.
Let be positive integers with . Must ? If not, construct a counterexample. Find the exact condition on the three pairwise GCDs that makes the equality hold.
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
while (b > 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
long long lcm_safe(long long a, long long b) {
if (a == 0 || b == 0) {
return 0;
}
a /= gcd(a, b);
if (a > LLONG_MAX / b) {
return -1;
}
return a * b;
}