For each positive integer $k$, there is a positive integer $m\neq 3k$ such that $\varphi(3k)=\varphi(m)$ (with $\varphi(n)$ being Euler's totient)

Question

Prove that for every positive integer $k$, $\exists m\neq 3k, m\in\mathbb{Z}^+$ such that $\varphi(3k)=\varphi(m)$. Here $\varphi(n)$ is Euler's totient function.

I am interested in the problem above. The above is my observation, but I have to idea how to prove it. Any help will be highly appreciated.

Answer 1

Two easy cases:

• If $k$ is odd, then $\varphi(6k)=\varphi(3k)$.

• If $k$ is even and $3$ does not divide $k$, then $\varphi(2k)=\varphi(3k)$.

The remaining case is when $6$ divides $k$.

Answer 2

Partial answer. Euler's totient function is multiplicative, i.e. if $\gcd(m,n)=1$ then $\varphi(m\cdot n)=\varphi(m)\cdot \varphi(n)$.

---

Let's consider $\gcd(6, k)=1$, then $\gcd(2^2,k)=1$ and $\gcd(3,k)=1$. And: $$\varphi(3\cdot k)= \varphi(3)\cdot \varphi(k)= 2\cdot \varphi(k)$$ $$\varphi(2^2\cdot k)= \varphi(2^2)\cdot \varphi(k)= 2\cdot \varphi(k)$$ So, we may consider $m=2^2\cdot k \ne 3\cdot k$.

---

Let's consider $\gcd(3, k)=1$ and $k=2^n\cdot k_1$, where $\gcd(2,k_1)=1$ (or $n$ is the maximum power of $2$ dividing $k$). Then: $$\varphi(3\cdot k)= \varphi(3)\cdot \varphi(k)= 2\cdot \varphi(2^{n}\cdot k_1)= 2\cdot 2^{n-1}\varphi(k_1)= 2^n\cdot\varphi(k_1)$$ $$\varphi(2\cdot k)=\varphi(2^{n+1}\cdot k_1)=\varphi(2^{n+1})\cdot \varphi(k_1)=2^{n}\cdot\varphi(k_1)$$ So, we may consider $m=2\cdot k \ne 3\cdot k$.

---

Let's consider $\gcd(2, k)=1$ and $k=3^n\cdot k_1$, where $\gcd(3,k_1)=1$ (or $n$ is the maximum power of $3$ dividing $k$). Then: $$\varphi(2\cdot3\cdot k)=\varphi(2)\cdot \varphi(3\cdot k)=\varphi(3^{n+1}\cdot k_1)=\varphi(3^{n+1})\cdot \varphi(k_1)=3^{n}\cdot 2 \cdot \varphi(k_1)$$ $$\varphi(3\cdot k)=\varphi(3^{n+1}\cdot k_1)=\varphi(3^{n+1})\cdot \varphi(k_1)=3^{n}\cdot 2 \cdot \varphi(k_1)$$ So, we may consider $m=6\cdot k \ne 3\cdot k$.

---

The remaining part is $6 \mid k$ or $k=2^{n_1}\cdot 3^{n_2}\cdot k_1$ where $n_1>0$, $n_2>0$, $\gcd(k_1,6)=1$.

$$\varphi(3\cdot k)= \varphi(2^{n_1}\cdot 3^{n_2+1}\cdot k_1)= 2^{n_1-1}\cdot 3^{n_2}\cdot 2\cdot \varphi(k_1)= 2^{n_1}\cdot 3^{n_2}\cdot \varphi(k_1)$$

• if $n_1=1$ then for $m=3^{n_2+1}\cdot k_1\ne 3k$ we have $\varphi(m)=2\cdot 3^{n_2}\cdot \varphi(k_1)$
• for $n_1 \geq 2$, we can use $2^2=\varphi(5)$ (assuming $k_1$ is not a multiple of $5$) or $2\cdot 3=\varphi(7)$ (assuming $k_1$ is not a multiple of $7$)

---

From here onwards, just observations ...

The last part of the previous section leads to $k=2^{n_1}\cdot 3^{n_2}\cdot 5^{n_3}\cdot 7^{n_4}\cdot k_1$ where $n_i>0$, $\gcd(k_1,2\cdot3\cdot5\cdot7)=1$. In this case we have $2\cdot5=\varphi(11)$.

---

The previous section leads to $k=2^{n_1}\cdot 3^{n_2}\cdot 5^{n_3}\cdot 7^{n_4}\cdot 11^{n_5}\cdot k_1$ where $n_i>0$, $\gcd(k_1,2\cdot3\cdot5\cdot7\cdot 11)=1$. In this case we have $2\cdot11=\varphi(23)$ or $2\cdot3\cdot5=\varphi(31)$

---

Then $2\cdot23=\varphi(47)$ or $2\cdot3\cdot7=\varphi(43)$.

---

How far did you go?