Show that $\varphi(n^2)=\varphi(k^2)$ if and only if $n=k$, where $\varphi$ is the Euler's function.

Question

One of the exercises asked me to show the above statement. I have shown that $\varphi(n^2)=n\varphi(n),\varphi(k^2)=k\varphi(k)$ and how to continue from here?

Answer 1

If $n = k$, then $\varphi(n^2) = \varphi(k^2)$. For the other direction, I don't offhand know how to use what you've stated, i.e., that $\varphi(n^2) = n\varphi(n)$ and $\varphi(k^2) = k\varphi(k)$ (note that, as shown in the Other formulae section, the more general case is $\varphi(n^m) = n^{m-1}\varphi(n)$).

Instead, if $n = 1$, then $\varphi(n^2) = \varphi(k^2) = 1$, so $k^2 = 1$ or $k^2 = 2$, which means $k^2 = 1 \; \to \; k = 1$. Similarly, if $k = 1$, we get $n = 1$. Otherwise, with $n \gt 1$ and $k \gt 1$, use the unique prime factorizations of $n$ and $k$, with the distinct prime factors expressed in increasing order, to get

$$n = \prod_{i=1}^{j}p_i^{a_i} \; \to \; \varphi(n^2) = \prod_{i=1}^{j}(p_i-1)p_i^{2a_i-1}, \; \; p_i \lt p_{i+1} \; \forall \; 1 \le i \lt j \tag{1}\label{eq1A}$$

$$k = \prod_{i=1}^{m}q_i^{b_i} \; \to \; \varphi(k^2) = \prod_{i=1}^{m}(q_i-1)q_i^{2b_i-1}, \; \; q_i \lt q_{i+1} \; \forall \; 1 \le i \lt m \tag{2}\label{eq2A}$$

If $p_j \gt q_m$, then since $2a_j-1\ge 1$, we have $p_j \mid \varphi(n^2)$. However, $p_j \not\mid \varphi(k^2)$ (since all of its prime factors are smaller), which is not possible. Similarly, $q_m \gt p_j$ also fails, so $q_m = p_j$. Next, since all other prime factors in $\varphi(n^2)$ and $\varphi(k^2)$ are smaller, using the $p$-adic valuation function (i.e., the exponent of the prime factor), we get $\nu_{p_j}(\varphi(n^2)) = 2a_j - 1$ and $\nu_{q_m}(\varphi(k^2)) = 2b_m - 1$, so $2a_j - 1 = 2b_m - 1 \; \to \; a_j = b_m$.

Thus, dividing $\varphi(n^2)$ in \eqref{eq1A} by $(p_j-1)p_j^{2a_j-1}$, and $\varphi(k^2)$ in \eqref{eq2A} by $(q_m-1)q_m^{2b_m-1}$, results in the values still being equal to each other. Repeat this procedure with each next largest prime factor in \eqref{eq1A} and \eqref{eq2A}, with it being impossible for there to be a different number of prime factors between them because then the values won't be equal, until all of the factors have been divided out in both \eqref{eq1A} and \eqref{eq2A}.

The end result is that $j = m$, plus $(p_i = q_i \land a_i = b_i) \; \forall \; 1 \le i \le j$, i.e., that $n = k$. Note this same technique can be used to prove the more general $\varphi(n^s) = \varphi(k^s) \iff n = k$ for all integers $s \ge 2$.