Probar $n\mid \phi(2^n-1)$

Question

Si 2 ^ $ p-1 es un primer, (así $p$ es un prime, también) entonces $p\mid 2^p-2=\phi(2^p-1). $

Pero encuentro que $n\mid \phi(2^n-1)$ se mantenga siempre, no importa qué $n$ es. Como \phi $4\mid (2 ^ 4 - 1) = 8. $

¿Si denotan $a_n=\dfrac{\phi(2^n-1)} {n}, $then $a_n$ es A011260 , pero cómo probar siempre es entero?

Gracias de antemano!

Answer 1

Considerar $U(2^n-1)$. Claramente $2\in U(2^n-1)$. Puede también ser demostrado fácilmente que el orden de $ 2 dólares en el grupo $U(2^n-1)$ es $ $n. Por el teorema de $|2| de Lagrange = n$ divide $| $ U(2^n-1)|=\phi(2^n-1).

Reamrk: Gracias por dejarme saber acerca de este hecho. Es interesante!

Answer 2

$(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$ es un grupo de orden $\phi(a^n-1)$ y mcd$(a,a^n-1)=1\Rightarrow\(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$

Tenemos $a^n\equiv 1\mod (a^n-1)$ y $a^k-1<^n-1$ cuando $k<n$ de modo que no existe $k<n$ que la condición anterior se mantiene. De modo que el orden de $un$ en $(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$ es $n$. Y como el orden de cada elemento que divide al orden del grupo, de modo que tenemos $n|\phi(a^n-1)$

Poner $a=2$ tenemos el resultado requerido se le preguntó en la pregunta.

Answer 3

Voy a utilizar Levantar el Exponente Lema(LTE).

Deje de $v_p(n)$ denotar el exponente más alto de $p$ en $n$.

Tomar alguna extraña divisor primo de $n$, nombre que $p$. Vamos $j$ ser del orden de us $2$ modulo $p$.

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

Resto es fácil. Decir $n=2^jm$ donde $m$ es impar.

Entonces $\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)$. Al menos $2^j$ términos en el lado derecho están incluso.