+0  
 
0
101
2
avatar

There is a number formed by n copies of 2020 and 1 in the unit place. If this number is divisible by 17, what is the smallest possible value of n?

 May 26, 2021
 #1
avatar+34390 
+1

n = 6 by trial and error .... (  2020 * 6   + 1  ) / 17 = 713

 May 26, 2021
 #2
avatar+26213 
+1

Number Theory

There is a number formed by n copies of 2020 and 1 in the unit place.
If this number is divisible by 17,
what is the smallest possible value of n?


Formula: \(2020n+1 \equiv 0 \pmod{17} \)

 

\(\begin{array}{|rcll|} \hline 2020n+1 &\equiv& 0 \pmod{17} \quad &|\quad 2020 \equiv 14 \pmod{17} \\ 14n+1 &\equiv& 0 \pmod{17} \\ 14n &\equiv& -1 \pmod{17} \\ n &\equiv& (-1)\dfrac{1}{14} \pmod{17} \\ \hline \end{array}\)

 

Modular multiplicative inverse using Euler's theorem:

\(\begin{array}{|rcll|} \hline \dfrac{1}{14} \pmod{17} &\equiv& 14^{\phi(17)-1} \pmod{17} \quad &|\quad \phi(17)=16 \\ &\equiv& 14^{16-1} \pmod{17} \\ &\equiv& 14^{15} \pmod{17} \quad &|\quad 14 \equiv -3 \pmod{17} \\ &\equiv& (-3)^{15} \pmod{17} \\ &\equiv& -(3)^{15} \pmod{17} \\ &\equiv& -(3)^{5*3} \pmod{17} \\ &\equiv& -\left(3^5\right)^{3} \pmod{17}\quad &|\quad 3^5 \equiv 5 \pmod{17} \\ &\equiv& -(5)^3 \pmod{17} \\ &\equiv& -125 \pmod{17} \quad &|\quad 125 \pmod{17} \equiv 6 \pmod{17} \\ \mathbf{ \dfrac{1}{14} \pmod{17} } &\equiv& \mathbf{ -6 \pmod{17}} \\ \hline \end{array}\)

 

\(\begin{array}{|rcll|} \hline n &\equiv& (-1)\dfrac{1}{14} \pmod{17} \quad &|\quad \mathbf{ \dfrac{1}{14} \pmod{17} \equiv -6 \pmod{17}}\\ n &\equiv& (-1)(-6) \pmod{17} \\ \mathbf{n} &\equiv& \mathbf{6 \pmod{17}} \\ n &=& 6+17k \qquad k\in \mathbb{Z} \\ \hline \end{array}\)

 

The smallest possible value of \(n\) is \(\mathbf{6}\)

 

laugh

 May 26, 2021

34 Online Users

avatar