Let $p>2$ be an odd number and let n be a positive integer. Prove that $p$ divides $$1^{p^n}+2^{p^n}+...+(p-1)^{p^n}.$$

Here is the solution:

Define $k = p^n$ and note that $k$ is odd. Then \begin{equation} \label{eq} d^k + (p-d)^k = p[d^{k-1}-d^{k-2}(p-d)+...+(p-d)^{k-1}]\qquad\text{[1]} \end{equation}

But how exactly the left part expands into the right part?

I would like to see how you get the right part of it from the left part: https://i.stack.imgur.com/QT9rz.jpg

  • $\begingroup$ Please use MathJax. $\endgroup$ – José Carlos Santos Aug 10 '17 at 15:00
  • $\begingroup$ You can also look at the equation modulo $p$ i.e. ignoring multiples of $p$ and you get $d^k+(p-d)^k\equiv d^k+(-d)^k=0$ (crucially $k$ is odd) which means that the original expression differs from $0$ by a multiple of $p$. $\endgroup$ – Mark Bennet Aug 10 '17 at 15:24
  • $\begingroup$ @MarkBennet I got it. But then, where did all the multiples of k go? $\endgroup$ – NiHao92 Aug 10 '17 at 16:43
  • $\begingroup$ @NiHao92 Multiples of $k$ are multiples of $p$ and any multiple of $p$ is essentially ignored. $\endgroup$ – Mark Bennet Aug 10 '17 at 17:26

You probably know this factorisation

$$x^n-1 = (x-1)(x^{n-1} + x^{n-2} + ... + x + 1)$$

There is also a homogeneous version, which you can get by substituting $x=a/b$ and multiplying through by $b^n$:

$$a^n-b^n = (a-b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + ... + b^{n-1})$$

In this case we use $a=d$ and $b=-(p-d)$, as well as $n=k$.

  • $\begingroup$ thanx. But how did the authors of the textbook come to applying this equation? What is the logical thought thread here, or did they just see the pattern(the formula you posted here) in the example? $\endgroup$ – NiHao92 Aug 10 '17 at 16:55

It looks like this is achieved by expanding $(p-d)^k$ using the binomial formula. We need to know that $k$ is odd to know that the final term, $d^k$ has a minus sign, and thus cancels the initial $d^k$, leaving only terms that are multiples of $p$.

$$(p-d)^k = p^k - kp^{k-1}d + \binom{k}{2}p^{k-2}d^2 - \cdots - d^k$$

Note that each term except for the last is a multiple of $p$, so when that last term goes away, a $p$ can be factored out of what remains.

  • $\begingroup$ Clearly this expansion works for the proof. It seems they've used something slightly different though, since there are still terms with powers of $(p-d)$ in them. $\endgroup$ – Jaap Scherphuis Aug 10 '17 at 15:13
  • $\begingroup$ I know that, but here I don't see any k as a factor, only as a power $ p[d^{k-1}-d^{k-2}(p-d)+...+(p-d)^{k-1}]$ $\endgroup$ – NiHao92 Aug 10 '17 at 15:14
  • $\begingroup$ @G Tony Jacobs where did all the k factors go, in my equation? $\endgroup$ – NiHao92 Aug 10 '17 at 16:42
  • $\begingroup$ It's clear this isn't how the authors did it in your case. It works, but this isn't the answer you're looking for. $\endgroup$ – G Tony Jacobs Aug 10 '17 at 21:58

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.