¿Cómo encontrar todos los enteros n para los cuales φ(n) =d(n)?

La ecuación propuesta es una igualdad entre funciones aritméticas.

Entiendo que d(n) se refiere al número de divisores enteros y positivos del entero positivo n ;

sin embargo, aunque a veces se denota como d(n), para esta función, que cuenta el número de divisores enteros y positivos, está más extendida la notación τ(n) (la función tau, denotada con esa letra griega).

Supongamos por tanto que d(n) = τ(n), esto es, que se trata de la misma función "contador de divisores" de un entero positivo.

Como es sabido, la función φ de Euler es también un "contador", llamado a veces indicador, totalizador o totient: cuenta el número de enteros positivos menores o iguales que n que son primos con n, esto es, que no tienen ningún factor en común con n. O dicho de otra forma,

φ(n) es el número de fracciones irreducibles en la lista { 1/n, 2/n, …(n-1) / n }

Se adopta el valor φ(1) = 1 (por definición).

Para el cálculo explícito de los valores numéricos de la función φ tenemos la

Fórmula de Euler :

Si la descomposición en factores primos del entero positivo n > 1 es

n = p₁^r₁ * p₂^r₂ * … * pₖ^rₖ , se verifica: φ(n) = n (1 - 1/p₁) (1 - 1/p₂) … (1 - 1/ pₖ).

En particular, para todo p primo es φ(p) = p - 1 .

Para la función aritmética d(n) (número de divisores, enteros y positivos, de n) tenemos la conocida fórmula:

d(n) = (r₁ + 1) * (r₂ + 1) * … * (rₖ + 1)

Para cotejar los primeros valores de estas dos funciones aritméticas, observemos que:

φ(1) = 1 ; φ(2) = 1 ; φ(3) = 2 ; φ(4) = 2 ; φ(5) = 4 ; φ(6) = 2 ; φ(7) = 6

d(1) = 1 ; d(2) = 2 ; d(3) = 2 ; d(4) = 3; d(5) = 2 ; d(6) = 4 ; d(7) = 2

φ(8) = 4 ; φ(9) = 6 ; φ(10) = 4 ; φ(11) = 10 ; φ(12) = 4 ; φ(13) = 12 ; φ(14) = 6

d(8) = 4 ; d(9) = 3 ; d(10) = 4 ; d(11) = 2 ; d(12) = 6 ; d(13) = 2 ; d(14) = 4

φ(15) = 8 ; φ(16) = 8 ; φ(17) = 16 ; φ(18) = 6 ; φ(19) = 18 ; φ(20) = 8 ; φ(21) = 12

d(15) = 4 ; d(16) = 5 ; d(17) = 2 ; d(18) = 6 ; d(19) = 2 ; d(20) = 6 ; d(21) = 4

φ(22) = 4 ; φ(23) = 22 ; φ(24) = 8 ; φ(25) = 20 ; φ(26) = 12 ; φ(27) = 18 ; φ(28) = 12

d(22) = 4 ; d(23) = 2 ; d(24) = 8 ; d(25) = 3 ; d(26) = 4 ; d(27) = 4 ; d(28) = 6

φ(29) = 28 ; φ(30) = 8 ; φ(31) = 30 ; φ(32) = 16 ; φ(33) = 20 ;

d(29) = 2 ; d(30) = 8 ; d(31) = 2 ; d(32) = 6 ; d(33) = 4 ;

Así pues, entre los 33 primeros enteros positivos hay ocho y solo ocho soluciones de la ecuación

φ(n) = d(n), que son:

n = 1 → φ(1) = d(1) = 1 ;

n = 3 → φ(3) = d(3) = 2 ;

n = 8 → φ(8) = d(8) = 4

n = 10 → φ(10) = d(10) = 4

n = 18 → φ(18) = d(18) = 6

n = 22 → φ(22) = d(22) = 4

n = 24 → φ(24) = d(24) = 8

n = 30 → φ(30) = d(30) = 8

Para seguir con la demostración, aunque pueda haber otros caminos, creo que abrevia mucho el trabajo emplear una de las múltiples y curiosas propiedades que ligan a la función φ de Euler con la función d(n).

Se trata de un teorema que publicaron Minculete y Savin, en su excelente artículo

Some Properties of Euler's Function and of the function τ and Generalizations in Algebraic Number Fields,

cuya demostración no es demasiado difícil de seguir, pero es bastante laboriosa; puede consultarse y aún descargarse en pdf (por ahora) en esta página:

Some Properties of Euler’s Function and of the Function τ and Their Generalizations in Algebraic Number Fields

Teorema:

Para todo entero positivo n se da la siguiente desigualdad:

[ (3 √15)/2 ] * φ(n) ≥ τ(n) * √n .

La desigualdad es siempre estricta, salvo para n = 60, en que se produce la igualdad.

Como en esta respuesta no usamos la letra griega τ (tau) , escribiremos la desigualdad sustituyendo dicha letra por la "d", para seguir la notación de la pregunta:

[ (3 √15)/2 ] * φ(n) ≥ d(n) * √n .

Supongamos ahora, para terminar la demostración, que algún n > 33 verifica la ecuación propuesta,

φ(n) = d(n) → sustituyendo φ(n) por d(n) en la desigualdad del teorema citado, se tendrá:

[ (3 √15)/2 ] * d(n) ≥ d(n) * √n ; simplificando al dividir por d(n) (≠0) →

(3 √15)/2 ≥ √n → elevando al cuadrado ambos miembros (positivos) de la desigualdad:

9*15 / 4 ≥ n → n ≤ 33.75, pero como n es entero, será n ≤ 33 ; puesto que también suponíamos por hipótesis que era n > 33 llegamos a una CONTRADICCIÓN, que proviene de haber supuesto que la ecuación φ(n) = d(n) tenía alguna solución con n > 33 .

NO HAY SOLUCIÓN ALGUNA con n > 33, de manera que todo valor de n que sea solución de la ecuación propuesta, cumplirá n ≤ 33 .

Y como entre los primeros 33 números enteros positivos, tras la inspección individual de cada caso al principio de esta respuesta, hemos encontrado 8 soluciones de la ecuación φ(n) = d(n) y solo 8, ésas soluciones son por tanto las únicas soluciones de la ecuación dada.

Luego hemos demostrado que hay exactamente 8 soluciones:

n = 1 ; n = 3 ; n = 8 ; n = 10 ; n = 18 ; n = 22 ; n = 24 ; n = 30.