+0

# Number Theory

0
106
2

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
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
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