Greatest common divisor

Greatest Common Divisor (GCD)

The greatest common divisor of two numbers, also expressed as GCD, a and b, can be found in several ways. The first way invlolves factoring both numbers, and the second way uses Euler's Thoerem.

Once the prime factorization of two numbers has been found, the greatest common divisor is the product of all common factors of the numbers.

Example: $270=2\times3^3\times5$ $144=2^4\times3^2$

The common factors are 2 and $3^2$ , so the GCD is $2\times3^2=18$

Another Example: $1200=2^4\times3\times5$ $720=2^4\times3^2\times5$ $288=2^5\times3^2$

The common factors are $2^4$ and 3, making the GCD ${2^4\times3=48}$ .

Euler's Theorem is much faster and can be used to give the GCD of any two numbers. Euler's Theorem is primarily faster because you do not need to find the prime factorizations, which can be very time consuming. Where finding the prime factorization of large numbers fails due to how large the numbers become, Euler's Theorem can be used.

For two numbers, a and b, the GCD can be at most |a-b|. Also, the GCD can also be no more than the difference in the largest multiple of the smaller number that is less than the larger number. By subtracting the largest multiple of the smaller number from the larger number over and over until the numbers are equal, you will end up with the largest number they both divide, the GCD.

Example: (1440, 560) (1440, 1120) (320, 1120) (960, 1120) (160, 960) (160, 160), so the GCD is 160.

Another Example: (1200, 720, 288) (1200, 720, 576) (624, 144, 576) (624, 576, 576) (624, 576) (48, 576) (48, 48), so the GCD is 48.

Page

Toolbox

Search

Greatest common divisor

Greatest Common Divisor (GCD)