Examkin

Question

Difficulty: MediumPrime Factorization, GCD, and LCM

Three positive integers xx, yy, and zz satisfy gcd⁡(x,y)=12\gcd(x, y) = 12, gcd⁡(y,z)=18\gcd(y, z) = 18, and gcd⁡(x,z)=30\gcd(x, z) = 30, where gcd⁡(a,b)\gcd(a, b) denotes the greatest common divisor of aa and bb. What is the minimum possible value of the least common multiple lcm(x,y,z)\text{lcm}(x, y, z)?

  1. A
    90
  2. 180Answer
  3. C
    360
  4. D
    540
  5. E
    1080

Answer

180
The correct answer is 180. Expressing the pairwise GCDs in prime factorized form shows that gcd⁡(x,y)=22⋅31\gcd(x, y) = 2^2 \cdot 3^1, gcd⁡(y,z)=21⋅32\gcd(y, z) = 2^1 \cdot 3^2, and gcd⁡(x,z)=21⋅31⋅51\gcd(x, z) = 2^1 \cdot 3^1 \cdot 5^1. To satisfy these simultaneously while minimizing the overall LCM, the maximum power of 2 across the numbers must be 222^2, the maximum power of 3 must be 323^2, and the maximum power of 5 must be 515^1. Thus, lcm(x,y,z)=22⋅32⋅51=180\text{lcm}(x, y, z) = 2^2 \cdot 3^2 \cdot 5^1 = 180.

Step-by-Step Solution

1
Express the given GCD values in their prime factorized forms.
gcd⁡(x,y)=12=22⋅31⋅50\gcd(x, y) = 12 = 2^2 \cdot 3^1 \cdot 5^0, gcd⁡(y,z)=18=21⋅32⋅50\gcd(y, z) = 18 = 2^1 \cdot 3^2 \cdot 5^0, and gcd⁡(x,z)=30=21⋅31⋅51\gcd(x, z) = 30 = 2^1 \cdot 3^1 \cdot 5^1.
Analyzing prime factor exponents determines the minimum required power of each prime in xx, yy, and zz.
2
Determine the minimum necessary exponents for prime 2 in xx, yy, and zz.
Since gcd⁡(x,y)\gcd(x, y) has 222^2, both xx and yy must contain at least 222^2. Thus, the maximum exponent of 2 across the integers is at least 2.
The least common multiple takes the maximum exponent for each prime factor among all three numbers.
3
Determine the minimum necessary exponents for prime 3 in xx, yy, and zz.
Since gcd⁡(y,z)\gcd(y, z) has 323^2, both yy and zz must contain at least 323^2. Thus, the maximum exponent of 3 across the integers is at least 2.
To satisfy gcd⁡(y,z)=18\gcd(y, z) = 18, the prime factor 3 must appear with an exponent of at least 2 in both yy and zz.
4
Determine the minimum necessary exponents for prime 5 in xx, yy, and zz.
Since gcd⁡(x,z)\gcd(x, z) has 515^1, both xx and zz must contain at least 515^1. Thus, the maximum exponent of 5 across the integers is at least 1.
To satisfy gcd⁡(x,z)=30\gcd(x, z) = 30, the prime factor 5 must appear with an exponent of at least 1 in both xx and zz.
5
Calculate the minimum least common multiple lcm(x,y,z)\text{lcm}(x, y, z).
lcm(x,y,z)=22⋅32⋅51=4⋅9⋅5=180\text{lcm}(x, y, z) = 2^2 \cdot 3^2 \cdot 5^1 = 4 \cdot 9 \cdot 5 = 180. (A valid assignment is x=60x = 60, y=36y = 36, z=90z = 90).
Multiplying the minimum maximum prime factor powers yields the smallest possible value for the LCM.

Key Concept

Prime Factor Exponents in Pairwise GCD and LCM Relations
Estimated Time:2m 0s
Rate this question

Topics

Prime Factorization, GCD, and LCM

More questions from this topic