Greatest Common Divisor Calculator


Instructions: Compute the Greatest Common Divisor (GCD) for two non-negative integer values \(n_1\) and \(n_2\). The values of \(n_1\) and \(n_2\) need to be integer and greater than or equal to 1

The integer \(n_1\) =
The integer \(n_2\) =

How to Compute the Greatest Common Divisor?

More about the Greatest Common Divisor (sometimes also referred as Greatest Common Factor): The greatest common divisor (GCD) between two positive integer numbers \(n_1\) and \(n_2\) is the largest integer that divides both \(n_1\) and \(n_2\). It is usually easy to find by inspection (this is, trying lots of numbers in a systematic way, until we find it), but that is true only for small numbers. Computing the GCD for large numbers by inspection can be tedious or plain hard.

Fortunately, there is a systematic, easy (cough, cough) way to compute the GCD for two numbers. The method goes like this

  • Compute the prime decomposition of \(n_1\) and \(n_2\). Symbolically, we would have something like this: \[n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}\] \[n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}\]
  • Find the list of common primes in the corresponding prime decomposition. If there are no common primes, then STOP, you have found that GCD = 1. Otherwise, let \(\{r_1, …, r_k \}\) be the list of \(k\) common primes and let \(\alpha_{i_l}, \beta_{i_l}\) for \(l=1,2,..,k\) the corresponding exponents found in the prime decomposition of \(n_1\) and \(n_2\) for the corresponding common primes.

  • The GCD is computed as: \[GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}} \]

The above method looks too complex?? Not really. Let’s see an example: Let us compute the GCD for \(n_1 = 165\) and \(n_2 = 1575\). Let us find the prime decomposition of each of these numbers (you can use our prime decomposition calculator)

\[165 = 3 \cdot 5 \cdot 11\] \[1575 = 3^2 \cdot 5^2 \cdot 7\]

From the above: what primes do these two numbers have in common? As we can see, the common primes are 3 and 5. Looking at the exponents of these common primes in each of the numbers, we look the minimum between the two. In this case, the minimum exponent for 3 is 1, and the minimum exponent for 5 is also 1. Therefore

\[GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15 \]



In case you have any suggestion, please do not hesitate to contact us.

log in

reset password

Back to
log in
Copy Protected by Chetan's WP-Copyprotect.