Skip to main content
4 of 4
Removed congruence
joro
  • 25.4k
  • 10
  • 66
  • 121

Identity?: $\frac{\varphi(2^n-1)}{n}=\frac{2^{\varphi(2^n-1)}-1 \bmod (2^n-1)^2}{2^n-1}$

The computer found this.

Let $n$ be a positive integer.

Up to $n=200$ we have:

$$\frac{\varphi(2^n-1)}{n}=\frac{2^{\varphi(2^n-1)}-1 \bmod (2^n-1)^2}{2^n-1}. \tag{1}\label{483144_1}$$

Q1 Is \eqref{483144_1} true?

Observe that the LHS is exponential in $n$ and the RHS is doubly exponential in $n$ and we reduce modulo $(2^n-1)^2$.

Sage code:

def mers1(n):  return euler_phi(2**n-1)/n
def mers2(n):
   return lift((Integers((2**n-1)**2)(2))**euler_phi(2**n-1)-1)/(2**n-1)
joro
  • 25.4k
  • 10
  • 66
  • 121