Prove that there exist infinitely many integers \(n\) which satisfy \(2017^2 | 1^n + 2^n + ... + 2017^n\).
Problem
Source: China Northern Mathematical Olympiad 2017
Tags: Divisibility, number theory
Muradjl
29.07.2017 16:31
we have $1^n+2^n+...+2017^n=\sum_{k=0}^{1008} (2017-k)^n+k^n$ take $n=2017^k.m$ where $m,k \geq 1$ by LTE : $v_{2017}(k^n+(2017-k)^n)=v_{2017}(2017)+v_{2017}(n)=1+v_{2017}(m)+k \geq 2 $
duck_master
29.07.2017 21:35
Faster: Note that n=3 is a solution, and that the value of $1^n + 2^n + ... + 2017^n$ must eventually become cyclic modulo $2017^2$, hence we have an infinite arithmetic progression of solutions.
Devastator
21.06.2018 13:00
It works when n=3 since $1^3+2^3+...+2016^3=(\frac{2016\cdot 2017}{2})^2$, which can be proved by induction, and it cycles every $\phi(2017^2)$ by Euler's Theorem (the one that's a generalization of FLT) [\hide]
Kaskade
21.06.2018 14:28
@Devastator It is called Euler's theorem, Fermat Euler theorem, or the Euler Totient theorem.
Using the well known fact $\sum_{r=1}^nr^3=\frac{n^2\left(n+1\right)^2}{4}$ we see that $n=3$ is a solution.
As $2017$ is prime, all the numbers below it are obviously coprime to $2017^2$, so by Fermat Euler
$\sum_{r=1}^{2016}r^{k\phi\left(2017^2\right)+3}=\sum_{r=1}^{2016}r^3=\frac{2016^2\cdot2017^2}{4}=0\left(\operatorname{mod}2017^2\right)$ for any integer $k$
Obviously $2017^n$ is going to be divisible by $2017^2$ for $n=k\phi\left(2017^2\right)+3$ so $k\phi\left(2017^2\right)+3$ is a solution for all non negative integers $k$
H.HAFEZI2000
21.06.2018 14:37
Muradjl wrote: we have $1^n+2^n+...+2017^n=\sum_{k=0}^{1008} (2017-k)^n+k^n$ take $n=2017^k.m$ where $m,k \geq 1$ by LTE : $v_{2017}(k^n+(2017-k)^n)=v_{2017}(2017)+v_{2017}(n)=1+v_{2017}(m)+k \geq 2 $ it's awesome!!!