47
$\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
  • 4
    $\begingroup$ :nice question $\color{green}{\large+1}$ $\endgroup$
    – M.H
    Commented Jun 24, 2013 at 18:07

5 Answers 5

37
$\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
  • 3
    $\begingroup$ An interesting answer! $\endgroup$
    – lsr314
    Commented Jun 15, 2013 at 14:33
  • $\begingroup$ @Hecke Yes. I didnt expect to find a short proof at the beginning ! $\endgroup$
    – Amr
    Commented Jun 15, 2013 at 14:33
  • 6
    $\begingroup$ You proved $n\mid \phi(a^n-1).$ $\endgroup$
    – lsr314
    Commented Jun 15, 2013 at 14:35
  • $\begingroup$ @Hecke I already realized this !! $\endgroup$
    – Amr
    Commented Jun 15, 2013 at 14:35
15
$\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
    Commented Jun 15, 2013 at 14:37
  • $\begingroup$ @Abhra, this can be generalized to $n|\phi(a^n-1)$ for any integer $a$ $\endgroup$ Commented Jun 15, 2013 at 14:45
  • $\begingroup$ @labbhattacharjee I think i have already generalized it to all integers. $\endgroup$ Commented Jun 15, 2013 at 16:01
  • 1
    $\begingroup$ @AbhraAbirKundu, may be my comment & your edit were concurrent. Anyway, good job. $\endgroup$ Commented Jun 15, 2013 at 16:05
11
$\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$ Commented Dec 16, 2013 at 16:14
9
$\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$ Commented 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$ Commented Jun 16, 2013 at 10:26

You must log in to answer this question.

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