0
$\begingroup$

Euler function of $x$ is denoted by $\varphi(x)$, which is defined in here (https://en.wikipedia.org/wiki/Euler%27s_totient_function ).

When $k$ is prime. @egreg comments that there does not exist a formula to obtain $\varphi(2^k-1)$. @Dietrich Burde comments that there need not be other factors of $\varphi(2^k-1)$ different from $2$ and $k$. However, if $k$ is not prime, it seems that finding factors of $\varphi(2^k-1)$ is not obvious.

  1. Motivation ($k$ is prime.) Let $n=2^k-1$, where $k$ is prime. In $\mathbb{Z}_{n}$, the group $G=\langle 2 \rangle$ is of order $k$. Since the order of the multiplicative group $$\mathbb{Z}_{n}^*=\{ x \in \mathbb{Z}_{n} \mid \gcd(x,n)=1\}$$ is $\varphi(n)$, it should have $$k \mid \varphi(2^k-1).$$

    Proposition 1: If $k$ is prime, then $2 \mid \varphi(2^k-1)$ and $k \mid \varphi(2^k-1)$.

  2. Problem

    Find other factors of $\varphi(2^k-1)$ where $k\ge 2$ is an integer, except $2$. Or proof some conjectures below.

3.My trying($k$ is not prime.)

[ <k, EulerPhi(2^k-1)> : k in [2..200] | (EulerPhi(2^k-1) mod 2 ne 0) or ( EulerPhi(2^k-1) mod k ne 0) ];

By the above magma program, it seems that $2$ and $k$ are two factors of $\varphi(2^k-1)$ for $2\le k \le 200$.

Proposition 2: $2 \mid \varphi(2^k-1)$ for $k\ge 2$.

Proof. Note that $2^k-1$ is odd. It follows that $\varphi(2^k-1)$ is even. QED.

For $k$ is not prime, it only has $2^k\equiv 1 \pmod{2^k-1}$ which is not sufficient to show that the group $G=\langle 2 \rangle$ is of order $k$.

conjecture 1: $k \mid \varphi(2^k-1)$ for $k\ge 2$.

Moreover, by the following magma program, it conjectures that $3\mid \varphi(2^k-1)$ if $5 \mid k$ or $7 \mid k$. It would be better if the sufficient and necessary condition of $3 \mid \varphi(2^k-1)$ can be given.

conjecture 2: $3\mid \varphi(2^k-1)$ if $5 \mid k$ or $7 \mid k$.

[ <k, Factorization(EulerPhi(2^k-1))> : k in [5..500 by 5] | (EulerPhi(2^k-1) mod 2 ne 0) or ( EulerPhi(2^k-1) mod 3 ne 0) ];
[ <k, Factorization(EulerPhi(2^k-1))> : k in [7..210 by 7] | (EulerPhi(2^k-1) mod 2 ne 0) or ( EulerPhi(2^k-1) mod 3 ne 0) ];
$\endgroup$
8
  • 1
    $\begingroup$ $p=11$ shows that there need not be other factors of $\phi(2^p-1)$, different from $2$ and $p$. We have $\phi(2^{11}-1)=2^4\cdot 11^2$. $\endgroup$ Commented Apr 26, 2019 at 9:27
  • 3
    $\begingroup$ If there were a formula, one could decide that a number is a Mersenne prime by $2^p-1=\varphi(2^p-1)+1$. $\endgroup$
    – egreg
    Commented Apr 26, 2019 at 9:34
  • $\begingroup$ The totient function $\varphi(n)$ can only be calculated if the factorization of $n$ is known. $\endgroup$
    – Peter
    Commented Apr 26, 2019 at 9:36
  • $\begingroup$ @egreg nice. what if $p$ is not a prime ? $\endgroup$ Commented Apr 26, 2019 at 9:36
  • $\begingroup$ Euler totient is multiplicative $\endgroup$
    – user665856
    Commented Apr 28, 2019 at 4:34

1 Answer 1

1
+50
$\begingroup$

Conjecture 3 is clearly true, and here is a generalization: if $d \mid k$ and $2^d-1$ is a Mersenne prime, then $2^d - 2$ divides $\varphi(2^k -1)$.

Proof: if $d \mid k$ then there exists $l \in \mathbb N$ such that $k = dl$, therefore

$$\varphi(2^k - 1) = \varphi \left( (2^d)^l - 1 \right) = \varphi \left( (2^d - 1) \sum_{i=0} ^{l-1} (2^d)^i \right) = \varphi(2^d - 1) \ \varphi \left( \sum_{i=0} ^{l-1} 2^{di} \right) = (2^d - 2) \ \varphi \left( \sum_{i=0} ^{l-1} 2^{di} \right) \ .$$

Now, notice that if $d \in \{5,7\}$ then $2^d - 2 \in \{30,126\}$, and these numbers are both divisible by $3$.

$\endgroup$
2
  • 1
    $\begingroup$ There is a typos. In fact it is Conjecture 2, not 3. Anyway, it is a positive result. I think the key point is to assume that $2^d-1$ is prime which leads to $\gcd(2^d-1, \sum_{i=0}^{l-1}{2^{di}})=1$. I was stuck in there for a long time. Thanks. $\endgroup$ Commented Apr 30, 2019 at 10:37
  • $\begingroup$ You are right, it should have been conjecture 2, but I am not going to edit my post for such a small correction anymore. $\endgroup$
    – Alex M.
    Commented Apr 30, 2019 at 10:39

You must log in to answer this question.

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