+0  
 
0
44
1
avatar

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
avatar+9457 
+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

7 Online Users