Let f(n)=∑d|n,d>0ϕ(d)f(n)=\sum_{d|n, d>0}\phi(d).

If p is prime, prove that f(pa)=paf(p^a)=p^a. Deduce that f(n)=nf(n)=n

So far I figured out that the divisors of pap^a are 1,p,…,pa1, p, …, p^a

so f(pa)f(p^a)=ϕ(1)+ϕ(p)+…+ϕ(pa)\phi(1)+\phi(p)+…+\phi(p^a)=(1)+(p−1)+…+(pa−1)=(1)+(p-1)+…+(p^{a}-1)

I got stuck here. How can I go from here to pap^a?

=================

That really looks like a geometric sum.

– YoTengoUnLCD

2 days ago

Actually it isn’t, it just telescopes nicely.

– xyzzyz

2 days ago

1

Possible duplicate of Prove that ∑d|nϕ(d)=n\sum_{d|n}\phi(d)=n where ϕ\phi is the Euler’s phi function, n,c∈Nn,c\in\mathbb{N}

– Dietrich Burde

2 days ago

It’s both a telescoping sum, and (aside from the initial 11) a geometric sum.

– Greg Martin

2 days ago

1

@DietrichBurde: I’d say this isn’t a duplicate of the other question, since this question asks about a very specific proof method, whereas the other one uses other proofs.

– Greg Martin

2 days ago

=================

1 Answer

1

=================

You’ve made a small error in computing ϕ(pn)\phi(p^n). ϕ(pn)=pn−pn−1\phi(p^n) = p^n – p^{n-1}, not pn−1p^n – 1. If kk is relatively prime to pnp^n, kk must be relatively prime to pp. Thus, to count ϕ(pn)\phi(p^n), we need to count multiples of pp less than or equal to pnp^n. These are p,2p,3p,…,(pn−1−1)p,pn−1pp, 2p, 3p,\dots, (p^{n-1} – 1)p, p^{n-1} p. There are precisely pn−1p^{n-1} such numbers, so ϕ(pn)=pn−pn−1\phi(p^n) = p^n – p^{n-1}. So the sum you want to compute is actually

∑d∣pn,d>0ϕ(d)=ϕ(1)+ϕ(p)+⋯+ϕ(pn)=1+(p−1)+(p2−p)+⋯+(pn−pn−1).

\sum_{d\mid p^n, \, d > 0}\phi(d) = \phi(1) + \phi(p) + \dots + \phi(p^n) = 1 + (p – 1) + (p^2 – p) + \dots + (p^n – p^{n-1}).

Can you finish it from here?