Examkin

Question

Difficulty: HardGreatest Common Divisor (GCD) and Least Common Multiple (LCM)

For two positive integers xx and yy with x<yx < y, the greatest common divisor is GCD(x,y)=15\text{GCD}(x, y) = 15 and the least common multiple is LCM(x,y)=9000\text{LCM}(x, y) = 9000. If xx is a multiple of 88 but not a multiple of 99, what is the value of y−xy - x?

Answer: 1005

Answer

1005
By writing x=15ax = 15a and y=15by = 15b with GCD(a,b)=1\text{GCD}(a, b) = 1, we derive a⋅b=900015=600a \cdot b = \frac{9000}{15} = 600. Prime factorizing 600=8×3×25600 = 8 \times 3 \times 25 yields four coprime pairs (a,b)(a, b) with a<ba < b: (1,600)(1, 600), (3,200)(3, 200), (8,75)(8, 75), and (24,25)(24, 25). These yield candidate values for xx of 1515, 4545, 120120, and 360360, respectively. Checking the divisibility conditions, 1515 and 4545 are not multiples of 88, while 360360 is a multiple of 99. The only value of xx that is a multiple of 88 and not a multiple of 99 is 120120 (corresponding to a=8,b=75a = 8, b = 75). Hence y=15×75=1125y = 15 \times 75 = 1125, and y−x=1125−120=1005y - x = 1125 - 120 = 1005.

Step-by-Step Solution

1
Set up the algebraic representation using the GCD
x=15ax = 15a and y=15by = 15b, where GCD(a,b)=1\text{GCD}(a, b) = 1 and a<ba < b
Any two integers can be written as the product of their GCD and coprime factor multipliers.
2
Relate LCM and GCD to find the product of multipliers a×ba \times b
a×b=LCM(x,y)GCD(x,y)=900015=600a \times b = \frac{\text{LCM}(x, y)}{\text{GCD}(x, y)} = \frac{9000}{15} = 600
The product of GCD and LCM equals the product of the numbers: GCD(x,y)×LCM(x,y)=x×y=15a×15b=225ab\text{GCD}(x,y) \times \text{LCM}(x,y) = x \times y = 15a \times 15b = 225ab.
3
Decompose 600 into coprime component blocks
600=23×31×52=8×3×25600 = 2^3 \times 3^1 \times 5^2 = 8 \times 3 \times 25
Since GCD(a,b)=1\text{GCD}(a, b) = 1, prime powers cannot be split between aa and bb.
4
Form all valid candidate pairs (a,b)(a, b) with a<ba < b
(1,600)(1, 600), (3,200)(3, 200), (8,75)(8, 75), and (24,25)(24, 25)
There are 23−1=42^{3-1} = 4 ways to partition the 3 prime factor blocks into two coprime factors where a<ba < b.
5
Apply divisibility constraints to isolate xx and yy
x=120x = 120 and y=1125y = 1125
Only x=15×8=120x = 15 \times 8 = 120 satisfies being a multiple of 8 without being a multiple of 9.
6
Calculate the target difference y−xy - x
1125−120=10051125 - 120 = 1005
Subtracting xx from yy yields the required value.

Key Concept

Partitioning prime factor powers of LCM/GCD to identify coprime factor multipliers
Rate this question

Topics

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

More questions from this topic