+0

# Number Theory

0
252
2

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
+36433
+1

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

May 26, 2021
#2
+26321
+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}$$

May 26, 2021