Happy new year, 2017!

Number Theory Level 4

Find the smallest positive integer $n$ such that $1^n+2^n+\cdots+2016^n$ is not divisible by 2017.

Bonus: Generalize this problem.

The answer is 2016.

2 solutions

Khang Nguyen Thanh
Jan 6, 2017

We can prove the more general statement: With $p$ is a odd prime, $1^k+2^k+\ldots+(p-1)^k$ is divisible by $p$ if and only if $k$ is not divisible by $p-1$ .

If $p-1\mid k$ , according to Fermat theorem, we have $1^k+2^k+\ldots+(p-1)^k\equiv p-1\pmod{p}$ .

If $p-1 \nmid k$ , there is a primitive root $m$ mod $p$ . Hence,

$1^k+2^k+\ldots+(p-1)^k\equiv m^k+(m^2)^k+\ldots+ (m^{p-1})^k\equiv m^k\cdot\dfrac{(m^k)^{p-1}-1}{m^k-1}\pmod{p}$ .

Since m is a primitive root mod $p$ and $p-1\nmid k$ , $p\nmid m^k-1$ .

Combine with $p\mid(m^k)^{p-1}-1$ , we get $1^k+2^k+\ldots+(p-1)^k\equiv 0\pmod{p}$ .

So the answer of this problem is $\boxed{2016}$ .

Faulhaber showed that if a sum for an odd power is given by

$\displaystyle \sum_{k=1}^n k^{2m+1}=c_{1}a^2+c_{2}a^3+.........+c_{m}a^{m+1}$

and for even power,

$\displaystyle \sum_{k=1}^n k^{2m}=\dfrac{(n+\dfrac{1}{2})}{2m+1}(2c_{1}a+3c_{2}a^2+.........+(m+1)c_{m}a^m)$

where, $a=\dfrac{n\times(n+1)}{2}$

we can see that it will be independent of $(n+1)$ for even powers when $2m=n$

thus the power has to be 2016

Anirudh Sreekumar - 4 years, 4 months ago

First of all, avoid double notation. When you say $2m = n$ , do you really want the $n$ to be the same as the $n$ in the summation? Or are you just talking about "any even power"? I believe it's the latter, but right now it indicates the former.

Secondly, it is not clear to me why the answer will be independent of $n+1$ . Since $a$ is already a function of $n+1$ , and the RHS is a polynomial in $a$ (though we don't know the coefficients), it seems very likely that it will be a polynomial in $n + 1$ , especially if $n+1$ is odd.

Thirdly, I believe you want it to be "dependent on $n+1$ ", or that "it is a polynomial in $n+1$ ", in order for us to conclude that $n+1$ divides this value (as shown in the proof). If so, you have to be careful about why it fails for 2016, but works for 1 to 2015.

Calvin Lin Staff - 4 years, 4 months ago

1 issue, you can guess this, I actually did.

Razzi Masroor - 4 years, 4 months ago

The Dark Lord
Feb 24, 2018

Can we do it like this ??

$2017$ is prime so from FLT $a^{p-1} \equiv 1 \pmod {p}$ we get $\displaystyle \sum_{i=1}^{2016} i^{2017-1} \equiv 2016 \equiv -1 \pmod {2017}$ .But I am unable to prove as to why 2016 must be smallest possible.

Happy new year, 2017!

The answer is 2016.

2 solutions

0 pending reports