Una posible Propiedad de Euler totient función: $n$ tal que $\varphi(n)$ $\varphi(n+1)$ ambos son potencias de dos

Question

$n$ es un entero positivo impar tal que $\varphi(n)$ $\varphi(n+1)$ ambos son potencias de dos . Aquí , $\varphi(n)$ denota Euler totient función.

Es cierto que $(n+1)$ es $6$ o un poder de $2$?

Por favor me ayudan a demostrar o refutar esta afirmación . (Se me fue al azar hojeando algunos de los valores alcanzados por la $\varphi$ función cuando he observado este patrón) :)

Answer 1

Hay exactamente siete enteros positivos impares $n$ tal que

$\varphi(n)$ $\varphi(n+1)$ ambos son potencias de dos.

Estos son: $$ n = 1, 3, 5, 15, 255, 65535, 4294967295. $$ Escrito más amablemente: \begin{align*} 5&\; \\ 1&= 2^{2^0} - 1 \\ 3&= 2^{2^1} - 1 = 3\\ 15 &= 2^{2^2} - 1 = 3 \cdot 5 \\ 255 &= 2^{2^3} - 1 = 3 \cdot 5 \cdot 17 \\ 65535 &= 2^{2^4} - 1 = 3 \cdot 5 \cdot 17 \cdot 257 \\ 4294967295 &= 2^{2^5} - 1 = 3 \cdot 5 \cdot 17 \cdot 257 \cdot 65537. \end{align*} En particular, su conjetura es verdadera: cualquiera de las $n+1 = 6$ o $n+1$ es una potencia de dos. Específicamente, $n+1$ es $6$ o igual a$2^{2^k}$$k \in \{0,1,2,3,4,5\}$.

Usted puede reconocer a $3, 5, 17, 257, 65537$ como el conocido de los números primos de Fermat. La razón por la que no hay mayor $n$ es que en el próximo número de Fermat, $4294967297$, es famosa por su compuesto y es igual a $641 \cdot 6700417$. (Aunque Fermat conjeturó que todos los números de Fermat son los principales, a excepción de la primera de cinco que ningún otro de los números primos de Fermat son conocidos, y algunos han conjeturado que no hay otros. Ver, por ejemplo, este oeis entrada.)

---

Prueba

En primer lugar, se demuestra que para un entero positivo $m$, $\varphi(m)$ es una potencia de dos, si y sólo si $m$ es una potencia de dos veces un producto de cero o más números primos de Fermat, es decir, de los números primos de la forma $2^{2^a} + 1$. (El mismo se encuentra en Matemático 42 de la respuesta.) Suponga que $\varphi(m)$ es una potencia de dos. Si $m$ es divisible por el cuadrado de cualquier prime $p$,$p \mid \varphi(m)$$p = 2$. Por lo tanto, $m$ es una potencia de dos ocasiones distintas impares primos $p_1 < p_2 < \cdots < p_i$: $$ m = 2^x p_1 p_2 \cdots p_i $$ Por lo tanto, $$ \varphi(m) = 2^{x-1} (p_1 - 1) (p_2 - 1) \cdots (p_i - 1), $$ y de ello se deduce que cada una de las $p_i$ debe ser una potencia de dos más 1. Y los únicos números primos de la forma $2^k + 1$ son de la forma $2^{2^k} + 1$ (de los números primos de Fermat); una rápida prueba se puede encontrar en esta sección de la página de la Wikipedia. Por lo $p_i$ es una de Fermat prime. Por el contrario, cualquier $m$ de esta forma se ha $\varphi(m)$ ser una potencia de dos.

De vuelta al problema, entonces, estamos mirando para todos los enteros positivos impares $n$ tal que $n, n+1$ son tanto una potencia de dos tiempos de un producto de números primos de Fermat. Como $n$ es impar, $n$ debe ser un producto de números primos de Fermat, y $n+1$ debe ser una potencia de dos tiempos de un producto. Para reducir a sólo siete posibles $n$, vamos a explotar el hecho de que un producto de números primos de Fermat tiene un muy, muy estructurado binario de expansión.

Vamos $$ n = \prod_{i=1}^l (2^{2^{a_i}} + 1), $$ donde $0 \le a_1 < a_2 < \cdots < a_l$ y cada término del producto es primo. Expandiendo el producto, tenemos que $$ n = \sum_{S \subseteq \{1,2,3,\ldots, l\}} 2^{\displaystyle \left( \sum_{i \in S} 2^{a_i} \right)} $$ Lo que esta de miedo fórmula está diciendo es que: $n$ es la suma de $2^l$ distintas potencias de dos, y los exponentes de las potencias de dos son todas las posibles sumas de $2^{a_1}, 2^{a_2}, \ldots, 2^{a_l}$. Pensando en binario:

• $n$ $2^l$ dígitos;

• $n$ es impar, por lo que el último dígito es también una $1$.

