2
$\begingroup$

Let $n\geq 1$ an integer, we denote the Euler's totient function as $\varphi(n)$ and the greatest prime dividing $n$ as $\operatorname{gpf}(n)$ (that it the arithmetic function defined in the MathWorld's article Greatest Prime Factor).

I know that is it possible to prove the following claim (I was inspired in [1] to ask a similar question).

Claim. If $n$ is an integer of the form $n=p\cdot(2^p-1)$ , where $2^p-1$ is a Mersenne prime, then satisfies $$\varphi(n)=n-\log_2(1+\operatorname{gpf}(n))-\operatorname{gpf}(n)+1.\tag{1}$$

In this post I ask about if those are the only solutions of the equation $(1)$.

Previous equation $(1)$ can be written also as $$\left(1+\operatorname{gpf}(n)\right)\cdot 2^{\varphi(n)+\operatorname{gpf}(n)}=2^{n+1}.\tag{2}$$

Question. Prove or disprove* the following conjecture:

If an integer $N\geq 1$ satisfies our equation $$\left(1+\operatorname{gpf}(N)\right)\cdot 2^{\varphi(N)+\operatorname{gpf}(N)}=2^{N+1}$$ then $N=p(2^p-1)$, where $2^p-1$ is a Mersenne prime. Many thanks.

*To disprove it show a counterexample.

References:

[1] Tripathi, A note on products of primes that differ by a fixed integer, The Fibonacci Quarterly, Vol. 48, No. 2 (MAY, 2010).

$\endgroup$
4
$\begingroup$

First of all, $gpf(N)$ must be a Mersenne-prime because $1+gpf(N)$ must be a power of $2$. Denote this Mersenne prime as $M=2^p-1$ with prime number $p$

This leads to $$p+\varphi(N)+2^p-1=N+1$$ $$p+\varphi(N)+M=N+1$$

$M^2|N$ would imply $M|\varphi(n)$ , hence we would have $p \equiv 1\mod M$ , but because of $p<2^p$, we have $0<p-1<2^p-1$, hence $M$ cannot divide $p-1$.

Hence we have $N=kM$ with $\gcd(k,M)=1$ , so we get $$p+\varphi(k)(M-1)+M=kM+1$$

which is equivalent to $$p-(\varphi(k)+1)=M(k-1-\varphi(k))$$

We have $k-1\ge \varphi(k)$ with equality if and only if $k$ is prime. If the inequality is strict, the right side is at least $M$ , but the left side smaller than $p$, this is impossible because of $p-1<2^p-1$. Hence $k$ must be a prime, the right side is $0$ and we have $p=\varphi(k)+1=k-1+1=k$. This completes the proof that the conjecture is actually true.

$\endgroup$
  • $\begingroup$ Many thanks I am going to study your answer. $\endgroup$ – user243301 Jun 28 '18 at 11:00
  • 1
    $\begingroup$ @user243301 I just fixed some errors, hopefully everything is OK now. $\endgroup$ – Peter Jun 28 '18 at 11:04
  • $\begingroup$ I've understand all your proof with the exception of the third paragraph (I'm sure that it is right, but I need to read and study it again), any case I believe that the following is your same proof. Proof by contradiction that $\gcd(k,2^p-1)=1$: If we assume $k=(2^p-1)^\alpha\cdot m$ with $\alpha\geq 1$ and $m\geq 1$ integers, and $\gcd(m,(2^p-1))=1$ then $$p+\left((2^p-1)^{\alpha+1}-(2^p-1)^{\alpha}\right)\cdot\varphi(m)+(2^p-1)=(2^p-1)^{\alpha+1}m+1.$$ And dividing by $2^p-1$ it leads again to the absurd $2^p-1\mid p-1$. $\endgroup$ – user243301 Jul 1 '18 at 7:31
  • $\begingroup$ Thus many thanks for your answer and the merit of this new characterization of Mersenne primes, is yours. $\endgroup$ – user243301 Jul 1 '18 at 7:32
  • 1
    $\begingroup$ @user243301 The totient function is multiplicative for coprime integers, in particular, if a prime power $p^k$ divides $N$, then $\varphi(p^k)=p^{k-1}\cdot (p-1)$ divides $\varphi(N)$ For $k\ge 2$, we get $p|\varphi(N)$ $\endgroup$ – Peter Jul 1 '18 at 7:42

Your Answer

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