How to show that $\varphi(m_1)=\varphi(m_2)$ gives $m_1=m_2$?

Question

I have solved a problem in number theory which I am providing the details below how I did. Request to all of you, please check it and advise me if I made any mistake.

Let $m_1, m_2$ be two odd positive integers such that $$\varphi(m_1)=2^\alpha=\varphi(m_2),~~\text{for some}~~\alpha\in \{1,2,\cdots, 31\}$$ where $\varphi$ is Euler's phi function that counts the total number of relatively prime integers less than $n$ given. Then $m_1=m_2$.

Here is what I have done.

If possible let $m_1\neq m_2$. In that case, the canonical form of $m_2$ must contain a different prime factor than in the canonical form of $m_1$.

So without loss of generality we assume that $p_1, p_1'$ be two distinct primes such that $p_1|m_1, p_1\not\mid m_2, p_1'\not\mid m_1, p_1'|m_2$ and let the canonical form of $m_1, m_2$ be given by \begin{align*} &m_1=p_1^{a_1}\prod_{i=2}^{r}p_i^{a_i}\\ &m_2=p_1'^{a_1'}\prod_{i=2}^{s}p_i^{a_i} \end{align*} where each $a_1, a_1', a_2, \cdots, a_r, \cdots, a_s\in \mathbb{N}$ with $r\leqslant s$.

Now it is easy to show that each $a_1, a_1', a_i$ etc will be equal to 1. In other words, $m_1, m_2$ must be square free. I managed to prove that part. Please ignore it.

So we can write then \begin{align*} &m_1=p_1p_2p_3\cdots p_r \\ &m_2=p_1'p_2p_3\cdots p_s \end{align*} where $r\leqslant s$. Since $2^\alpha=\varphi(m_1)=\varphi(m_2)$, we must have \begin{align*} 2^\alpha=(p_1-1)\prod_{i=2}^{r}(p_i-1)=(p_1'-1)\prod_{i=2}^{s}(p_i-1) \end{align*} If $r<s$ then we get $p_1-1=(p_1'-1)\prod\limits_{i=r+1}^{s}(p_i-1)$ which is contradiction as RHS can be necessarily divided by $2^{s-r+1}$ but LHS is not.

If $r=s$ then we get $p_1-1=p_1'-1$ i.e. $p_1=p_1'$, contradiction again.

hence the proof.

Please tell me if I made any mistake. In case, if any mistake you find, please suggest me how to correct that.

Thank you in advance

Answer 1

You have shown that $m_1$ and $m_2$ must be square-free. The $p_i-1$ in your argument must be powers of $2$. It is a standard fact that if $2^k+1$ is prime, then $k$ must be a power of $2$. Thus all the $p_i$ must be Fermat primes, that is, primes of the form $2^{2^n}+1$.

There are currently only $5$ Fermat primes known, namely $3$,$5$,$17$,$257$, and $65537$, which is $2^{16}+1$.

Suppose that $m_1=p_1\cdots p_s$, where the $p_i$ are distinct Fermat primes, and that $m_2=q_1\cdots q_t$, where the $q_i$ are distinct Fermat primes.

We may assume that the $p_i$ and $q_i$ are distinct sets of primes. For if there is overlap, we may divide by common primes until there isn't.

Assume that the $p_i$ and $q_i$ are listed in ascending order. If $m_1\ne m_2$ we may assume without loss of generality that $q_t\gt p_s$.

Since $q_t$ is a Fermat prime, $q_t-1=2^{2^N}$ for some $N$. We have $\varphi(m_2)\ge 2^{2^N}$.

Since the $p_i$ are Fermat primes less than $q_t$, we have $$(p_1-1)(p_2-1)\cdots (p_s-1)\le 2^1 \cdot 2^2 \cdot 2^4\cdots 2^{2^{N-1}}.$$ The product on the right is $2$ to the power $1+2+4+\cdots +2^{N-1}$, which is less than $2^{2^N}$, so $\varphi(m_1)$ cannot be equal to $\varphi(m_2)$.

Remark: Since the problem restricts attention to numbers up to $2^{31}$, we can instead just consider the products of the known Fermat primes mentioned earlier in the answer.