Browse · harp
Printimc
number theory intermediate
Problem
Let be the least positive integer greater than for which What is the sum of the digits of ?
(A)
(B)
(C)
(D)
Solution
We know that and by the Euclidean Algorithm. Hence, let and , where and . Subtracting the two equations, . Letting , we get . Taking modulo , we have . We are given that , so . Notice that if then the condition is violated. The next possible value of satisfies the given condition, giving us . Alternatively, we could have said for only, so , giving us our answer. Since the problem asks for the sum of the digits of , our answer is .
Final answer
C