44
$\begingroup$

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!

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

5 Answers 5

35
$\begingroup$

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!

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

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

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

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

$\endgroup$
1
  • $\begingroup$ Yeah.... This was actually quite straightforward. Sorry. $\endgroup$ Dec 16, 2013 at 16:14
6
$\begingroup$

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:

$\endgroup$
1
  • 1
    $\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$ Jan 6, 2016 at 6:49
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You are assuming $j|n$ but if $n=7$, $p=7$ then $j=3$... $\endgroup$ Jun 16, 2013 at 10:26

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.