elementary number theory - 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.

Answer

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}$$