+0

# number theory

0
54
3

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?

Jun 19, 2021

#1
+26112
+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?

$$\begin{array}{|rcll|} \hline n &\equiv& {\color{red}5} \pmod{9} \\ n &\equiv& {\color{red}3} \pmod{7} \\ n &\equiv& {\color{red}4} \pmod{5} \\ \text{Let}~ m &=& 9*7*5 = 315 \\ \hline \end{array}$$

Because 9 and 7 and 5 are relatively prim $$\Big(\gcd(9,7,5)=1\Big)$$,
we can go on.

$$\begin{array}{|rcll|} \hline n &=& {\color{red}5} *7*5*\dfrac{1}{7*5}\pmod{9} \\ && +{\color{red}3} *9*5* \dfrac{1}{9*5}\pmod{7} \\ && +{\color{red}4} *9*7* \dfrac{1}{9*7}\pmod{5} \\ && + 315k \quad | \quad k \in \mathbb{Z} \\\\ n &=& 175* \left(\dfrac{1}{35}\pmod{9}\right) \\ && +135*\left(\dfrac{1}{45}\pmod{7}\right) \\ && +252* \left(\dfrac{1}{63}\pmod{5}\right) \\ && + 315k \\\\ \hline \end{array} \begin{array}{|lcll|} \hline \dfrac{1}{35}\pmod{9} \quad | \quad 35 \equiv -1 \pmod{9} \\ \equiv \dfrac{1}{-1}\pmod{9} \\ \dfrac{1}{35}\pmod{9}\equiv -1\pmod{9} \\ \hline \dfrac{1}{45}\pmod{7} \quad | \quad 45 \equiv 3 \pmod{7} \\ \equiv \dfrac{1}{3}\pmod{7} \\ \equiv 3^{\phi(7)-1}\pmod{7} \\ \equiv 3^{6-1}\pmod{7} \\ \equiv 3^{5}\pmod{7} \\ \equiv 243 \pmod{7} \\ \dfrac{1}{45}\pmod{7} \equiv 5 \pmod{7} \\ \hline \dfrac{1}{63}\pmod{5} \quad | \quad 63 \equiv 3 \pmod{5} \\ \equiv \dfrac{1}{3}\pmod{5} \\ \equiv 3^{\phi(5)-1}\pmod{5} \\ \equiv 3^{4-1}\pmod{5} \\ \equiv 3^{3}\pmod{5} \\ \equiv 27 \pmod{5} \\ \dfrac{1}{63}\pmod{5}\equiv 2 \pmod{5} \\ \hline \end{array}$$

$$\begin{array}{|rcll|} \hline n &=& 175* \left(\dfrac{1}{35}\pmod{9}\right) \\ && +135*\left(\dfrac{1}{45}\pmod{7}\right) \\ && +252* \left(\dfrac{1}{63}\pmod{5}\right) \\ && + 315k \\\\ n &=& 175*(-1) +135*5 +252*2 + 315k \\ n&=& -175 +675 + 504 +315k \\ n &=& 1004 + 315k \quad | \quad 1004 \equiv 59 \pmod{315} \\ n &=& 59 + 315k \\ \mathbf{ n_{\text{min.}}} &=& \mathbf{ 59 } \\ \hline \end{array}$$

Jun 19, 2021
#3
+26112
+2

The smallest possible value of n is a four-digit positive integer

$$\begin{array}{|rcll|} \hline \mathbf{n} &=& \mathbf{59 + 315k} \\ 59 + 315k &>& 999 \\ 315k &>& 999 - 59 \\ 315k &>& 940 \\\\ k &>& \dfrac{940}{315} \\\\ k &>& 2.9841269841 \\ \mathbf{k} &=& \mathbf{3} \\ n_{\text{The smallest possible value of n is a four-digit positive integer }} &=& 59 + 315*3 \\ \mathbf{n} &=& \mathbf{1004} \\ \hline \end{array}$$

heureka  Jun 20, 2021
#2
+287
+2

Isn't N a four-digit positive integer?

Jun 20, 2021