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?
+26367 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}\)
