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≡0(mod17)
2020n+1≡0(mod17)|2020≡14(mod17)14n+1≡0(mod17)14n≡−1(mod17)n≡(−1)114(mod17)
Modular multiplicative inverse using Euler's theorem:
114(mod17)≡14ϕ(17)−1(mod17)|ϕ(17)=16≡1416−1(mod17)≡1415(mod17)|14≡−3(mod17)≡(−3)15(mod17)≡−(3)15(mod17)≡−(3)5∗3(mod17)≡−(35)3(mod17)|35≡5(mod17)≡−(5)3(mod17)≡−125(mod17)|125(mod17)≡6(mod17)114(mod17)≡−6(mod17)
n≡(−1)114(mod17)|114(mod17)≡−6(mod17)n≡(−1)(−6)(mod17)n≡6(mod17)n=6+17kk∈Z
The smallest possible value of n is 6
