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

Removed congruence

Source Link

edited Nov 26 at 16:27

joro

25.4k
10
66
121

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$.

We are working over the integers and both sides are integers. By $\bmod N$ we take the smallest residue modulo $N$. Answer gives partial result congruence, which is of interest, but in its current state doesn't answer the question.

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)

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$.

We are working over the integers and both sides are integers. By $\bmod N$ we take the smallest residue modulo $N$. Answer gives partial result congruence, which is of interest, but in its current state doesn't answer the question.

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)

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)

Clarified that we working over the integers to address congruence in an answer

Source Link

edited Nov 26 at 9:45

joro

25.4k
10
66
121

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$.

We are working over the integers and both sides are integers. By $\bmod N$ we take the smallest residue modulo $N$. Answer gives partial result congruence, which is of interest, but in its current state doesn't answer the question.

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)

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)

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$.

We are working over the integers and both sides are integers. By $\bmod N$ we take the smallest residue modulo $N$. Answer gives partial result congruence, which is of interest, but in its current state doesn't answer the question.

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)

`\tag`+`\label`+`\eqref`

Source Link

edited Nov 25 at 17:44

LSpice

12.9k
4
45
69

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} \qquad (1)$$$$\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 (1)\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)

The computer found this.

Let $n$ be 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} \qquad (1)$$

Q1 Is (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)

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)

Source Link

asked Nov 25 at 15:46

joro

25.4k
10
66
121

Loading

Stack Exchange Network

Return to Question