8
$\begingroup$

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)
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Note that for $n=1$, $\varphi(1)/1=1$, while $(1 \bmod 1)/1=0$. So I guess $n>1$. $\endgroup$
    – Fred Hucht
    Commented Nov 25 at 20:08

1 Answer 1

Reset to default
13
$\begingroup$

Denote by $a$ the left hand side and $m = 2^n - 1$. We know that $a$ is an integer, since $n$ is the order of $2$ in $(\mathbb{Z} / m \mathbb{Z})^*$. We want to prove that $2^{an} - 1 - am \equiv 0 \pmod{m^2}$. But $2^n = m + 1$ and hence it is equivalent to $(m + 1)^a - 1 - am \equiv 0 \pmod{m^2}$ which is clear.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks, this is of interest. I edited clarifying that I am working over the integers and congruence is not a full answer to the question. $\endgroup$
    – joro
    Commented Nov 26 at 9:47
  • 4
    $\begingroup$ But $\varphi(2^n-1)/n<2^n-1$, so this is complete. It is a prime example of why formulating things as in (1) is harder to work with than congruences and inequalities. $\endgroup$
    – Chris Wuthrich
    Commented Nov 26 at 10:30
  • 1
    $\begingroup$ @ChrisWuthrich I still fail to understand why congruence $\mod{m^2}$ in which there is exponent $a=(\varphi(2^n-1))/n$ implies equality over the integers. $\endgroup$
    – joro
    Commented Nov 26 at 11:43
  • 4
    $\begingroup$ @joro You want the identity $am = (2^{an}-1 \pmod{m^2})$. I assume that by equality over integers you mean that the right hand side is a number less than $m^2$. But $am < m^2$, that is why congruence $\mod m^2$ is enough. $\endgroup$
    – Petr Kucheryavy
    Commented Nov 26 at 12:44
  • 1
    $\begingroup$ @joro Remember that Euler's totient fulfils $0<\varphi(m)<m$ for $m=2^n-1>1$. Your identity holds for arbitrary functions $\phi(m)=a n$ with this property. $\endgroup$
    – Fred Hucht
    Commented Nov 26 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .