¿Cómo encontrar todos los enteros n positivos tales φ(n) /n?

Interesante pregunta, como todas las que rodean a la misteriosa función indicador, la función φ de Euler. De hecho, en relación con esta función hay varios problemas abiertos.

[Entiendo que se trata aquí de la función de Euler, fundamental en teoría de números; pero no estaría de más aclararlo en la redacción de la pregunta, ya que la letra griega φ puede representar también a otras funciones].

La barra inclinada parece más un signo de división: para indicar que φ(n) es un divisor de n o en otras palabras, que φ(n) divide a n, es más usada la barra vertical: φ(n) | n.

Bien, empezando por los primeros valores, sabemos que:

φ(1) = 1, de modo que para n = 1 es cierta la afirmación φ(n) | n.

φ(2) = 1 , y en efecto, 1 | 2.

A partir de n ≥ 3 sabemos que φ(n) es siempre par, de modo que los valores impares de n no pueden ser divisibles por el número par φ(n).

Cuando n ≥ 3, φ(n) solo puede tomar valores pares.

Sea entonces n par, n ≥ 4.

Si n es potencia de 2 → n = 2^t, con t entero positivo → φ (n) = 2^t (1 - 1/2) = 2^(t-1) y ciertamente se verifica que φ(n) | n.

Así pues, todas las potencias de 2 cumplen la condición del problema, incluido el caso

n = 2° = 1.

Ahora supongamos n par, n ≥ 4, y n no es potencia de 2, así que además de divisible por 2 también es divisible por algún número primo impar.

Supongamos que n cumple la condición del problema → φ(n) | n .

Sabemos que si la descomposición de n en factores primos es:

n = 2^m * p₁^r₁ * p₂^r₂ * … * pₖ^rₖ,

donde m ≥ 1, y los factores primos distintos p₁, p₂, … , pₖ (k ≥ 1) todos impares.

Los exponentes r₁, r₂, … ,rₖ son enteros positivos; entonces, por la fórmula de Euler,

φ(n) = n * (1 - 1/2) (1 - 1/ p₁) (1 - 1/ p₂) …(1 - 1 / pₖ), o bien,

φ(n) = 2^(m - 1) * [p₁^r₁ - p₁^(r₁ - 1) ] [p₂^r₂ - p₂^(r₂ - 1)] … [pₖ^rₖ - pₖ^(rₖ - 1) ] =

= 2^(m - 1) * p₁^(r₁ - 1) * p₂^(r₂ - 1) * …* pₖ^(rₖ - 1) * (p₁ - 1) (p₂ - 1) …(pₖ - 1),

y esto, por la hipótesis asumida, divide a

2^m * p₁^r₁ * p₂^r₂ * … * pₖ^rₖ .

Cuando, en general, siendo A, B y D enteros positivos cualesquiera, se cumple

(A * D) | (B * D) → B * D = A * D * t (con t entero positivo) → simplificando por D:

B = At → A | B ; o sea, en una relación de divisibilidad como (AD) | (BD), se pueden dividir ambos números entre cualquier divisor común; en este caso, se deduce que A | B.

Como φ(n) | n (por hipótesis), era cierto que

2^(m - 1) * p₁^(r₁ - 1) * p₂^(r₂ - 1) * …* pₖ^(rₖ - 1) (p₁ - 1) (p₂ - 1) …(pₖ - 1) divide a

2^m * p₁^r₁ * p₂^r₂ * … * pₖ^rₖ →

podemos simplificar, usando la propiedad anterior, dividiendo ambos enteros por su divisor común (o factor común) 2^(m - 1) * p₁^(r₁ - 1) * p₂^(r₂ - 1) * …* pₖ^(rₖ - 1) → resultaría

(p₁ - 1) (p₂ - 1) …(pₖ - 1)|2 * p₁ p₂ … pₖ.

Pero como todos los primos p₁, p₂, … , pₖ son impares, será (p₁ - 1) (p₂ - 1) …(pₖ - 1) múltiplo de 2^k, puesto que todos los paréntesis serían pares; si fuera k ≥ 2, esto es, si de esos primos impares hubiera dos o más, tendríamos que 2^k | 2, con k ≥ 2, ¡CONTRADICCIÓN!

De manera que solo puede ser k = 1, y así, en principio, solo podría haber un primo impar p₁.

n sería de la forma n = 2^m * p₁^r₁ y se tendría la relación de divisibilidad:

(p₁ - 1) | 2 * p₁ ; si (p₁ - 1) tuviera algún divisor primo impar ( > 2) , al dividir a 2 * p₁ y ser primo con 2, tal divisor debería dividir al otro factor (p₁), pero en este caso, por ser primo p₁, sus únicos posible divisores son 1 y p₁ ; descartamos p₁ puesto que todo divisor de (p₁ - 1) debe ser menor que p₁, luego quedaría tan solo la posibilidad de que tal divisor primo impar (>2) fuera el 1 → de cualquier manera se llega a CONTRADICCIÓN.

Esto prueba que la suposición de que (p₁ - 1) tuviera algún divisor primo impar ( > 2) es FALSA.

Ahora bien, si (p₁ - 1) no tiene ningún divisor impar, será potencia de 2 →

p₁ - 1 = 2^s (para cierto entero positivo s) → p₁ = 2^s + 1. Sin embargo, si s contiene algún divisor impar mayor que 1 esto también conduce a contradicción, puesto que si s es entero positivo tal que s = td, con d impar > 1 → 2^s + 1 = (2^t)^d + 1 es múltiplo de 2^t + 1, como demuestra la familiar identidad algebraica:

