# Prove summations are equal

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.

• This was discussed at the following MSE link, which in fact points to two threads on this problem. 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}$$
• What exactly do you mean by the " $r=1,n$ with the line over it? I think this was exactly what I needed though! Apr 26 '15 at 22:48
• 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}$. Apr 26 '15 at 23:02
• 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? Apr 26 '15 at 23:30
• @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. Apr 27 '15 at 0:02