Phi de Euler de la función y las competencias de los dos

Question

Para valores pequeños de n$\ge$1 parece que uno tiene la desigualdad

$\phi(2^n)$ $\le$ $\phi(2^n + 1)$.

Sin embargo, parece poco probable que esto sirva para todo n .

Pregunta: ¿hay alguna explícita los valores de n conocido por que la desigualdad es violado ?

Gracias

Answer 1

Marca Bennet me inspiró, así que gracias de antemano y un (+1) como un homenaje.

Podemos recopilar un gran número de números primos de la forma $8k+3$, decir $p_1,\ldots,p_N$.

$\frac{p_k-1}{2}$ es impar y por la reciprocidad cuadrática, $\left(\frac{2}{p_k}\right)=-1$, por lo que si tomamos: $$ n=\prod_{k=1}^{N}\frac{p_k-1}{2}\tag{1} $$ tenemos: $$ 2^n+1 \equiv \left(2^{\frac{p_k-1}{2}}\right)^d+1 \equiv (-1)^d+1\equiv 0\pmod{p_k}\tag{2}$$ y cada una de las $p_k$ divide $2^n+1$. Desde $$ \sum_{p\equiv 3\pmod{8}}\frac{1}{p}\tag{3} $$ es una divergente de la serie, $$ \prod_{p\equiv 3\pmod{8}}\left(1-\frac{1}{p}\right) = 0,\tag{4} $$ por lo que la desigualdad se produce un error por infinidad de $n$s.

Gracias a Thomas Andrews, también tenemos una explícita contra-ejemplo: $$\prod_{\substack{p\equiv 3\!\!\pmod{\!\!8}\\p\leq 467}}\!\!\frac{p-1}{2}=118,036,297,108,708,732,142,419,220,832,488,800,078,125.$$

Marca Bennet le da una forma más pequeña contra-ejemplo: $$ n=3^4⋅5^2⋅7⋅11⋅13⋅17⋅23⋅29⋅41⋅53=49,945,180,460,175.$$

Answer 2

Para cada factor primordial $p|2^n+1$ consigue una reducción de $\frac {p-1}P$ $\varphi$ función. El $p$ que usted está buscando son aquellos para los cuales $2^n\equiv -1 \bmod p$. Luego de impar $k$, $2^{kn}\equiv -1 \bmod p$. Así que si trabajamos con exponentes impares podemos recoger de los números primos - la pregunta es ¿podemos recoger lo suficientemente pequeños números primos.

Ahora tenemos $2^1\equiv -1\bmod 3, 2^5\equiv -1 \bmod 11, 2^7\equiv -1 \bmod 43$ y la lista de poderes y los primos continúa $(1:3), (5:11), (7:43), (9:19), (11:683), (13:2731), (15:331)$ -, para ellos, el factor relevante es aproximadamente $0.5581$ y la necesitamos por debajo de $0.5$

No hay duda de que alguien puede buscar de manera más eficiente de lo que yo puedo ofrecer una conclusión definitiva.