Strange math question?

Question

Let N denote the smallest positive integer that satisfies the two conditions:
(i) If N is divided by 11 then the remainder is 9
(ii) If N is divided by 7 then the remainder is 5

What are the sum of the digits of N?

And how the heck do you do it?

Answer 1

One uses the Chinese remainder theorem,
which says we can find an answer of the form c + 77n.
So the first condition gives
N = 9 + 11m
Then 9 + 11m = 5 + 7n
4 + 4m = 7(n-m)
In other words, 7 must divide 4 + 4m
So 7 divides 1+ m
and the smallest m that works is m = 6.
Thus the general solution is N = 9 + 11(6+7n) = 75 + 77n
So N = 9 + 11(6) = 75 is the smallest value of N
and the sum of its digits is 12.

Answer 2

To understand this solution, you will need to know modular arithmetic. This problem is one that can also be solved by Chinese Remainder Theorem. So to rewrite (i) and (ii),

(i) N = 9 mod 11
(ii) N = 5 mod 7

Or, instead of (i), you might say N = 11j + 9 for some natural number j. Substitute that in for (ii) and you get:

11j+9 = 5 mod 7 =>
11j = 3 mod 7 =>
j = 6 mod 7 since 2 = 11^(-1) mod 7

I.e. j = 7k+6 for some positive integer k. So, substitute that in N = 11j+9 and you get N = 11(7k+6)+9 = 77k + 75. Alright, so the smallest such number is when k=0, so N = 75. You can now check that this is the right number. 7+5 = 12.