Problem:
How many positive integers n are there such that n is a multiple of 5 , and the least common multiple of 5 ! and n equals 5 times the greatest common divisor of 10 ! and n ?
Answer Choices:
A. 12
B. 24
C. 36
D. 48
E. 72
Solution:
We set up the following equation as the problem states:
Icm(5!,n)=5gcd(10!,n)
Breaking each number into its prime factorization, we see that the equation becomes
Icm(23⋅3⋅5,n)=5gcd(28⋅34⋅52⋅7,n)
We can now determine the prime factorization of n. We know that its prime factors belong to the set {2,3,5,7}, as no factor of 10 ! has 11 in its prime factorization, nor anything greater. Next, we must find exactly how many different possibilities exist for each.
There can be anywhere between 3 and 8 2's and 1 to 43 's. However, since n is a multiple of 5 , and we multiply the gcd by 5 , there can only be 35 's in n 's prime factorization. Finally, there can either 0 or 17 's.
Thus, we can multiply the total possibilities of n 's factorization to determine the number of integers n which satisfy the equation, giving us 6×4×1×2= (D)48 .
OR
Like the Solution 1, we start from the equation:
lcm(5!,n)=5gcd(10!,n)
Assume Icm(5!,n)=k⋅5 !, with some integer k. It follows that k⋅4!=gcd(10!,n). It means that n has a divisor 4!. Since n is a multiple of 5,n has a divisor 5!. Thus, Icm(5!,n)=n=k⋅5 !. The equation can be changed as
k⋅5!=5gcd(10!,k⋅5!)
k=5gcd(6⋅7⋅8⋅9⋅10,k)
We can see that k is also a multiple of 5 , with a form of 5⋅m. Substituting it in the above equation, we have
m=5gcd(6⋅7⋅8⋅9⋅2,m)
Similarly, m is a multiple of 5 , with a form of 5⋅s. We have
s=gcd(6⋅7⋅8⋅9⋅2,5⋅s)=gcd(25⋅33⋅7,s)
The equation holds, if s is a divisor of 25⋅33⋅7, which has (5+1)(3+1)(1+1)=(D)48 divisors .
The problems on this page are the property of the MAA's American Mathematics Competitions