+0  
 
0
106
2
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 4. What is the smallest possible value of  N?

 Jan 10, 2022
 #1
avatar+26 
0

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}\).

 Jan 11, 2022
edited by pogyou  Jan 11, 2022
 #2
avatar
0

LCM(9,7,5) ==315

 

LCM(3, 4, 5)==60

 

315n  + (60 - 1)==315n  +  59, where n==0, 1, 2, 3,4,........etc.

 

The smallest 4-digit integer ==[314 x 3  +  59] ==945  +  59 ==1,004

 Jan 11, 2022

6 Online Users