The greatest common divisor of two numbers
Suppose we have two ribbons, 84 cm and 30 cm long, and want to cut both into pieces of one length, a whole number of centimetres, with nothing left over. We want the pieces as long as possible. A length works for a ribbon when it divides the ribbon's length, so it has to divide both 84 and 30. A number that divides both is a common divisor of the two, and the largest one is their greatest common divisor, written .
For numbers this small we can list the divisors of each and compare the lists:
| Number | Divisors |
|---|---|
| 84 | 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84 |
| 30 | 1, 2, 3, 5, 6, 10, 15, 30 |
| In both lists | 1, 2, 3, 6 |
So : the long ribbon makes pieces and the short one . The same number reduces a fraction to lowest terms. Dividing the top and bottom of by 6 gives , and no further reduction is possible, because 5 and 14 have no common divisor except 1. Two numbers whose gcd is 1 are called coprime.
Comparing lists means trying every candidate up to the smaller number against both numbers. That is 60 divisions for the ribbons, but contest inputs go up to and beyond, and a pair near would take about divisions. At the rule-of-thumb rate of simple operations a second, that is twenty seconds for one gcd. The method in the next part finds the ribbons' answer in three divisions, and a pair below takes it at most 43, as the cost section further down works out.
Replace the larger number with a remainder
We lay the short ribbon along the long one and cut. Two 30 cm lengths fit along the 84 cm ribbon and leave 24 cm over, which is the division .
Now we compare the pieces that fit before and after the cut. Any length that cuts 84 and 30 evenly also cuts the 24 cm leftover evenly, because the leftover is the long ribbon with two whole 30s removed, and each 30 is a whole number of pieces. In the other direction, any length that cuts 30 and 24 evenly also cuts evenly. So the pair 84 and 30 has exactly the same common divisors as the pair 30 and 24, and the same greatest one.
That turns the question into a smaller one of the same kind, , and the same step applies again:
The last step leaves the pair 6 and 0. Every positive number divides 0, since leaves no remainder, so the common divisors of 6 and 0 are the divisors of 6, and the largest of those is 6 itself. In general . No step changed the common divisors, so , the answer from the lists.
This is the Euclidean algorithm: replace the pair with until the second number is 0, and the first number is then the gcd. Here is the mathematical way to write the remainder a % b.
If the first number is the smaller one, the first step swaps the two: , so becomes .
Worked example
Step through the divisions
The trace shows each step as the current pair and the remainder that replaces it. Start with the ribbons, then try No common factor, which ends at 1, so 17 and 13 are coprime. Fibonacci pair, most steps runs 89 and 55, neighbours in the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13 and so on, where each number is the sum of the two before it. They take nine divisions, more than any other pair below 100 with the larger number first, and Cost of Euclid below shows why. First number is zero turns into in one step and returns 9.
A common divisor must divide both numbers. Replacing the larger part by the remainder preserves those divisors.
Change the example input
Current result: 6
See the divisions as squares in a rectangle
The same steps have a picture. We draw the ribbons as the sides of an 84 by 30 rectangle. A piece length that cuts both ribbons evenly is the side of a square that tiles the whole rectangle. Each division cuts off as many of the largest squares as fit, two squares of side 30 at first, and leaves a smaller rectangle for the next division. The last squares fit with nothing left over, and their side is the gcd.
The example 21, 13 ends with squares of side 1, and in 35, 100 the first number is the smaller one, so the first step only swaps the sides.
The Euclidean algorithm in code
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(gcd(84, 30))
print(gcd(30, 84))
print(gcd(0, 9))
print(gcd(0, 0))The line a, b = b, a % b works out both new values from the old pair before it assigns either of them. Written as two statements, a = b and then b = a % b, the second would compute b % b, which is 0.
The loop runs only while b is not 0, so it never divides by zero. When b is 0 from the start it returns a unchanged, which for 0 and 0 gives 0. The library functions return 0 for that pair as well.
In practice we call the library function math.gcd(a, b). It takes negative numbers too and returns the gcd of their absolute values.
Why it is correct
Replacing with does not change the set of common divisors.
The ribbon argument works for any pair. Write the division as . A number that divides and also divides , and a number that divides and also divides . This is a loop invariant, a statement that is true before every turn: the common divisors of the current pair are the common divisors of the two inputs.
The loop also has to end. Each remainder is smaller than the number it was divided by, so the second number of the pair gets smaller every turn, and it cannot go below 0.
Cost of Euclid
- Try every candidate up to the smaller number
- Two divisions per candidate: 866,988,874 for 701,408,733 and 433,494,437, one of the slowest pairs below for Euclid.
- Euclidean algorithm
- The first number of the pair at least halves every two steps. The same pair takes 42 divisions.
The steps are few because a remainder is small: when , the remainder is less than half of . If is at most half of , the remainder is smaller than and so smaller than half of . If is more than half of , it fits into only once, and the remainder is again less than half of . For the ribbons, is less than 42.
Two steps turn the pair into and then into , where . So every two steps the first number of the pair drops to less than half of what it was. The halving starts from the smaller input, because within two steps the smaller input is the first number of the pair: becomes , and becomes and then . A number below can be halved about 30 times before it reaches 0, so the loop takes at most about 60 steps.
The slowest inputs are neighbouring Fibonacci numbers such as 89 and 55. Each Fibonacci number is the sum of the two before it, so , then , and so on down the sequence. Every quotient but the last is 1, and each step removes as little as possible. The largest such pair below is the one in the table. By Lamé's theorem, which the cp-algorithms page under Further reading states, its 42 divisions are the most that any pair below needs when the larger number comes first, well under the bound of about 60 from halving. With the smaller number first, the swap adds one more.
The least common multiple
The gcd is the largest number that fits into both inputs. The opposite question asks for the smallest number that both inputs fit into. Two buses leave a station together. One returns every 84 minutes and the other every 30. They are next at the station together after a number of minutes that is a multiple of 84 and also a multiple of 30. Such a number is a common multiple, and the smallest positive one is the least common multiple, .
We could step through the multiples of 84 until one is a multiple of 30: 84, 168, 252, 336, 420. The gcd gets there without a search. We split each number into the gcd and what is left, and . A multiple of 84 is for some whole number , and it is also a multiple of when is a multiple of 5.
For from 1 to 4 that product is 14, 28, 42 and 56, none of them a multiple of 5, and gives 70. So the first that works is 5, the other leftover part. The same happens for every pair. What is left of two numbers after dividing by their gcd is always coprime, since a shared divisor would have made the gcd larger, and for coprime parts the first that works is the other part itself.
The Euclidean algorithm shows why. Run it on and : its divisions are the ones for 14 and 5 with the pair and the remainder multiplied by , so , then , then , and it ends at . The algorithm keeps the common divisors the same at every step, so a number that divides both and divides . When is a multiple of 5, 5 divides both numbers, so is a multiple of 5, and the smallest such is 5. Any two coprime parts work the same way, because their Euclidean algorithm ends at 1.
So the least common multiple is : the gcd once, times what is left of each number. Since 14 is and is 30, the same product can be written from the two inputs and their gcd:
After 420 minutes the first bus has made 5 round trips and the second 14.
def lcm(a, b):
if a == 0 or b == 0:
return 0
return a // gcd(a, b) * b
print(lcm(84, 30))
print(lcm(0, 5))
print(lcm(100000, 99999))Python 3.9 and later also provide math.lcm.
The first line of the function handles 0. The only common multiple of 0 and another number is 0, and returning it early also keeps the function from dividing by .
The gcd of more than two numbers
The next problem gives a whole array of numbers and needs only two of them:
You get an array nums of positive integers. Return the greatest common divisor of the smallest and the largest number in it.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [2,5,6,9,10]
Output
2
Sample 2 · Input
nums = [7,5,6,8,3]
Output
1
Sample 3 · Input
nums = [3,3]
Output
3
In the first sample the smallest value is 2 and the largest is 10, and . One pass finds both ends, and one call to the library gcd finishes:
def find_gcd(nums):
low = high = nums[0]
for x in nums:
low = min(low, x)
high = max(high, x)
return gcd(low, high)
print(find_gcd([2, 5, 6, 9, 10]))
print(find_gcd([7, 5, 6, 8, 3]))
print(find_gcd([3, 3]))For the gcd of all the numbers, we combine them two at a time. Suppose a third ribbon, 45 cm long, joins the first two. A length that cuts all three evenly cuts the first two evenly, so it divides , and it also has to divide 45. The longest such length is therefore the gcd of 6 and 45:
In code, we keep a running gcd g and combine each number into it, starting g at 0. Since , the first number passes through unchanged, and an array of one number gives that number.
def gcd_of_list(nums):
g = 0
for x in nums:
g = gcd(g, x)
return g
print(gcd_of_list([84, 30, 45]))
print(gcd_of_list([84, 30]))
print(gcd_of_list([7]))Once g reaches 1 it stays 1, because 1 has no other divisor, so a loop over a long array can stop there. The lcm of many numbers combines the same way, two at a time, starting from 1.
Common GCD and LCM mistakes
Changing
abefore taking the remainder.- Where it breaks
- With
a = bfollowed byb = a % b, the second line computesb % b = 0, andgcd(84, 30)returns 30. - The fix
- Compute the remainder from the old pair first: a tuple assignment in Python, a temporary variable in C++.
Starting a running gcd at 1.
- Where it breaks
- for every , so the gcd of 84, 30 and 45 comes out as 1 instead of 3.
- The fix
- Start at 0, because .
Dividing by the gcd when both inputs can be 0.
- Where it breaks
- , so
a / gcd(a, b)divides by zero for the pair 0 and 0. - The fix
- Return 0 for the lcm when either input is 0, before dividing.
Recall Run the Euclidean algorithm on 21 and 13. How many divisions does it take, and what does the result say about the fraction 13/21?
The divisions are , , , , and . That is six divisions, and the gcd is 1. So 21 and 13 are coprime, and is already in lowest terms. Every quotient but the last is 1, because 13 and 21 are neighbouring Fibonacci numbers.