Problem:
There are exactly 77,000 ordered quadruples (a,b,c,d) such that gcd(a,b,c,d)= 77 and lcm(a,b,c,d)=n. What is the smallest possible value of n ?
Answer Choices:
A. 13,860
B. 20,790
C. 21,560
D. 27,720
E. 41,580
Solution:
Note that gcd(a,b,c,d)=77 and lcm(a,b,c,d)=n if and only if gcd(7Ta,77b,77c,77d)=1 and lcm(77a,7Tb,77c,77d)=77n. Thus there are 77,000 ordered quadruples (a,b,c,d) such that gcd(a,b,c,d)=1 and lcm(a,b,c,d)=77n. Let m=77n and suppose that p is a prime that divides m. Let A=A(p), B=B(p),C=C(p),D=D(p), and M=M(p)≥1 be the exponents of p such that pA,pB,pC,pD, and pM are the largest powers of p that divide a, b,c,d, and m, respectively. The gcd and 1 cm requirements are equivalent to min(A,B,C,D)=0 and max(A,B,C,D)=M. For a fixed value of M, there are (M+1)4 quadruples (A,B,C,D) with each entry in {0,1,…,M}. There are M4 of them for which min(A,B,C,D)≥1, and also M4 of them such that max(A,B,C,D)≤M−1. Finally, there are (M−1)4 quadruples (A,B,C,D) such that min(A,B,C,D)≥1 and max(A,B,C,D)≤M−1. Thus the number of quadruples such that min(A,B,C,D)=0 and max(A,B,C,D)=M is equal to (M+1)4−2M4+(M−1)4=12M2+2=2(6M2+1). Multiplying these quantities over all primes that divide m yields the total number of quadruples (a,b,c,d) with the required properties. Thus
77,000=23⋅53⋅7⋅11=p∣m∏2(6(M(p))2+1)
Note that 6(M(p))2+1 is odd and this product must contain three factors of 2 , so there must be exactly three primes that divide m. Let p1,p2, and p3 be these primes. Note that 6⋅12+1=7,6⋅22+1=52, and 6⋅32+1=5⋅11. None of these could appear as a factor more than once because 77,000 is not divisible by 72,54, or 112. Moreover, the product of these three is equal to 53⋅7⋅11. All other factors of the form 6M2+1 are greater than these three, so without loss of generality the only solution is M(p1)=1,M(p2)=2, and M(p3)=3. It follows that m=p11p22p33, and the smallest value of m occurs when p1=5,p2=3, and p3=2. Therefore the smallest possible values of m and n are 5⋅32⋅23=360 and 77(5⋅32⋅23)=27,720, respectively.
The problems on this page are the property of the MAA's American Mathematics Competitions