# Find other factors of the euler function of $2^k-1$ where $k\ge 2$ is an integer, except $2$.

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) ];

• $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$. Commented Apr 26, 2019 at 9:27
• If there were a formula, one could decide that a number is a Mersenne prime by $2^p-1=\varphi(2^p-1)+1$. Commented Apr 26, 2019 at 9:34
• The totient function $\varphi(n)$ can only be calculated if the factorization of $n$ is known. Commented Apr 26, 2019 at 9:36
• @egreg nice. what if $p$ is not a prime ? Commented Apr 26, 2019 at 9:36
• Euler totient is multiplicative
– user665856
Commented Apr 28, 2019 at 4:34

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$$.
• 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. Commented Apr 30, 2019 at 10:37