Una conjetura sobre $\phi(n)$

Question

Dejemos que $\phi(n)$ denotan la función totiente de Euler de $n $ .
Entonces dejemos que $N$ sea un número tal que $\phi(N)$ divide $N$ . También deja que $I_1= \frac{N}{\phi(N)}$ que se define como el "Índice de belleza de segundo orden de $N$ ".

Entonces demuestre que - Para todo número $I_1$ existe un número $N$ tal que $I_1$ es el índice de belleza de segundo orden de $N$ .

Answer 1

Lo siento, pero la conjetura es realmente falsa: De hecho, no hay otros valores enteros para $N/\varphi(N)$ entonces $1,2,3$ . Razón:

La función $\varphi(N)$ es una función multiplicativa de la teoría de los números. Sea $N = \prod p_i^{k_i}$ con primos pares distintos $p_i$ dividiendo $N$ entonces $$\frac{N}{\varphi(N)} = \frac{\prod p_i^{k_i}}{\prod (p_i-1)p_i^{k_i-1}} = \frac{\prod p_i }{ \prod (p_i-1)}.$$

Ahora compara los factores primos del numerador y del denominador:

• Si $N$ es divisible por $3$ , entonces hay un $2$ en el denominador, cancelando la única $2$ en el numerador. Esto significa que no puede haber otro factor primo de $N$ que no sea $2,3$ . Así que $N/\varphi(N)=3$ es el único valor entero en este caso, obtenido por cualquier $N$ de la forma $2^k3^j$ .
• Supongamos que $N$ es divisible por un primo $>3$ y que $p$ sea el menor de dichos primos. Entonces hay $p-1$ en el denominador que debe ser cancelado por los primos en el numerador menores que $p$ . Pero como ya hemos descartado $3$ Sólo hay un único $2$ en el numerador que queda como posible factor de $p-1$ una contradicción.
• El único valor restante es $N/\varphi(N) = 1$ para $n=1$ y $N/\varphi(N) = 2$ para $N = 2^k$ .

---

EDITAR

Por cierto, ya que esto se discutió al lado: Aquí está mi recomendación para el cálculo de muchos valores de $\varphi(N)$ : utiliza tamices.

N = 10**8
BeautyIndex = set([1])
PHI = numpy.arange(N)

for i in xrange(2,N):
   if PHI[i]==i:#i is prime
     PHI[i::i]*=i-1
     PHI[i::i]/=i
   if i%PHI[i]==0:
     BeautyIndex.add(i)
print BeautyIndex

Answer 2

No es una respuesta, pero esto no funcionará como comentario. Aquí está el código solicitado para echar un vistazo de una manera lenta y de fuerza bruta en Python.

def totient(n):
  if n == 1: return 1
  return sum(d * mobius(n / d) for d in range(1, n+1) if n % d == 0)
def mobius(n):
  result, i = 1, 2
  while n >= i:
    if n % i == 0:
      n = n / i
        if n % i == 0:
          return 0
      result = -result
    i = i + 1
  return result

results = set() #sets store only unique items, so the output is cleaner

for n in range(1,[large number]):
  if float(n)/float(totient(n))==float(n/totient(n)): #integer check
    results.add(n/totient(n))

for item in results:
  print str(item) #shows what we got

Actualización: Hasta $100000$ obtenemos $\{1,2,3\}$ .