[Math] Calculate Euler’s totient function for perfect squares

number theorytotient-function

Can $φ(n)$ be easily calculated when $n$ is a perfect square i.e. there exists a natural number $k$ so that $n=k^2$?

Best Answer

If $p_1$ through $p_n$ form the unique primes in the prime factorization of $k$ (so not including multiplicities) we can use the following definition:

$$\varphi(k) = k\left(1 - \frac1{p_1}\right)\left(1 - \frac1{p_2}\right)\cdots\left(1 - \frac1{p_n}\right)$$

And the knowledge that each prime in the factorization of $k$ occurs twice in $k^2$, without introducing any new primes to find out:

$$\varphi(k^2) = k^2\left(1 - \frac1{p_1}\right)\left(1 - \frac1{p_2}\right)\cdots\left(1 - \frac1{p_n}\right)$$

$$\varphi(k^2) = k\varphi(k)$$