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 4. What is the smallest possible value of N?
+26 By Chinese Remainder Theorem, there exists a unique residue \(\pmod{315}\) for \(N\). Hence, all we need to do is find a possible residue, and that will be the unique residue for \(N\) when taken \(\pmod{315}\). By \(N \equiv 3 \equiv -4 \pmod{7}\) and \(N \equiv 5 \equiv -4 \pmod{9}\), we get that \(N \equiv -4 \pmod{63}\). Hence, \(N = 63k + 59\) for some integer \(k\).
Combining this with the last condition, we get \(63k + 59 \equiv 3k + 4 \equiv 4 \pmod{5}\), so \(3k \equiv 0 \pmod{5}\). Multiplying both sides of this congruence by \(2\), we get that \(6k \equiv k \equiv 0 \pmod{5}\), so hence \(k \equiv 0 \pmod{5}\). Thus, \(N \equiv 63 \cdot 0 + 59 \equiv 59 \pmod{315}\).
Hence, we want to find the smallest four-digit \(N\) where \(N \equiv 59 \pmod{315}\), which gives us an answer of \(315 \cdot 3 + 59 = \boxed{1004}\).
