If $2^p-1$ is a prime, (thus $p$ is a prime, too) then $p\mid 2^p-2=\phi(2^p-1).$

But I find $n\mid \phi(2^n-1)$ is always hold, no matter what $n$ is. Such as $4\mid \phi(2^4-1)=8.$

If we denote $a_n=\dfrac{\phi(2^n-1)}{n}$, then $a_n$ is A011260, but how to prove it is always integer?

Thanks in advance!

  • 3
    $\begingroup$ :nice question $\color{green}{\large+1}$ $\endgroup$ – M.H Jun 24 '13 at 18:07

Consider $U(2^n-1)$. Clearly $2\in U(2^n-1)$. It can also be shown easily that the order of $2$ in the group $U(2^n-1)$ is $n$. By Lagrange's theorem $|2|=n$ divides $|U(2^n-1)|=\phi(2^n-1)$.

Remark: Thank you for letting me know about this fact. It's interesting!

  • 2
    $\begingroup$ An interesting answer! $\endgroup$ – Next Jun 15 '13 at 14:33
  • $\begingroup$ @Hecke Yes. I didnt expect to find a short proof at the beginning ! $\endgroup$ – Amr Jun 15 '13 at 14:33
  • 2
    $\begingroup$ You proved $n\mid \phi(a^n-1).$ $\endgroup$ – Next Jun 15 '13 at 14:35
  • $\begingroup$ @Hecke I already realized this !! $\endgroup$ – Amr Jun 15 '13 at 14:35

$(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$ is a group of order $\phi(a^n-1)$ and gcd$(a,a^n-1)=1\Rightarrow a\in (\mathbb{Z}/\mathbb{(a^n-1)Z})^*$

We have $a^n\equiv 1\mod (a^n-1)$ and $a^k-1<a^n-1$ when ever $k<n$ so there does not exist $k<n$ such that the above condition holds. So the order of $a$ in $(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$ is $n$. And as the order of each element divides the order of the group so we have $n|\phi(a^n-1)$

Putting $a=2$ we have the required result asked in the question.

  • $\begingroup$ Thanks,this is more detailed. $\endgroup$ – Next Jun 15 '13 at 14:37
  • $\begingroup$ @Abhra, this can be generalized to $n|\phi(a^n-1)$ for any integer $a$ $\endgroup$ – lab bhattacharjee Jun 15 '13 at 14:45
  • $\begingroup$ @labbhattacharjee I think i have already generalized it to all integers. $\endgroup$ – Abhra Abir Kundu Jun 15 '13 at 16:01
  • 1
    $\begingroup$ @AbhraAbirKundu, may be my comment & your edit were concurrent. Anyway, good job. $\endgroup$ – lab bhattacharjee Jun 15 '13 at 16:05

Hint: Clearly $2$ has order $n$, modulo $2^n-1$.

Further Hint: We know that $2^{ \phi(2^n -1)} \equiv 1 \pmod{2^n-1}$.

  • $\begingroup$ Yeah.... This was actually quite straightforward. Sorry. $\endgroup$ – Bob the Builds Dec 16 '13 at 16:14

I will use Lifting the Exponent Lemma(LTE).

Let $v_p(n)$ denote the highest exponent of $p$ in $n$.

Take some odd prime divisor of $n$, and call it $p$. Let $j$ be the order of $2$ modulo $p$.

So, $v_p(2^n-1)=v_p(2^j-1)+v_p(n/j)>v_p(n)$ as $j\le p-1$.

All the rest is easy. Indeed, let's pose $n=2^jm$ where $m$ is odd.

Then $\varphi\left(2^{2^jm}-1\right)=\varphi(2^m-1)\varphi(2^m+1)\varphi(2^{2m}+1)\cdots\varphi\left(2^{2^{j-1}}m+1\right)$. At least $2^j$ terms in the right side are even.

  • $\begingroup$ You are assuming $j|n$ but if $n=7$, $p=7$ then $j=3$... $\endgroup$ – punctured dusk Jun 16 '13 at 10:26

Observation. If $2^n-1\mid 2^k-1$ then $n \mid k$.

Proof. Let $2^n-1\mid 2^k-1$. Let $k=qn+r$ where $0\le r<n$. Then we get $$2^k-1=2^{qn+r}-1=2^{qn+r}-2^r+2^r-1=2^r(2^{qn}-1)+2^r-1.$$ Since $2^{qn}-1=(2^n-1)(2^{(q-1)n}+2^{(q-2)n}+\dots+2^n+1)$, we see that $2^n-1$ divides $2^{qn}-1$. Therefore $2^n-1$ also divides $$2^r-1 = 2^k-1 - 2^r(2^{qn}-1).$$ But $2^n-1 \mid 2^r-1$ with $0\le r<n$ is only possible if $r=0$. So we get that $k=qn$ and $n\mid k$.

From Euler's theorem we have $$2^{\varphi(2^n-1)}\equiv 1 \pmod{2^n-1},$$ i.e., $2^n-1 \mid 2^{\varphi(2^n-1)}-1$. (Notice that $\gcd(2,2^n-1)=1$, so Euler's theorem can be applied here.)

Using the above observation for $k=\varphi(2^n-1)$ we get $$n\mid \varphi(2^n-1).$$

Note: The same argument would work to show that $n\mid \varphi(a^n-1)$ for any $a\ge2$. Some posts about this more general question:

  • $\begingroup$ This is basically Calvin Lin's answer rewritten in a more elementary language. (His answer was originally posted here, but the two posts were merged.) $\endgroup$ – Martin Sleziak Jan 6 '16 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.