Friday

April 29, 2016
Posted by **Cathy** on Tuesday, February 19, 2008 at 5:18pm.

- Math -
**Count Iblis**, Tuesday, February 19, 2008 at 5:29pm54 = 9 x 6 = 2x3^3

144 = 12x12 = 2^4x3^2

gcd(54,144) = 2x3^2 = 18

Another way to do the problem is as follows. You use the fact that

gcd(x,y) = gcd(x, y - n x)

where n is an arbitrary integer.

gcd(54,144) = gcd(54, 144- 2x54) =

gcd(36,54) = gcd(36, 54-36) =

gcd(18,36) = gcd(18, 36 - 2x18) =

gcd(18,0) = 18

The advantage of the second method is that you don't need to factor the numbers into primes.