Examkin

Question

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

For a positive integer NN, the greatest common divisor of NN and 360360 is 120120, and the least common multiple of NN and 450450 is 90009000. What is the value of NN?

Answer: 3000

Answer

The value of NN is 30003000.
Prime factorizing 360360, 120120, 450450, and 90009000 converts the GCD and LCM requirements into a system of min/max equations for the exponents of 22, 33, and 55. The condition gcd⁡(N,360)=120\gcd(N, 360) = 120 dictates that the exponent of 33 in NN must be exactly 11, while the exponent of 22 is at least 33. The condition lcm(N,450)=9000\text{lcm}(N, 450) = 9000 dictates that the exponent of 22 must be exactly 33 and the exponent of 55 must be exactly 33. Combining these constraints gives N=23×31×53=3000N = 2^3 \times 3^1 \times 5^3 = 3000.

Step-by-Step Solution

1
Find the prime factorizations of all known numbers
360=23×32×51360 = 2^3 \times 3^2 \times 5^1, 120=23×31×51120 = 2^3 \times 3^1 \times 5^1, 450=21×32×52450 = 2^1 \times 3^2 \times 5^2, and 9000=23×32×539000 = 2^3 \times 3^2 \times 5^3.
Prime factorization allows us to analyze GCD and LCM conditions using exponent minimums and maximums.
2
Apply the GCD exponent rule min⁡(expN(p),expA(p))=expGCD(p)\min(\text{exp}_N(p), \text{exp}_A(p)) = \text{exp}_{GCD}(p)
For factor 22: min⁡(a,3)=3  ⟹  a≥3\min(a, 3) = 3 \implies a \ge 3; For factor 33: min⁡(b,2)=1  ⟹  b=1\min(b, 2) = 1 \implies b = 1; For factor 55: min⁡(c,1)=1  ⟹  c≥1\min(c, 1) = 1 \implies c \ge 1.
The GCD of two numbers takes the minimum exponent for each prime factor.
3
Apply the LCM exponent rule max⁡(expN(p),expB(p))=expLCM(p)\max(\text{exp}_N(p), \text{exp}_B(p)) = \text{exp}_{LCM}(p)
For factor 22: max⁡(a,1)=3  ⟹  a=3\max(a, 1) = 3 \implies a = 3; For factor 55: max⁡(c,2)=3  ⟹  c=3\max(c, 2) = 3 \implies c = 3. No prime factors greater than 55 exist in NN.
The LCM of two numbers takes the maximum exponent for each prime factor.
4
Synthesize the exponents and compute NN
N=23×31×53=8×3×125=3000N = 2^3 \times 3^1 \times 5^3 = 8 \times 3 \times 125 = 3000.
Multiplying out the uniquely determined prime factors gives the value of NN.

Key Concept

Simultaneous prime exponent analysis using GCD (minimum exponents) and LCM (maximum exponents) rules.
Rate this question

Topics

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

More questions from this topic