54 = 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.
What is the greatest common divisor of 54 and 144?
1 answer
1 answer