0
$\begingroup$

Find all positive integers $n>1$ such that the following series is divisible by $n$: $$1^n + 2^n + 3^n + \ldots + (n-1)^n.$$

I started with considering separate cases for even and odd values of $n$ but couldn't make any progress, and on searching I found following conjecture:

If $n$ is a prime, then $$n \mid 1^{n-1}+2^{n-1} + \ldots + (n-1)^{n-1} + 1,$$

but I am not able to understand the proof. It seems the above is by fermat

$\endgroup$
1
  • $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ May 2 '20 at 6:06
0
$\begingroup$

Suppose $n$ is odd. Consider the sum modulo $n$. Then $$(n - k)^n \equiv (-k)^n \equiv (-1)^n k^n \equiv -k^n.$$ So, each term of the sum pairs uniquely with another term of the sum which is its negative. So, when $n$ is odd, the sum should be $0$ modulo $n$, i.e. divisible by $n$.

Otherwise, consider the case where $n$ is even. Then $n = 2^km$ for some odd $m$, and positive integer $k$. Consider the sum modulo $2^k$. Note that $k \le n$, hence if $r$ is an even number between $1$ and $n - 1$, then $2^k \mid r^n$.

Otherwise, if $r$ is an odd number in the range $1$ to $n - 1$. Then $r^n$ is odd, and there are an odd number of such terms. So, adding all the terms modulo $2^k$, we obtain an odd number, implying that the sum cannot be $0$ modulo $2^k$, and hence it can't be $0$ modulo $n$.

Therefore, the sum is divisible by $n$ if and only if $n$ is odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.