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