# GCD Calculator

## How To Use GCD Calculator

Lets first understand, what is GCD and how we can calculate the GCD?

The greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

For two integers x, y, the greatest common divisor (GCD) of x and y is denoted gcd(x,y).

We will denote the greatest common divisor (GCD) of two integers a and b as gcd(a,b). Sometimes, we use (a,b).

Example

What is the greatest common divisor (GCD) of 48, 12 and 4?

$$4=2*2*1$$

$$12=3*2*2*1$$

$$48=3*2*2*2*2*1$$

Common divisors of 48, 12 and 4: 1, 2, 4

The greatest of these is 4. That is, the greatest common divisor (GCD) of 48, 12 and 4 is 4. So, we can write $$gcd(48,12,4)=4$$.

Coprime numbers

Two numbers are called relatively prime, or coprime, if their greatest common divisor (GCD) equals 1. For example, 7, 12 and 5 are relatively prime.

Least common multiple

The greatest common divisor (GCD) can be used to find the least common multiple (LCM) of two numbers when the greatest common divisor is known, using the relation

$$lcm(a,b,c)=\dfrac{|a.b.c|.gcd(a,b,c)}{gcd(a,b).gcd(a,c).gcd(b,c)}$$

If we know LCM, then we can find the GCD, using the relation

$$gcd(a,b,c)=\dfrac{|a.b.c|.lcm(a,b,c)}{lcm(a,b).lcm(a,c).lcm(b,c)}$$

Euclid's algorithm

A much more efficient method to find the GCD is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference.

$$gcd(a,0)=0$$

$$gcd(a,a)=a$$

$$gcd(a,b)=gcd(b,a\hspace{0.1cm}mod\hspace{0.1cm}b)$$

$$gcd(a,b)=gcd(a-b,b)\hspace{0.1cm},if\hspace{0.1cm}a>b$$

$$gcd(a,b)=gcd(a,b-a)\hspace{0.1cm},if\hspace{0.1cm}b>a$$

Properties of GCD

1. Every common divisor of a and b is a divisor of gcd(a, b).

2. gcd(a, 0) = |a|, for $$a\ne 0$$, since any number is a divisor of 0, and the greatest divisor of a is |a|.

3. If m is a non-negative integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).

4. If m is any integer, then gcd(a+m⋅b, b) = gcd(a, b).

5. The gcd is a commutative function: gcd(a, b) = gcd(b, a).

6. The gcd is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).

For calculating GCD using above GCD calculator, you have to just write the values in the given input box and press the calculate button, you will get the GCD.