A^d + 1 = (A + 1) [ A^(d - 1) + A^(d - 2) + … + 1 ], válida para todo exponente d impar

y para todo A real o complejo; tomando A = 2^t resulta probado lo que se afirmaba en el párrafo anterior, puesto que todos los términos se vuelven enteros positivos, y es forzoso que s no admita factores impares, por lo cual s es potencia de 2 →

s = 2^h (h entero no negativo)

Luego debe verificarse que

n = 2^m * p₁^r₁ = 2^m * [ 2^ (2^h) + 1 ]^r₁, siendo 2^ (2^h) + 1 primo.

Como es sabido, los números primos de la forma 2^ (2^h) + 1 (h ≥ 0) se llaman números primos de Fermat.

Son la clave para encontrar todos los polígonos regulares que pueden dibujarse exactamente con solo regla y compás (problema planteado por los antiguos griegos, y aún todavía abierto: hasta el día de hoy solo se conocen cinco (para h = 0, 1, 2, 3, 4).

La función φ de Euler está rodeada de un notable halo de misterio: yace en el fondo de muchos problemas aún sin resolver en teoría de números.

Gauss demostró que un polígono regular convexo de n lados (n > 2) se puede dibujar con solo regla y compás si y solo si φ(n) es una potencia de 2.

El problema es que todavía no se sabe cuántos n cumplen esa condición, porque se topa enseguida con los números primos de Fermat, de los que se ignora si hay o no más de cinco de ellos.

En el presente problema hemos probado que si φ(n) | n (siendo n > 2) entonces necesariamente

n es de la forma n = 2^m * [ 2^ (2^h) + 1 ]^r₁,

siendo 2^ (2^h) + 1 un número primo de Fermat. Designémoslo por F(h) = 2^ (2^h) + 1.

Así, n = 2^m * F(h)^r₁ .

Por tanto, φ(n) = n * (1–1/2) * [1 - 1/F(h)] = 2^(m - 1) * [ F(h)^r₁ - F(h)^(r₁ - 1)] =

= 2^(m - 1) * F(h)^(r₁ - 1) [F(h) - 1] = 2^(m - 1) * 2^ (2^h) * F(h)^(r₁ - 1) =

= 2^[2^h + m - 1 ] * F(h)^(r₁ - 1) .

Como debe cumplirse, por hipótesis, que

φ(n) | n → 2^[2^h + m - 1 ] | [ 2^m * F(h)^r₁ ].

Sin embargo, F(h) es impar, así como toda potencia suya, de modo que ha de verificarse:

2^[2^h + m - 1 ] | 2^m ; pero eso implica que el exponente de la base 2 en el primer miembro sea menor o igual que el exponente de la base 2 en el segundo miembro →

2^h + m - 1 ≤ m → 2^h ≤ 1 = 2ª → h ≤ 0, junto con la evidente desigualdad, asumida desde el principio, h ≥ 0, nos da la única posibilidad

→ h = 0 → n = 2^m * [ 2^ (2^h) + 1 ]^r₁ = 2^m * 3^r₁ . El único número primo de Fermat que podría - en principio - presentarse es, pues, el 3. Hemos demostrado así la

CONDICIÓN NECESARIA :

Si φ(n) | n → n es de la forma n = 2^m * 3^r₁, con m y r₁ enteros positivos.

Recordemos, de paso, que la función aritmética φ es multiplicativa, esto es, si a y b son enteros positivos primos entre sí, se tiene φ(ab) = φ(a) φ(b) (hay varias demostraciones sencillas, aunque no triviales, y al menos una se puede hallar en cualquier texto de teoría elemental de números).

Luego será φ(n) = φ(2^m * 3^r₁) = φ(2^m) φ(3^r₁) = 2^m * 3^r₁ * (1 - 1/2) * (1 - 1/3) =

= (1/3) * 2^m * 3^r₁ = 2^m * 3^(r₁ - 1) ; y efectivamente, φ(n) | n = 2^m * 3^r₁, puesto que

n / φ(n) = 3 → n = 3 φ(n) → φ(n) | n, c.q.d

Esto prueba la recíproca, esto es:

CONDICIÓN SUFICIENTE: Si n es par, n ≥ 4, y n no es potencia de 2, siendo n de la forma

n = 2^m * 3^r₁, con m y r₁ enteros positivos, se verifica que

φ(n) | n, o sea, φ(n) es divisor de n.

Como solo vamos a usar el exponente r₁, por comodidad podemos suprimir el subíndice, y escribir tan solo r.

SOLUCIÓN DEL PROBLEMA:

La condición necesaria y suficiente para que el entero positivo n cumpla la propiedad

φ(n) | n es que sea n = 1 o bien que n sea de la forma n = 2^m * 3^r,

siendo m entero positivo y r entero no negativo.

(r = 0 corresponde al caso, válido, en que sea n una potencia de 2, mayor que 2⁰ = 1).

Ejemplo: con m = 3, r = 4 → n = 2^3 * 3^4 = 8 * 81 = 648.

φ (648) = 648 * (1 - 1/2) * (1 - 1/3) = 648 * 1/2 * 2/3 = 648 * 1/3 = 216, divisor de n = 648.

COROLARIO: Si c es un entero positivo, tal que existe n, entero positivo, que cumpla

n = c * φ(n) → solo puede ser c = 1 (única solución, n = 1), o bien,

c = 2 (soluciones → n = potencia de 2 de exponente entero positivo) o, por último,

c = 3 (cuando n sea de la forma n = 2^m * 3^r, siendo m y r enteros positivos).

Para cualquier otro valor de c (o sea, c > 3)

no existe ningún entero positivo n tal que n = c * φ(n).