+0

# number theory

0
31
1

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

Nov 13, 2022

#1
+17
+1

Using modular arithmetic, we can create three "equations."

$$n\equiv 5 \pmod{9}$$

$$n\equiv 2 \pmod{7}$$

$$n\equiv4\pmod{5}$$

from the last equation, we get that $$n = 5a+4$$ for some integer a. From the middle one, we get $$n = 7b+2$$ for some integer b. Set these equal to each modulo 5 to get that$$5a + 4 \equiv 7b+2 \pmod{5}$$. you get that $$2b\equiv 2\pmod{5}$$, so $$b \equiv 1 \pmod{5}$$. So, $$b = 5c+1$$ for some integer c and the bottom system simplifies to 7(5c+1) + 2 = 35c+9, so $$n\equiv 9\pmod{35}$$

We do the same with this and the top equation we left out before to get that $$n = 315e + 149$$ for some integer e. e=3 minimizes the four digit integer, and we get n = 1094.

hope this helped

Nov 13, 2022