Encontrar el número máximo con un determinado valor de Euler

Question

La función totient de Euler tiene un límite inferior para valores grandes, pero ¿hay alguna forma de elegir máximos para valores específicos de la función?

Es decir, ¿cómo encontraría el número máximo n tal que phi (n) = 1000, por ejemplo?

Answer 1

Esto podría ser un problema difícil, en general, pero echemos un vistazo a 1000.

$n$ no puede ser impar, ya que tendríamos $2n\gt n$$\phi(2n)=\phi(n)$. Deje $n=2m$.

$m$ no puede tener más de 3 distintos factores primos, ya que obligaría a $\phi(n)$ a ser divisible por $2^4$, que no lo es.

Si $p$ es el primer y $p^2$ divide $n$ $p$ divide $\phi(n)$ $p$ es de 2 o 5.

Ahora usted puede comenzar a loking en los números de $2^r5^s$ $r=1,2,3$ $s=0,1,2,3$ para ver cuáles son las $\phi(p)$ para algunos prime $p$ (distinto de 2 y 5, la cual puede ser tratada por separado). Así, por ejemplo,, $\phi(11)=10$, $\phi(101)=100$, $\phi(41)=40$, y así sucesivamente. Una vez que usted tiene el conjunto (finito) de la lista, usted puede probar las formas de elaboración de los productos de estos números (y potencias de 2 y/o 5) ver cómo llegar $\phi(n)=1000$ y de qué manera se maximiza $n$.

Es un poco ad hoc, pero no estoy seguro de que puede ser ayudado.

Answer 2

Combinando el Teorema 329 en Hardy y Wright con el límite superior en$\sigma(n)$ en Robin (1984), obtenemos$$ \phi(n) > \frac{6 n \log \log n}{\pi^2 \left( e^\gamma (\log \log n)^2 + 0.6482 \right)},$$ where $ \ gamma = 0.5772156649 ...$ is the Euler-Masceroni constant.

As a result, $ \ phi ( n)> 1000$ unless $ n \ leq 6872.$

I'm just saying.

1111 = 11 * 101  phi =  1000 = 2^3 * 5^3
1255 = 5 * 251  phi =  1000 = 2^3 * 5^3
1375 = 5^3 * 11  phi =  1000 = 2^3 * 5^3
1875 = 3 * 5^4  phi =  1000 = 2^3 * 5^3
2008 = 2^3 * 251  phi =  1000 = 2^3 * 5^3
2222 = 2 * 11 * 101  phi =  1000 = 2^3 * 5^3
2500 = 2^2 * 5^4  phi =  1000 = 2^3 * 5^3
2510 = 2 * 5 * 251  phi =  1000 = 2^3 * 5^3
2750 = 2 * 5^3 * 11  phi =  1000 = 2^3 * 5^3
3012 = 2^2 * 3 * 251  phi =  1000 = 2^3 * 5^3
3750 = 2 * 3 * 5^4  phi =  1000 = 2^3 * 5^3
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

One thing I noticed after the fact is that 41 does not appear. This is as it should be. For 2 and powers of 2, we have $ \ phi (2 ^ {k +1} = 2 ^ k.$ However, for any odd prime $ p$ such as 5, it is not possible to have any $ \ phi (n) = p$ or $ \ phi (n) = p ^ 2$ or, in general, $ \ phi (n) = p ^ k.$ In particular it is impossible to have $ \ phi (n) = 25.$ As a result, if $ \ phi (n) = 1000,$ it is impossible to have $ 41 | n.$ Oh, any prime dividing this $ n$ must have $ (p-1) | 1000,$ and if the exponent is going to be larger than 1 we also need $ p | 1000.$ So, with 41, the exponent is 1, and we then need to find some relatively prime $ m $ with $ \ phi (m) = 25, $ imposible.