+0

# Number Theory

0
165
1

N is a four-digit positive integer.  Dividing N by 9, the remainder is 5.  Dividing N by 7, the remainder is 3.  Dividing N by 5, the remainder is 3.  What is the smallest possible value of N?

May 17, 2022

#1
+1

You can use Chinese Remainder Theorem.

The problem translates to: $$\begin{cases}1000 \leq N \leq 9999\\N \equiv 5 \pmod 9\\N \equiv 3 \pmod 7\\ N \equiv 3 \pmod 5\end{cases}$$

Now, we let $$N = 9k + 5$$ for some integer k. Since $$N \equiv 3 \pmod 7$$,

$$\begin{array}{rclc}9k+5&\equiv&3&\pmod7\\ 2k&\equiv&-2&\pmod{7}\\ k&\equiv&6&\pmod7\end{array}$$

Then we let $$k = 7n + 6$$ for some integer n. Then $$N = 9(7n + 6) + 5 = 63n + 59$$.

Repeat this process one more time with N = 3 (mod 5), and you will get $$N = 315m + 248$$ for some integer m.

We can try m = 0, 1, 2, 3, ... to see which one gives the smallest possible 4-digit number. You will get $$N = 315(3) + 248 = 1193$$. You are more than welcome to check that this solution satisfies the conditions described in the problem.

May 18, 2022