4.II .7E. 7 \mathrm{E} \quad

Numbers and Sets | Part IA, 2005

State and prove the Principle of Inclusion and Exclusion.

Use the Principle to show that the Euler totient function ϕ\phi satisfies

ϕ(p1c1prcr)=p1c11(p11)prcr1(pr1).\phi\left(p_{1}^{c_{1}} \cdots p_{r}^{c_{r}}\right)=p_{1}^{c_{1}-1}\left(p_{1}-1\right) \cdots p_{r}^{c_{r}-1}\left(p_{r}-1\right) .

Deduce that if aa and bb are coprime integers, then ϕ(ab)=ϕ(a)ϕ(b)\phi(a b)=\phi(a) \phi(b), and more generally, that if dd is any divisor of nn then ϕ(d)\phi(d) divides ϕ(n)\phi(n).

Show that if ϕ(n)\phi(n) divides nn then n=2c3dn=2^{c} 3^{d} for some non-negative integers c,dc, d.

Typos? Please submit corrections to this page on GitHub.