What is the smallest positive integer whose remainder is 3 when divided by 7, whose remainder is 4 when divided by 9, and whose remainder is 2 when divided by 16?
Examining positive integers that satisfy the given conditions
Positive integers whose remainder is 3 when divided by 7 are:
3, 10, 17, 24, 31, ...
Positive integers whose remainder is 4 when divided by 9 are:
4, 13, 22, 31, ...
Therefore, positive integers whose remainder is 3 when divided by 7 and whose remainder is 4 when divided by 9 are smallest at 31.
Beyond this are the numbers added to 31 the multiples of 7 as well as the multiples of 9, or the multiples of 63.
Let N be such numbers, and 'p' be a nonnegative integer, N is written as:
N=63p+31 .....[1].
Since N leaves 2 as a remainder when divided by 16, N is an even number. Then, 'p' is an odd number according to [1].
The remainders of N divided by 16, for p=1, 3, 5, ... are as follows:
If p=1, N=94=16*5+14.
If p=3, N=220=16*13+12.
If p=5, N=346=16*21+10.
... And,
if p=13, N=850=16*53+2.
Hence, the solution is 850.
Setting up equations from the given conditions
Let N be a solution, and 'a', 'b', and 'c' be integers, N is written as:
N=7a+3 .....[1]
N=9b+4 .....[2]
N=16c+2 .....[3].
From [1] and [2],
7a+3=9b+4.
7(a-b+1)=2(b+4).
Since 7 and 2 are primes to each other, and both a-b+1 and b+4 are integers,
b+4=7d .....[4]. (Note: 'd' is an integer.)
From [2] and [4],
N=9(7d-4)+4=63d-32 .....[5].
From [3] and [5],
16c+2=63d-32.
d+2=16(4d-c-2).
Since both d+2 and 4d-c-2 are integers,
d+2=16e .....[6]. (Note: 'e' is an integer.)
From [5] and [6],
N=63(16e-2)-32=1008e-158.
A positive integer N minimizes when e=1:
N=1008-158=850.