Let $a_1,a_2,...,a_n$ be integers such that $a_1^{20}+a_2^{20}+...+a_n^{20}$ is divisible by $2020$. Show that $a_1^{2020}+a_2^{2020}+...+a_n^{2020}$ is divisible by $2020$.
Problem
Source: Kosovo MO 2020 Grade 12, Problem 2
Tags: Kosovo, national olympiad, Olympiad, number theory, divisible
kaede
02.02.2020 18:23
$2020=2^{2} \cdot 5\cdot 101$. It is sufficient to show that $x^{2020} \equiv x^{20}\pmod{2020}$ for any integer $x$. Note that $\lambda ( 2020) =\text{lcm}( \lambda ( 4) ,\lambda ( 5) ,\lambda ( 101)) =\text{lcm}( 2,4,100) =100$. So we have $2020\mid x^{2}\left( x^{100} -1\right)$. In particular, we have $2020\mid x^{20}\left( x^{2000} -1\right)$, which implies $x^{2020} \equiv x^{20}\pmod{2020}$. $\blacksquare $
Vertil
02.02.2020 18:24
Note that $2020=101*5*2*2$ and $101$ is prime. So by Little Fermat's $(a_i^{20})^{101}\equiv(a_i)^{20}$ mod $101$. Clearly the second sum is divisible by 101 since the first sum is also divisible by 101. It is simple to show that both sums are also divisible by 4 and 5.
Vertil
02.02.2020 18:25
kaede wrote: $2020=2^{2} \cdot 5\cdot 101$. It is sufficient to show that $x^{2020} \equiv x^{20}\pmod{2020}$ for any integer $x$. Note that $\lambda ( 2020) =\text{lcm}( \lambda ( 4) ,\lambda ( 5) ,\lambda ( 101)) =\text{lcm}( 2,4,100) =100$. So we have $2020\mid x^{2}\left( x^{100} -1\right)$. In particular, we have $2020\mid x^{20}\left( x^{2000} -1\right)$, which implies $x^{2020} \equiv x^{20}\pmod{2020}$. $\blacksquare $ Sniped again, excellent solution.