3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I do not understand the argument towards the end. There is an easy proof, but it requires more specific information about the $p_i$. Use the fact they are Fermat primes. $\endgroup$ – André Nicolas Apr 7 '16 at 6:10
  • $\begingroup$ @AndréNicolas Basically we can show that each odd prime $p_i$ is a Fermat's prime. But without that information I am trying to complete the track. Won't it be possible sir ? $\endgroup$ – Anjan3 Apr 7 '16 at 6:14
  • 1
    $\begingroup$ To make sure different combinations of primes give different products, one will need ro know more than the fact the $p_i-1$ are powers of $2$, since products of different powers of $2$ can be equal. $\endgroup$ – André Nicolas Apr 7 '16 at 6:19
  • $\begingroup$ In that case dear sir, I failed to prove the problem. Can you please help me ? :-( $\endgroup$ – Anjan3 Apr 7 '16 at 6:21
  • $\begingroup$ The point about the Fermat numbers is that they grow so fast that a product of them must be less than the next one. $\endgroup$ – André Nicolas Apr 7 '16 at 6:22
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.