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:

1. Start with two positive integers, say a and b, where a > b.
2. Divide a by b and get the quotient q and remainder r, such that a = b * q + r.
3. If r = 0, then greatest common divisor(a, b) = b, since b is a divisor of a.
4. 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.
5. 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:

1. 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
2. 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:

1. 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
2. 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.
3. Replace a with b and b with r, and repeat above steps until the remainder becomes 0.
4. a = 15, b = 5
   a/b = 15/5 = 3 + 0, q = 3, r = 0
5. 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.
• #NAME? error if you misspell the function name.
• propagates errors, meaning that if the input contains an error (e.g., #VALUE!, #REF!), the function will return the same error.

5.1 Troubleshooting the error value

When you encounter an error value in a cell a warning symbol appears, displayed in the image above. Press with mouse on it to see a pop-up menu that lets you get more information about the error.

1. The first line describes the error if you press with left mouse button on it.
2. The second line opens a pane that explains the error in greater detail.
3. The third line takes you to the "Evaluate Formula" tool, a dialog box appears allowing you to examine the formula in greater detail.
4. This line lets you ignore the error value meaning the warning icon disappears, however, the error is still in the cell.
5. The fifth line lets you edit the formula in the Formula bar.
6. The sixth line opens the Excel settings so you can adjust the Error Checking Options.

Here are a few of the most common Excel errors you may encounter.

#NULL error - This error occurs most often if you by mistake use a space character in a formula where it shouldn't be. Excel interprets a space character as an intersection operator. If the ranges don't intersect an #NULL error is returned. The #NULL! error occurs when a formula attempts to calculate the intersection of two ranges that do not actually intersect. This can happen when the wrong range operator is used in the formula, or when the intersection operator (represented by a space character) is used between two ranges that do not overlap. To fix this error double check that the ranges referenced in the formula that use the intersection operator actually have cells in common.

#SPILL error - The #SPILL! error occurs only in version Excel 365 and is caused by a dynamic array being to large, meaning there are cells below and/or to the right that are not empty. This prevents the dynamic array formula expanding into new empty cells.

#DIV/0 error - This error happens if you try to divide a number by 0 (zero) or a value that equates to zero which is not possible mathematically.

#VALUE error - The #VALUE error occurs when a formula has a value that is of the wrong data type. Such as text where a number is expected or when dates are evaluated as text.

#REF error - The #REF error happens when a cell reference is invalid. This can happen if a cell is deleted that is referenced by a formula.

#NAME error - The #NAME error happens if you misspelled a function or a named range.

#NUM error - The #NUM error shows up when you try to use invalid numeric values in formulas, like square root of a negative number.

#N/A error - The #N/A error happens when a value is not available for a formula or found in a given cell range, for example in the VLOOKUP or MATCH functions.

#GETTING_DATA error - The #GETTING_DATA error shows while external sources are loading, this can indicate a delay in fetching the data or that the external source is unavailable right now.

5.2 The formula returns an unexpected value

To understand why a formula returns an unexpected value we need to examine the calculations steps in detail. Luckily, Excel has a tool that is really handy in these situations. Here is how to troubleshoot a formula:

1. Select the cell containing the formula you want to examine in detail.
2. Go to tab “Formulas” on the ribbon.
3. Press with left mouse button on "Evaluate Formula" button. A dialog box appears.
   The formula appears in a white field inside the dialog box. Underlined expressions are calculations being processed in the next step. The italicized expression is the most recent result. The buttons at the bottom of the dialog box allows you to evaluate the formula in smaller calculations which you control.
4. Press with left mouse button on the "Evaluate" button located at the bottom of the dialog box to process the underlined expression.
5. Repeat pressing the "Evaluate" button until you have seen all calculations step by step. This allows you to examine the formula in greater detail and hopefully find the culprit.
6. Press "Close" button to dismiss the dialog box.

There is also another way to debug formulas using the function key F9. F9 is especially useful if you have a feeling that a specific part of the formula is the issue, this makes it faster than the "Evaluate Formula" tool since you don't need to go through all calculations to find the issue..

1. Enter Edit mode: Double-press with left mouse button on the cell or press F2 to enter Edit mode for the formula.
2. Select part of the formula: Highlight the specific part of the formula you want to evaluate. You can select and evaluate any part of the formula that could work as a standalone formula.
3. Press F9: This will calculate and display the result of just that selected portion.
4. Evaluate step-by-step: You can select and evaluate different parts of the formula to see intermediate results.
5. Check for errors: This allows you to pinpoint which part of a complex formula may be causing an error.

The image above shows cell reference B3 converted to hard-coded value using the F9 key. The GCD function requires numerical values which is not the case in this example. We have found what is wrong with the formula.

Tips!

• View actual values: Selecting a cell reference and pressing F9 will show the actual values in those cells.
• Exit safely: Press Esc to exit Edit mode without changing the formula. Don't press Enter, as that would replace the formula part with the calculated value.
• Full recalculation: Pressing F9 outside of Edit mode will recalculate all formulas in the workbook.

Remember to be careful not to accidentally overwrite parts of your formula when using F9. Always exit with Esc rather than Enter to preserve the original formula. However, if you make a mistake overwriting the formula it is not the end of the world. You can “undo” the action by pressing keyboard shortcut keys CTRL + z or pressing the “Undo” button

5.3 Other errors

Floating-point arithmetic may give inaccurate results in Excel - Article

Floating-point errors are usually very small, often beyond the 15th decimal place, and in most cases don't affect calculations significantly.

Functions in 'Math and trigonometry' category

The GCD function function is one of 62 functions in the 'Math and trigonometry' category.

Excel function categories

Excel categories

Leave a Comment