Exercise 4.2.22* ($n \mapsto n \phi(n)$ is one-to-one)

Proof.

(a)

Suppose that $\mathit{m\varphi }(m)=\mathit{n\varphi }(n)$, where $m,n$ are positive integers. If $m=1$, then $\mathit{n\varphi }(n)=1$, thus $n=m=1$, and we have the same conclusion if $n=1$. We may assume now that $m>1,n>1$.

Let

$$m=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_l^{{\alpha }_l},n=q_1^{{\beta }_1}{q}_2^{{\beta }_2}\cdots q_r^{{\beta }_r}$$

be the decompositions of $n$ and $m$ in prime factors, where ${\alpha }_i>0,{\beta }_j>0$ for all $i,j$. The prime factors are arranged so that

$$p_1>p_2>\cdots >p_l,q_1>q_2>\cdots >q_r.$$

Possibly exchanging $m$ and $n$, we may suppose that ${\alpha }_1\ge {\beta }_1$. Then

$$\begin{array}{llll}\hfill \mathit{m\varphi }(m)& =p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_l^{{\alpha }_l}{p}_1^{{\alpha }_1-1}(p_1-1)p_2^{{\alpha }_2-1}(p_2-1)\cdots p_l^{{\alpha }_l-1}(p_l-1)& \hfill & \\ \hfill & =p_1^{2{\alpha }_1-1}{p}_2^{2{\alpha }_2-1}\cdots p_l^{2{\alpha }_l-1}(p_1-1)(p_2-1)\cdots (p_l-1)& \hfill & \end{array}$$

Moreover $p_1\nmid (p_1-1)$, and since $p_1>p_i$ for $i=2,\dots l$, $p_1\nmid p_i-1$, therefore

$${\nu }_{p_1}(\mathit{m\varphi }(m))=2{\alpha }_1-1.$$

Moreover $p_1$ is a divisor of

$$\mathit{n\varphi }(n)=q_1^{2{\beta }_1-1}{q}_2^{2{\beta }_2-1}\cdots q_r^{2{\beta }_r-1}(q_1-1)(q_2-1)\cdots (q_l-1).$$

If $p_1\ne q_1$, then $p_1>q_1>q_2>\cdots >q_r$ and $p_1>q_i-1$ for $i=1,\dots ,r$. Therefore $p_1\nmid \mathit{n\varphi }(n)$. This is a contradiction, therefore $p_1=q_1$. Since $p_1=q_1$ is not a divisor of $q_2^{2{\beta }_2-1}\cdots q_r^{2{\beta }_r-1}(q_1-1)(q_2-1)\cdots (q_l-1)$, we obtain

$${\nu }_{p_1}(\mathit{n\varphi }(n))=2{\alpha }_1-1=2{\beta }_1-1,$$

so ${\alpha }_1={\beta }_1$ (if ${\beta }_1\ge {\alpha }_1$, replacing $p_1$ by $q_1$ in the reasoning, we obtain the same result). The largest prime divisor of $m$ is a divisor of $n$ to the same power.

To introduce a strong induction, consider the proposition

$$𝒫(N):\forall <!--\; FUNCTION\; APPLICATION\; -->m\in {\mathbb{N}}^{\text{∗}},\forall <!--\; FUNCTION\; APPLICATION\; -->n\in {\mathbb{N}}^{\text{∗}},(m\le N\text{ and }n\le N\text{ and }\mathit{m\varphi }(m)=\mathit{n\varphi }(n))\Rightarrow m=n.$$

If $N=1$, then $m=n=1$, so $𝒫(1)$ is true. Suppose now that $𝒫(N)$ is true for some $N\ge 1$, and that $m\le N+1,n\le N+1$ and $\mathit{m\varphi }(m)=\mathit{n\varphi }(n)$. By the first part, the largest prime divisor $p=p_1$ of $m$ is a divisor of $n$ to the same power $\alpha >0$, so $m=p^{\alpha }{m}^{\prime },n=p^{\alpha }{n}^{\prime }$, where $p\nmid m^{\prime },p\nmid n^{\prime }$. Since $\varphi$ is multiplicative, the equality $\mathit{m\varphi }(m)=\mathit{n\varphi }(n)$ gives

$$p^{\alpha }{m}^{\prime }{p}^{\alpha -1}(p-1)\varphi (m^{\prime })=p^{\alpha }{n}^{\prime }{p}^{\alpha -1}(p-1)\varphi (n^{\prime }),$$

so

$$m^{\prime }\varphi (m^{\prime })=n^{\prime }\varphi (n^{\prime }),$$

where $m^{\prime }\le N,n^{\prime }\le N$. The induction hypothesis $𝒫(N)$ shows that $m^{\prime }=n^{\prime }$, thus $m=n$, and the induction is done.

If $\mathit{m\varphi }(m)=\mathit{n\varphi }(n)$ for positive integers $m$ and $n$, then $m=n$.

(b)

Using the values of $\sigma$ given in Problem 3, we obtain $$12\sigma (12)=12\times 28=336,14\sigma (14)=14\times 24=336.$$

So $12\sigma (12)=14\sigma (14)$.

(Other examples are the pairs $48,62$ and $60,70$.)