Prove that:

$$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{2n} (-1)^k p^{2n-k} = p^{2n} - p^ {2n-1} + p^{2n-2} - ... + p^{2n-2n}$$

I'm not exactly sure how to do this unless I can say:

Assume $\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)}$ = $\sum_{k=0}^{2n} (-1)^k p^{2n-k}$

and show by induction that the sums equal each other and show the inductive step that you can take the expanded sum part with $n+1$ and get to $\sum_{k=0}^{2n+1} (-1)^k p^{2(n+1)-k}$

However, I'm not even sure that I am allowed to do this.. Any suggestion in how to prove this? I'm not looking for a whole proof just a push in the direction of how to solve this.

  • $\begingroup$ This was discussed at the following MSE link, which in fact points to two threads on this problem. $\endgroup$ Apr 26 '15 at 22:52

First note that $gcd(p^n,r)$ for $r=\overline{1,p^n}$ must be of the form $p^k$ with $k\in\overline{0,n}$, and for each $k$ there is exactly $\phi(p^{n-k})$ numbers with that property in $\overline{1,p^n}$ so: $$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{n} \frac{p^n}{p^k}\phi(p^{n-k}) = 1+\sum_{k=0}^{n-1} \frac{p^n}{p^k}p^{n-k}(1-\frac{1}{p}) = 1+\sum_{k=0}^{n-1} p^{2(n-k)}(1-\frac{1}{p}) = \sum_{k=0}^{2n} (-1)^k p^{2n-k} \square$$ For the last equality: $$\sum_{k=0}^{n-1} p^{2(n-k)}(1-\frac{1}{p}) = \sum_{k=0}^{n-1} (p^{2(n-k)}-p^{2(n-k)-1})= \sum_{k=0}^{n-1} ((-1)^{2(n-k)}p^{2(n-k)}+(-1)^{2(n-k)-1}p^{2(n-k)-1}) = \sum_{i=0}^{2n-1} (-1)^i p^{2n-i}$$

  • $\begingroup$ What exactly do you mean by the " $r=1,n$ with the line over it? I think this was exactly what I needed though! $\endgroup$ Apr 26 '15 at 22:48
  • $\begingroup$ I think that $\overline{a, b}$ means the integers from $a$ through $b$. If this is so, then I think the first use should be $\overline{1, p^n}$, not $\overline{1, n}$. $\endgroup$ Apr 26 '15 at 23:02
  • $\begingroup$ Okay thats kinda what I was thinking it was... Also, how exactly do you get $\sum_{k=1}^{n} p^{2(n-k)}(1-\frac{1}{p}) = \sum_{k=0}^{2n} (-1)^k p^{2n-k}$ And what is the square at the end? $\endgroup$ Apr 26 '15 at 23:30
  • $\begingroup$ @martycohen yes that's what it means, and thanks for pointing out the mistake $\endgroup$ Apr 26 '15 at 23:59
  • $\begingroup$ @JonathanSeeman $\overline{a,b}$ means the integer numbers from $a$ to $b$ inclusive, and the last equality was not true for $k=1$ to $n$ it must be from $k=0$ was a mistake fixed now. $\endgroup$ Apr 27 '15 at 0:02

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.