Problem:
Let n be the least positive integer greater than 1000 for which
gcd(63,n+120)=21 and gcd(n+63,120)=60
What is the sum of the digits of n?
Answer Choices:
A. 12
B. 15
C. 18
D. 21
E. 24
Solution:
We know that
gcd(n+57,63)=21
and
gcd(nβ57,120)=60
by the Euclidean Algorithm. Hence, let
n+57=21Ξ± and nβ57=60Ξ³, where gcd(Ξ±,3)=1 and gcd(Ξ³,2)=1
Subtracting the two equations, 38=7Ξ±β20Ξ³. Letting Ξ³=2s+1, we get 58=7Ξ±β40. Taking modulo 40, we have Ξ±β‘14(mod40). We are given that n=21Ξ±β57>1000, so Ξ±β₯51. Notice that if Ξ±=54 then the condition gcd(Ξ±,3)=1 is violated. The next possible value of Ξ±=94 satisfies the given condition, giving us n=1917.
Alternatively, we could have said Ξ±=40k+14β‘0(mod3) for kβ‘1(mod3) only, so kβ‘0,2(mod3), giving us our answer. Since the problem asks for the sum of the digits of n, our answer is 1+9+1+7=(C) 18β.
OR
The conditions of the problem reduce to the following: n+120=21k and n+63=60β, where gcd(k,3)=1 and gcd(β,2)=1. From these equations, we see that 21kβ60β=57. Solving this Diophantine equation gives us that k=20a+17 and β=7a+5. Since, n>1000, we can do some bounding and get that k>53 and β>17. Now we start bashing by plugging in numbers that satisfy these conditions: a=4 is the first number that works so we get β=33,k=97. Therefore, we have n=21(97)β120=60(33)β63=1917, and our answer is 1+9+1+7=(C) 18β.
The problems on this page are the property of the MAA's American Mathematics Competitions