15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The Euclidean algorithm finds the greatest common divisor of two numbers by repeated division. Replace the pair (a, b) with (b, a mod b) until b is 0, and the remaining a is the GCD. It takes O(log(min(a, b))) steps with O(1) space, and the LCM follows as (a / gcd) × b.
| Recurrence | gcd(a, b) = gcd(b, a mod b) while b is not 0 |
|---|---|
| Stop | When b = 0, return a |
| Time | O(log(min(a, b))) for positive inputs |
| Extra space | O(1): a, b and the remainder |
| LCM | (a / gcd(a, b)) × b, dividing first; gcd × lcm = a × b for positive inputs |
| Zero cases | gcd(a, 0) = a, gcd(0, 0) = 0, lcm(a, 0) = 0 |
Assume you can factor a number into primes.
For two nonnegative integers:
gcd(a, b), is the largest positive integer that divides both numbers.lcm(a, b), is the smallest positive integer divisible by both positive numbers.Use these course conventions for zero:
gcd(a, 0) = a when a is nonnegative.gcd(0, 0) = 0.lcm(a, 0) = 0.The division algorithm drives Euclid's algorithm. When b > 0, divide a by b:
where:
q is the quotient,r is the remainder,Euclid's algorithm uses:
as long as b is not 0.
Compute:
Use factorization to determine the expected answers.
For the GCD, keep only primes shared by both factorizations. Use the smaller shared exponent:
For the LCM, include every prime that appears. Use the larger exponent:
Factorization defines the GCD and LCM. Euclid's algorithm computes the GCD without listing prime factors.
Start with the ordered pair:
Euclid's algorithm replaces (a, b) with (b, a mod b) until b is 0. For (84, 30) the pairs are (30, 24), (24, 6), (6, 0), so gcd = 6 and lcm = 420.
Divide the first number by the second.
The remainder is 24. Replace the pair (84, 30) with (30, 24).
Current a | Current b | Division | Remainder | Next pair |
|---|---|---|---|---|
| 84 | 30 | 24 | (30, 24) | |
| 30 | 24 | 6 | (24, 6) | |
| 24 | 6 | 0 | (6, 0) |
Now b is 0, so stop. The current first value is the GCD:
Use that result to compute the LCM:
Divide before multiplying. In a language with bounded integers, this can reduce the risk of an intermediate multiplication overflow.
Check the positive-input relationship:
For this pair:
At every step, the current pair has exactly the same common divisors as the previous pair.
For the first update, compare (84, 30) with (30, 24).
Since:
any number that divides both 84 and 30 must also divide:
So every common divisor of (84, 30) is also a common divisor of (30, 24).
The reverse direction also holds. If a number divides both 30 and 24, then it divides:
So it divides both 84 and 30.
For every update, the division equation gives these two directions. The loop invariant is:
At every Euclidean step, the set of common divisors of the current pair
(a, b)is the same as the set of common divisors of the previous pair.
The pair changes while its set of common divisors remains unchanged.
Suppose b is positive. Divide a by b:
where:
A number d divides both a and b exactly when it divides both b and r:
d divides a and b, it divides .d divides b and r, it divides .Therefore:
Use the repeated update:
Each nonzero remainder is smaller than the divisor used to produce it:
The second value cannot stay positive forever. Eventually it becomes 0.
At that point the pair is (a, 0). Every positive divisor of a divides 0, so the common divisors of (a, 0) are exactly the divisors of a. The greatest one is a.
For positive inputs, compute the LCM after finding the GCD:
The standard GCD-LCM relationship is:
The formula produces a common multiple and gives the least common multiple for positive inputs.
The Euclidean remainder recurrence and termination mechanism are described in the source packet.
GCD accepts nonnegative integers. It does not mutate caller-owned values; a and b are local variables.
1function GCD(a, b) -> nonnegative integer
2 input:
3 a, b: nonnegative integers
4 returns:
5 gcd(a, b), using gcd(0, 0) = 0
6 mutation:
7 does not mutate the caller's inputs
8
91. while b != 0
102. remainder <- a mod b
113. a <- b
124. b <- remainder
135. return aThe assignments on lines 3 and 4 implement the pair replacement:
LCM also accepts nonnegative integers. It handles zero before dividing.
1function LCM(a, b) -> nonnegative integer
2 input:
3 a, b: nonnegative integers
4 returns:
5 lcm(a, b), using lcm(a, 0) = 0
6 mutation:
7 does not mutate the caller's inputs
8 helper contract:
9 GCD(x, y) returns gcd(x, y) for nonnegative integers x and y
10
111. if a == 0 or b == 0
122. return 0
133. divisor <- GCD(a, b)
144. return (a / divisor) * bFor line 4, divisor is nonzero because both inputs are positive after the zero check.
Run GCD(84, 30).
| Pseudocode line | a | b | remainder | What happens |
|---|---|---|---|---|
| Start | 84 | 30 | — | Enter GCD(84, 30). |
| 1 | 84 | 30 | — | b != 0, so continue. |
| 2 | 84 | 30 | 24 | Set remainder <- 84 mod 30. |
| 3 | 30 | 30 | 24 | Set a <- b. |
| 4 | 30 | 24 | 24 | Set b <- remainder. The pair is now (30, 24). |
| 1 | 30 | 24 | — | b != 0, so continue. |
| 2 | 30 | 24 | 6 | Set remainder <- 30 mod 24. |
| 3 | 24 | 24 | 6 | Set a <- b. |
| 4 | 24 | 6 | 6 | Set b <- remainder. The pair is now (24, 6). |
| 1 | 24 | 6 | — | b != 0, so continue. |
| 2 | 24 | 6 | 0 | Set remainder <- 24 mod 6. |
| 3 | 6 | 6 | 0 | Set a <- b. |
| 4 | 6 | 0 | 0 | Set b <- remainder. The pair is now (6, 0). |
| 1 | 6 | 0 | — | b == 0, so leave the loop. |
| 5 | 6 | 0 | — | Return 6. |
Run LCM(84, 30).
| Pseudocode line | State | What happens |
|---|---|---|
| 1 | a = 84, b = 30 | Neither input is zero. Do not return. |
| 3 | divisor = 6 | GCD(84, 30) returns 6. |
| 4 | (84 / 6) × 30 | Compute 14 × 30, then return 420. |
The product check is:
The two products match.
Before the loop begins, the current pair is the input pair (a, b). Its common divisors are, by definition, the common divisors of the original inputs.
The invariant holds initially.
Assume the current pair is (a, b) with b != 0.
Line 2 computes:
By the division algorithm:
A number divides both a and b if and only if it divides both b and r. Therefore the pairs (a, b) and (b, r) have the same set of common divisors.
Lines 3 and 4 replace (a, b) with (b, r). The invariant remains true.
When b != 0, the next second value is:
and it satisfies:
Each nonzero second value is smaller than the previous nonzero second value. Nonnegative integers cannot strictly decrease forever, so eventually b becomes 0.
At termination, the pair is (a, 0). Every divisor of a divides 0, so the common divisors of (a, 0) are exactly the divisors of a. Therefore a is the GCD.
Because the invariant says the final pair has the same common divisors as the original pair, GCD returns the GCD of the original inputs.
If either LCM input is zero, LCM returns 0, matching the selected convention.
Otherwise both inputs are positive. Let:
The algorithm returns:
The standard positive-input relationship is:
Rearranging gives:
So LCM returns the least common multiple.
One GCD loop iteration performs these operations:
a mod b.b into a.b.Each iteration changes:
The second value is a nonnegative remainder smaller than the prior nonzero second value. Standard Euclidean analysis bounds the number of remainder steps for positive inputs by:
Therefore:
GCD(a, b) takes time for positive inputs.GCD uses auxiliary space because it keeps only a, b, and remainder.LCM(a, b) performs one GCD computation plus a constant number of arithmetic operations.For positive inputs:
LCM takes time.LCM uses auxiliary space.aIncorrect update:
1a <- a mod bwhile leaving b unchanged.
Exposing input:
1GCD(84, 30)After the first remainder, the state becomes (24, 30) instead of (30, 24). The intended Euclidean pair replacement did not happen. A later iteration can repeat or stall in an incorrect state.
Correction: update the pair to (b, a mod b) using a temporary remainder.
1remainder <- a mod b
2a <- b
3b <- remainderIncorrect stopping assumption:
1if a mod b == 0
2 return 0Exposing input:
1GCD(24, 6)The remainder is 0, but the GCD is 6.
Correction: after updating (24, 6) to (6, 0), return the current a, which is the last nonzero value.
Incorrect formula:
1return a * bExposing input:
1LCM(12, 18)Wrong output:
But:
so the correct result is:
Correction:
1return (a / GCD(a, b)) * bfor positive inputs.
Incorrect order:
1divisor <- GCD(a, b)
2return (a / divisor) * bExposing input:
1LCM(0, 0)Here GCD(0, 0) is 0 under this course convention. Dividing by 0 fails.
Correction: handle any zero input before calling the division formula.
1if a == 0 or b == 0
2 return 0| Input | Expected GCD | Expected LCM |
|---|---|---|
(0, 15) | 15 | 0 |
(15, 0) | 15 | 0 |
(0, 0) | 0 | 0 |
(17, 17) | 17 | 17 |
(8, 15) | 1 | 120 |
For (8, 15), the GCD is 1, so:
Implement:
gcd(a, b) for nonnegative integers, with gcd(0, 0) = 0.lcm(a, b) for nonnegative integers, with lcm(a, 0) = 0.The tests verify exact GCD and LCM values and, for positive inputs, verify:
1def gcd(a, b):
2 while b != 0:
3 remainder = a % b
4 a = b
5 b = remainder
6 return a
7
8def lcm(a, b):
9 if a == 0 or b == 0:
10 return 0
11 return (a // gcd(a, b)) * b # divide first to keep the product small
12
13print("gcd(84, 30) =", gcd(84, 30))
14print("lcm(84, 30) =", lcm(84, 30))
15print("gcd(0, 0) =", gcd(0, 0))
16print("lcm(8, 15) =", lcm(8, 15))1public class Main {
2 static long gcd(long a, long b) {
3 while (b != 0) {
4 long remainder = a % b;
5 a = b;
6 b = remainder;
7 }
8 return a;
9 }
10
11 static long lcm(long a, long b) {
12 if (a == 0 || b == 0) return 0;
13 return (a / gcd(a, b)) * b; // divide first to keep the product small
14 }
15
16 public static void main(String[] args) {
17 System.out.println("gcd(84, 30) = " + gcd(84, 30));
18 System.out.println("lcm(84, 30) = " + lcm(84, 30));
19 System.out.println("gcd(0, 0) = " + gcd(0, 0));
20 System.out.println("lcm(8, 15) = " + lcm(8, 15));
21 }
22}1#include <iostream>
2using namespace std;
3
4long long gcdEuclid(long long a, long long b) {
5 while (b != 0) {
6 long long remainder = a % b;
7 a = b;
8 b = remainder;
9 }
10 return a;
11}
12
13long long lcmEuclid(long long a, long long b) {
14 if (a == 0 || b == 0) return 0;
15 return (a / gcdEuclid(a, b)) * b; // divide first to keep the product small
16}
17
18int main() {
19 cout << "gcd(84, 30) = " << gcdEuclid(84, 30) << endl;
20 cout << "lcm(84, 30) = " << lcmEuclid(84, 30) << endl;
21 cout << "gcd(0, 0) = " << gcdEuclid(0, 0) << endl;
22 cout << "lcm(8, 15) = " << lcmEuclid(8, 15) << endl;
23}1function gcd(a, b) {
2 while (b !== 0) {
3 const remainder = a % b;
4 a = b;
5 b = remainder;
6 }
7 return a;
8}
9
10function lcm(a, b) {
11 if (a === 0 || b === 0) return 0;
12 return (a / gcd(a, b)) * b; // divide first to keep the product small
13}
14
15console.log("gcd(84, 30) = " + gcd(84, 30));
16console.log("lcm(84, 30) = " + lcm(84, 30));
17console.log("gcd(0, 0) = " + gcd(0, 0));
18console.log("lcm(8, 15) = " + lcm(8, 15));Write a = q × b + r. Any number dividing a and b divides a - q × b = r, and any number dividing b and r divides q × b + r = a. So (a, b) and (b, r) have the same common divisors, and the loop never changes the answer.
Each new second value a mod b is smaller than b and never negative. A nonnegative integer cannot shrink forever, so b reaches 0. The pair is then (a, 0), whose common divisors are the divisors of a.
Write the loop shown above, or call the library: math.gcd in Python and std::gcd from
For positive a and b, gcd(a, b) × lcm(a, b) = a × b. For 84 and 30, 6 × 420 = 2520 = 84 × 30. Compute the GCD first, then divide before you multiply.
The product counts shared prime factors twice. For 12 and 18, a × b = 216, but gcd = 6 and the least common multiple is (12 / 6) × 18 = 36.