## GCD Formula:

Euclidean Algorithm

While n mod m is not equal to 0

n = m

m = n mod mThen GCD = m

## GCD Definition

Use our free Greatest Common Divisor (GCD) calculator and get your answers in an instant! When looking for the (GCD), it is important to consider the numbers in question. If one will divide evenly by the other, that is likely the number you are seeking. However, that might not be true. This calculator will tell you what the answer is so you can check it against the results you come up with. If you do it by hand, you might end up using a trial-by-error method when comparing the two values’ prime numbers.

To explain GCD it is necessary to clarify the role of prime numbers. All integers can be constructed from products of primes. For example, 8 = 2*2*2, 300 = 5*5*3*2*2.

Some tips clarify the “prime number” designation:

- The prime number “1″ is redundant as a multiplier, but will be listed here for clarity. It serves to give a non-trivial definition of primes in the following sentence and to explain cases where GCD = 1.
- Prime numbers are products of themselves and 1. For example, 3 = 3*1, 19 = 19*1, x = x*1. You may have guessed that the GCD of all prime numbers is 1.

The GCD is used in a variety of applications. Probably one of the easiest to identify is creating an equal division of one value with the other. For instance, 8 buns and 10 hot dogs gives you a GCD of 2. Using this number, you can calculate how many packages of buns and hot dogs you need to have an equal number of each.

## GCD Calculator Steps

Type in the two numbers in question. Order does not matter. Negative signs are allowed, though they are superfluous in determining the numeric value of a GCD.

Examples:

- Input numbers: 6 and 5
- Find the product of primes that makes 6: 6 = 3*2*1
- Find the product of primes that make 5: 5 = 5*1
- The largest common prime is “1,” therefore GCD = 1

- Input numbers: 665, 3383335
- Product of primes for 665 = 19*7*5*1
- Product of primes for 3383335 = 7603*89*5*1
- The largest common prime here is 5, so GCD = 5.

Note that there is no “weight” given to large primes such as 7603 in this example. It may happen that two very large numbers have GCD of 1.

## Calculation Limitations

Entering non-integers may result in errors. For example, given input numbers 9.8 and 3, the calculator displays “GCD of 10 and 3 is 3.”

Taken on its face, the above statement is false. Note that 10 = 5*2*1, 3 = 3*1, GCD = 1. The calculator took the “9″ of 9.8 and properly calculated 9 = 3*3*1, and 3 = 3*1, giving GCD = 3. However, the display rounds a non-integer; in this case, 9.8 is rounded to 10. Since display text and calculation do not match, a false statement such as “10 and 3 have GCD 3″ may result with non-integer inputs.

Use the GCD to multiply both numbers until you end up with the same value if you are looking for an equal number.

## Putting the Greatest Common Divisor to Use

The GCD is probably used most for comparing the common values shared between two numbers. For instance, 30 and 7 have the number 1 in common. While not all GCD’s will be expressed as prime numbers, they are products of prime numbers.

The prime numbers of 30 are 1, 2, 3, and 5; those of 6 are 1, 2, and 3. The common numbers between them (1, 2, and 3) multiple to 6, which makes 6 the GCD.

Using the above method to calculate the GCD is known as prime factoring. Unless you are using a calculator, this is probably the easiest way to find the GCD if the values do not immediately suggest a common value between them. That can take time with larger values, so this calculator will help you save time.

## How to Calculate GCD

Sometimes the best gcd calculator is the one that is easy to use and doesn’t require us to even know what the gcd formula is in the first place! But if you want to know the exact formula for calculating gcd then please check out the “Formula” box above.