• Y, sobre todo, si $l \ge 1$ $n$ se compone de dos bloques idénticos: dígitos $0$ a través de $2^{a_l} - 1$ $2^{a_l}$ a través de $2^{a_l+1}$ son los mismos. El bloque puede comenzar con algunos $0$s. (Dentro de cada uno de los dos bloques que, a continuación, tener dos o más bloques idénticos, y así sucesivamente, pero no puede ser ceros acolchado en cada paso. Ejemplo: $(2^{2^0} + 1)(2^{2^1}+1)(2^{2^3}+1) = 3 \cdot 5 \cdot 257$ $111100001111$ en binario. Los dos bloques idénticos se $00001111$$00001111$. Cada bloque consta de dos bloques idénticos $11$$11$, aunque cuatro de $0$s son acolchado en la parte delantera. Luego cada una de esas consta de dos bloques idénticos $1$$1$.)

Por el mismo razonamiento, $n+1$ debe ser una potencia de dos veces un número que se ve exactamente la misma. Podemos decir que para algunos $r,m$ y $0 \le b_1 < b_2 < \ldots < b_m$, $n+1$ es igual a $2^r$ veces el producto de $2^{2^{b_i}} + 1$, y luego:

• $n+1$ $2^m$ dígitos;

• $\frac{n+1}{2^r}$ se compone de dos bloques idénticos: dígitos $0$ a través de $2^{b_m} - 1$ $2^{b_m}$ a través de $2^{b_m + 1}$ son los mismos. (Dentro de cada uno de los dos bloques que, a continuación, tener dos o más bloques idénticos, y así sucesivamente.)

Para formar $n+1$$n$, añadimos $1$ a los binarios de expansión, por lo que el número de $1$s disminuye por $(c-1)$ donde $c$ es el número de $1$s al final de los binarios de expansión de $n$. Como $n$$2^l$, $n+1$$2^l - (c-1)$. Ya que esta tiene que ser una potencia de dos, debemos tener $c = 1$ o $c \ge 2^{l-1}+1$. En el primer caso, vamos a mostrar que el $n$ debe ser igual a $5$. En la última, que $n$ debe ser igual a $2^{2^l} - 1$.

Caso 1: $c = 1$

Desde $c = 1$, $n$ ha $01$ al final de su binario de expansión. Por lo $n+1$ tiene el mismo binario de expansión con $01$ reemplazado por $10$, e $r = 1$ (número de dos en dos, dividiendo $n+1$). Mirando el $1$s en $n+1$, podemos extraer exactamente los números de $b_i$: $2^i$th 1 de la derecha, si empezamos a contar desde 0, se encuentra en la posición $2^{b_i} + 1$ (cuando las posiciones empiezan a contar desde $0$ como bueno, es decir, el $k$th posición es la $2^k$s dígitos). Pero también está en la posición $2^{a_i}$. De ello se deduce que sólo $a_i = 1$ es posible, y $l = 1, m = 1$, $n = 2^{2^1} + 1 = 5$, $n+1 = 6 = 2 \cdot 3$.

Caso 2: $c \ge 2^{l-1} + 1$

Aquí, $n$ debe tener al menos $2^{l-1} + 1$ consecutivas en el derecho. Pero $n$ se compone de dos bloques idénticos, cada uno conteniendo $2^{l-1}$. Por lo que no debe ser ningún cero en cada bloque: $n$ debe ser una cadena de $2^{l}$ consecutivas. Que es, exactamente, $$ n = 2^{2^l} - 1. $$ Ahora, este tipo de factores como $$ n = (2^{2^0} + 1) (2^{2^1} + 1) (2^{2^2} + 1) \cdots (2^{2^{l-1}} + 1). $$ Para $l \le 5$, todos estos factores son el primer y tenemos una verdadera solución.

Pero para $l \ge 6$, el factor de $(2^{2^{5}} + 1)$ está presente, y los factores en $641 \cdot 6700417$, lo que hace que $\varphi(n)$ divisible por $640$ y por lo tanto no es una potencia de dos.

Answer 2

Esta no es una respuesta, pero puede ser útil cuando alguien más inteligente que yo intenta demostrar esto.

Escribir $n=\prod_{i}p_i^{n_i}$$n+1=\prod_{i}(p_i')^{m_i}$. A continuación, $\phi(n)=\prod_{i} p_i^{n_i-1}(p_i-1)$ ser una potencia de dos que implica que si $p_i\neq 2$, $n_i=1$ $(p_i-1)$ es una potencia de dos. Lo mismo vale para los $\phi(n+1)$.

Deje $I$ ser una enumeración de los números primos tales que el primer número menos uno es una potencia de dos, es decir, $0$ corresponde a $2$, $1$ corresponde a $5$, $2$ corresponde a $17$ y así sucesivamente. Entonces $$n=2^{n_0}\prod_{i\in I, i\geq 1}p_i^{n_i}$$ where $n_i\en \left\{0,1\right\}$ and $$n+1=2^{m_0}\prod_{i\in I,i\geq 1}p_i^{m_i}$$ donde $m_i\in \left\{0,1\right\}$. Aquí $p_i$ indica el $i$-ésimo número primo tal que $p_i-1$ es una potencia de $2$ (y nos empiezan a contar desde cero). De esto podemos conseguir que $$2^{n_0}\prod_{i\in I, i\geq 1}p_i^{n_i}+1=2^{m_0}\prod_{i\in I, i\geq 1}p_i^{m_i}.$$

A partir de esta ecuación, debemos ser capaces de encontrar algo que, sin embargo, yo no sé si el conjunto de índices $I$ es finito o no, la realización de nuevas manipulaciones difíciles.