1
$\begingroup$

I've tried this with a few examples, but how would I show that it's true for EVERY odd number $n$? And why wouldn't it work for even number $n$?

$\endgroup$
  • $\begingroup$ It wouldn't work for even number $n$ because $1^2$ is not divisible by $2$, so $n=2$ is invalid. That being said, the problem doesn't say that it doesn't work for (at least some) even numbers. It just asks you to show that it does work for odd numbers. $\endgroup$ – Arthur Apr 19 at 23:16
  • $\begingroup$ For even $n$ see OEIS A182398 $\endgroup$ – Henry Apr 19 at 23:39
  • $\begingroup$ Essentially a dupe of this and likely many others. See there for links to generalizations. $\endgroup$ – Bill Dubuque Apr 19 at 23:50
2
$\begingroup$

Suppose $n$ is an odd number. Note that the sequence $1,2,3,...,n-1$ can be written like this:

$1,2,...,\frac{n-1}{2},n-\frac{n-1}{2},...,n-2,n-1$.

For each $k\in\{1,2,...,\frac{n-1}{2}\}$ we obviously have $n-k\equiv -k$(mod $n$). Since $n$ is odd $(-k)^n=-k^n$ and hence $(n-k)^n\equiv -k^n$(mod $n$). And from here we get:

$1^n+2^n+...+(n-1)^n\equiv 1^n+2^n+...+(\frac{n-1}{2})^n-(\frac{n-1}{2})^n-...-2^n-1^n\equiv 0$(mod $n$).

So the sum is divisible by $n$ just as we wanted.

As for even values take $n=2$ as a counterexample.

$\endgroup$
1
$\begingroup$

Hint:

  • For odd $n$, can you show $k^n+(n-k)^n$ is divisible by $n$? (Try the binomial expansion)

  • Then add these up for $k \in \{1,2,\ldots,\frac{n-1}{2}\}$

$\endgroup$
0
$\begingroup$

Firstly, $k\equiv k-n \mod n$.

For odd $n>1$, $$A:=\sum^{n-1}_{k=1}k^n\equiv \sum^n_{k=1}k^n\equiv\sum^{n}_{k=1}(k-n)^n=-\sum^n_{k=1}(n-k)^n=-\sum^n_{k=1}k^n\equiv-\sum^{n-1}_{k=1}k^n =-A\mod n$$

$A\equiv -A \mod n\implies 2A\equiv 0\mod n$.

Hence, either $2\equiv 0\mod n$ (impossible) or $A\equiv 0\mod n$, which is the desired conclusion.

$\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.