This page will calculate the greatest common divisor (or factor) of two numbers that you enter. Two numbers are considered coprime if their greatest common divisor is 1. Numbers must be positive. Decimal values are not supported.

Number 1
Number 2


 
The quickest way to find the greatest common divisor of two integers, a and b (written as gcd(a,b)), is the Euclidean Algorithm.

This algorithm works on the following two principles:

1)     a = qb + r (where q is the quotient and r is the remainder)
2)     gcd(a,b) = gcd(b,r)

These enable us to reduce any given numbers rapidly as shown in the example below:

Find gcd(630, 132).

630 = 4 × 132 + 102
132 = 1 × 102 + 30
102 = 3 × 30 + 12
30 = 2 × 12 + 6
12 = 2 × 6 + 0

 Therefore gcd(630,132) = gcd(132,102) = gcd(102,30) = gcd(30,12) = gcd(12,6) = gcd(6,0) = 6.

The algorithm ends when the remainder (rn) equals zero.