What is the greatest common divisor of 54 and 144?
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.
To find the greatest common divisor (GCD) of two numbers, you can use either prime factorization or the Euclidean algorithm. Let's use the Euclidean algorithm, which is a faster method.
Step 1: Divide the larger number (144) by the smaller number (54).
144 ÷ 54 = 2 remainder 36
Step 2: Divide the previous divisor (54) by the remainder (36).
54 ÷ 36 = 1 remainder 18
Step 3: Divide the previous divisor (36) by the new remainder (18).
36 ÷ 18 = 2 remainder 0
Since the remainder is 0, the previous divisor (18) is the GCD of 54 and 144.
Therefore, the greatest common divisor of 54 and 144 is 18.