How to use the GCD function
What is the GCD function?
The GCD calculates the greatest common divisor that divides all given arguments without a remainder.
Introduction
What is the greatest common divisor?
The greatest common divisor of two or more integers is the largest integer that divides them all. For two numbers number1 and number2, it is the largest integer that divides both number1 and number2 without remainder.
For example:
- greatest common divisor(8,12) = 4
This is because 4 is the largest number that divides both 8 and 12. - greatest common divisor(18,24) = 6
6 is the greatest common factor of 18 and 24. - greatest common divisor(10,15,25) = 5
5 is the largest number that divides 10, 15 and 25.
Both the Euclidean algorithm and the prime factorization method can be used to find the greatest common divisor of two or more integers. The Euclidean algorithm is generally more efficient for larger numbers, while the prime factorization method can be more intuitive for smaller numbers.
Here's how the Euclidean algorithm works, step-by-step:
- Start with two positive integers, say a and b, where a > b.
- Divide a by b and get the quotient q and remainder r, such that a = b * q + r.
- If r = 0, then greatest common divisor(a, b) = b, since b is a divisor of a.
- If r ≠ 0, then greatest common divisor(a, b) = greatest common divisor(b, r), since the greatest common divisor of a and b is the same as the greatest common divisor of b and the remainder r.
- Replace a with b and b with r, and repeat steps 2-4 until the remainder becomes 0.
The key idea behind the Euclidean algorithm is that if we have two numbers, a and b, and we divide a by b, the GCD of a and b is the same as the GCD of b and the remainder of the division. This is because any common divisor of a and b must also be a divisor of the remainder (r = a - b * q).
By repeatedly replacing the larger number with the smaller number and the smaller number with the remainder, we eventually reach a point where the remainder becomes 0. At this point, the smaller number (b) is the GCD of the original two numbers (a and b).
The Euclidean algorithm is efficient because the number of steps required is approximately proportional to the number of digits in the smaller of the two input numbers, making it much faster than other methods for large numbers.
What is a remainder?
A remainder is the amount left over after dividing two integers.
The remainder is what is left after dividing two integers. If you divide 15 with 2 you get 7 and 1 is left over. 2*7 equals 14. 15 - 14 equals 1. The remainder is 1.
What is a divisor?
A divisor is a number that divides into another number either cleanly or leaving a remainder.
dividend / divisor = quotient( + remainder)
What is a dividend?
In division, the dividend is the number being divided.
For example, in the division:
15 / 5 = 3
15 is the dividend 5 is the divisor and 3 is the quotient
What is a quotient?
The quotient is the result when two numbers are divided.
What is a factor?
A factor is a number that divides evenly into another number, in other words, without leaving a remainder.
When is the greatest common divisor useful?
The GCD can be used to reduce fractions to their simplest form. For example, greatest common divisor(36,68) = 4 can simplify 36/68 to 9/17.
Finding least common multiples is the product of two numbers divided by their greatest common divisor. Excel has the LCM function that you can use instead of calculating the least common multiple.
What other Excel functions are about division, dividend, divisor, and quotient?
| Excel Function | Description |
| GCD | Returns the greatest common divisor of two numbers |
| LCM | Returns the least common multiple of two numbers |
| QUOTIENT | Returns the integer portion of a division between two numbers |
| MOD | Returns the remainder after dividing num1 by num2 |
2. Syntax
GCD(number1, [number2], ...)
| number1 | Required. A single numerical value or a cell reference to multiple numerical values. |
| [number2] | Optional. Upp to 254 additional arguments. |
3. Example 1
This example demonstrates how to calculate the greatest common divisor using the GCD function. The image above shows the arguments in cell range B3:C7 and the results in cell range E3:E7.
The first argument pair is 2 and 6 which are displayed in cells B3:C3 respectively. Cell E3 which contains the formula below returns 2. 2 is the greatest common divisor based on 2 and 6.
Formula in cell E3:
Lets calculate this manually:
- Divide a by b and get the quotient q and remainder r, such that a = b * q + r.
a = 6, b = 2
a / b = 6 / 2 = 3 + 0, q = 3, r = 0 - If r = 0, then greatest common divisor(a, b) = b, since b is a divisor of a.
greatest common divisor(6, 2) = 2
Our calculated value 2 matches the result in cell E3.
The next argument pair I want to demonstrate is in cells B5:C5 which contain 20 and 15. Cell E5 which contains the formula below returns 5. 5 is the greatest common divisor based on 20 and 15.
Formula in cell E3:
Lets calculate this manually:
- Divide a by b and get the quotient q and remainder r, such that a = b * q + r.
a= 20, b = 15
a/b = 20/15 = 1 + 5, q = 1, r = 5 - If r ≠ 0, then greatest common divisor(a, b) = greatest common divisor(b, r), since the greatest common divisor of a and b is the same as the greatest common divisor of b and the remainder r.
- Replace a with b and b with r, and repeat above steps until the remainder becomes 0.
- a = 15, b = 5
a/b = 15/5 = 3 + 0, q = 3, r = 0 - If r = 0, then greatest common divisor(a, b) = b, since b is a divisor of a.
greatest common divisor(15, 5) = 5
The calculated value 5 matches the result in cell E5.
4. Example 2
A company has three machines that require maintenance every 6, 15, and 18 days respectively. To optimize maintenance scheduling and minimize downtime, they want to find the common interval when all three machines need maintenance?
The arguments 6, 15, and 18 are in cells C2:C4 respectively.
Formula in cell E3:
The formula in cell E3 returns 3, this means that the common maintenance interval for all three machines is 3 days.
5. The function is not working?
The GCD function returns
- #NUM! error value if any number is less than 0 (zero).
- #VALUE! error value if any argument is not a numerical number.
Functions in 'Math and trigonometry' category
The GCD function function is one of 62 functions in the 'Math and trigonometry' category.
How to comment
How to add a formula to your comment
<code>Insert your formula here.</code>
Convert less than and larger than signs
Use html character entities instead of less than and larger than signs.
< becomes < and > becomes >
How to add VBA code to your comment
[vb 1="vbnet" language=","]
Put your VBA code here.
[/vb]
How to add a picture to your comment:
Upload picture to postimage.org or imgur
Paste image link to your comment.
Contact Oscar
You can contact me through this contact form