Examkin

Question

Difficulty: Very hardGreatest Common Divisor (GCD) and Least Common Multiple (LCM)

For three positive integers xx, yy, and zz, all of whose prime factors belong exclusively to the set {2,3,5}\{2, 3, 5\}, their pairwise greatest common divisors are given by gcd⁡(x,y)=60\gcd(x, y) = 60, gcd⁡(y,z)=90\gcd(y, z) = 90, and gcd⁡(x,z)=150\gcd(x, z) = 150. What is the minimum possible value of the sum x+y+zx + y + z?

  1. A
    300300
  2. B
    465465
  3. 930930Answer
  4. D
    1,3501,350
  5. E
    2,7002,700

Answer

The minimum possible value of the sum x+y+zx + y + z is 930930.
Analyzing the prime factorization exponents for each prime factor p∈{2,3,5}p \in \{2, 3, 5\} establishes minimum lower bounds on exponents. For prime 22, min⁡(x2,y2)=2\min(x_2, y_2) = 2 forces x2≥2x_2 \ge 2 and y2≥2y_2 \ge 2, which in turn forces z2=1z_2 = 1 to satisfy min⁡(y2,z2)=1\min(y_2, z_2) = 1. Similarly, for prime 33, y3≥2y_3 \ge 2 and z3≥2z_3 \ge 2 forces x3=1x_3 = 1. For prime 55, x5≥2x_5 \ge 2 and z5≥2z_5 \ge 2 forces y5=1y_5 = 1. Evaluating x=22⋅31⋅52=300x = 2^2 \cdot 3^1 \cdot 5^2 = 300, y=22⋅32⋅51=180y = 2^2 \cdot 3^2 \cdot 5^1 = 180, and z=21⋅32⋅52=450z = 2^1 \cdot 3^2 \cdot 5^2 = 450 gives x+y+z=930x + y + z = 930.

Step-by-Step Solution

1
Express the given pairwise GCDs in their prime factorized forms.
gcd⁡(x,y)=60=22×31×51\gcd(x,y) = 60 = 2^2 \times 3^1 \times 5^1
gcd⁡(y,z)=90=21×32×51\gcd(y,z) = 90 = 2^1 \times 3^2 \times 5^1
gcd⁡(x,z)=150=21×31×52\gcd(x,z) = 150 = 2^1 \times 3^1 \times 5^2
The exponent of any prime pp in gcd⁡(a,b)\gcd(a,b) is min⁡(ap,bp)\min(a_p, b_p).
2
Determine the minimum required prime exponents for prime 22.
min⁡(x2,y2)=2\min(x_2, y_2) = 2, min⁡(y2,z2)=1\min(y_2, z_2) = 1, min⁡(x2,z2)=1  ⟹  x2=2,y2=2,z2=1\min(x_2, z_2) = 1 \implies x_2 = 2, y_2 = 2, z_2 = 1
Since min⁡(x2,y2)=2\min(x_2, y_2) = 2, both x2≥2x_2 \ge 2 and y2≥2y_2 \ge 2. To satisfy min⁡(y2,z2)=1\min(y_2, z_2) = 1, we must have z2=1z_2 = 1. The minimal exponents are x2=2,y2=2,z2=1x_2=2, y_2=2, z_2=1.
3
Determine the minimum required prime exponents for prime 33.
min⁡(x3,y3)=1\min(x_3, y_3) = 1, min⁡(y3,z3)=2\min(y_3, z_3) = 2, min⁡(x3,z3)=1  ⟹  x3=1,y3=2,z3=2\min(x_3, z_3) = 1 \implies x_3 = 1, y_3 = 2, z_3 = 2
Since min⁡(y3,z3)=2\min(y_3, z_3) = 2, both y3≥2y_3 \ge 2 and z3≥2z_3 \ge 2. To satisfy min⁡(x3,y3)=1\min(x_3, y_3) = 1, we must have x3=1x_3 = 1. The minimal exponents are x3=1,y3=2,z3=2x_3=1, y_3=2, z_3=2.
4
Determine the minimum required prime exponents for prime 55.
min⁡(x5,y5)=1\min(x_5, y_5) = 1, min⁡(y5,z5)=1\min(y_5, z_5) = 1, min⁡(x5,z5)=2  ⟹  x5=2,y5=1,z5=2\min(x_5, z_5) = 2 \implies x_5 = 2, y_5 = 1, z_5 = 2
Since min⁡(x5,z5)=2\min(x_5, z_5) = 2, both x5≥2x_5 \ge 2 and z5≥2z_5 \ge 2. To satisfy min⁡(x5,y5)=1\min(x_5, y_5) = 1, we must have y5=1y_5 = 1. The minimal exponents are x5=2,y5=1,z5=2x_5=2, y_5=1, z_5=2.
5
Calculate the values of xx, yy, and zz and find their sum.
x=22×31×52=300x = 2^2 \times 3^1 \times 5^2 = 300
y=22×32×51=180y = 2^2 \times 3^2 \times 5^1 = 180
z=21×32×52=450z = 2^1 \times 3^2 \times 5^2 = 450
x+y+z=300+180+450=930x + y + z = 300 + 180 + 450 = 930
Summing the minimal values yields the required minimum total.

Key Concept

Finding integers from pairwise GCD conditions using prime factor exponent minimums: vp(gcd⁡(a,b))=min⁡(vp(a),vp(b))\text{v}_p(\gcd(a,b)) = \min(\text{v}_p(a), \text{v}_p(b)).
Estimated Time:2m 30s
Rate this question

Topics

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

More questions from this topic