se cumple para todo n?

¿Cómo puedo probar que τ(n) * φ(n) ≥ n se cumple para todo n?

Para aquellos lectores y estudiantes que no estén familiarizados con la Teoría de números, o como se llama también a veces, en hermoso castellano, la Aritmética Superior, repasaremos algunos hechos y definiciones básicas, como breve recuerdo introductorio para situar el problema, y no solo dar esquemáticamente la solución. La idea es animar a seguir esta demostración a lectores que en principio no leerían, probablemente, la solución de un problema como el que plantea la pregunta, por desconocimiento de la nomenclatura y las técnicas utilizadas.

Muchas veces la caña es más interesante que el pez, como ocurre en este caso.

En el ámbito de las escuelas primaria y secundaria, suele entenderse el vocablo "Aritmética" como sinónimo de "Aritmética elemental", esa colección de conocimientos muy, muy básicos, que incluyen las cuatro operaciones fundamentales con números naturales, extendida hasta el manejo algorítmico simple de potencias y raíces con números racionales, incluyendo en ellos a los útiles números decimales.

En seguida se abandona la Aritmética colegial, después de estudiar lo más simple y elemental sobre divisibilidad, descomposición de un número natural en factores primos, cálculo del máximo común divisor y del mínimo común múltiplo, conversión de fracciones en decimales periódicos o viceversa, y prácticamente ahí termina todo, para empezar una matemática mucho más avanzada : la "temida" Álgebra, algunos conceptos básicos de la Geometría Analítica, un poquito de Análisis Matemático que alcanza en bachillerato tan solo a límites de funciones reales de variable real, derivadas e integrales muy sencillas de funciones elementales, sin entrar en muchos tecnicismos ni fundamentos lógicos, y ahí queda todo hasta que en estudios universitarios se abordan ramas realmente avanzadas como el Álgebra abstracta, el Análisis Matemático en todas sus inmensas ramas, la Topología y cosas bastante "complejas", como la propia Variable compleja, las Ecuaciones diferenciales…y como ésta, otras partes del Análisis Matemático, que ya constituyen auténticas ramas matemáticas con nombre propio.

En definitiva, se ve la matemática "superior" en contraposición con la matemática "elemental", con la que los estudiantes de secundaria (y más gente…) asocian a menudo, inconscientemente, la palabra Aritmética.

Las pocas personas que llegan a estudiar alguna introducción a la matemática discreta emplean ciertas herramientas -ya menos elementales- sobre los números enteros, y descubren, de manera incipiente, que existe la rama denominada Teoría de los números, que es verdaderamente la Aritmética avanzada, aquélla que quedó interrumpida en secundaria no por no ser interesante, todo lo contrario, sino por requerir para su estudio profundo de todas las demás ramas de la matemática. Está bien darle ese nombre particular a la Aritmética, una de las más antiguas ramas de la matemática, para no confundir los términos; pero una vez que se conoce algo de la enorme dificultad de los problemas no elementales de la Aritmética, desde luego se destierra esa falsa suposición de que se refiere a las habas contadas, de que se ocupa de hechos triviales sobre conjuntos finitos y sus cardinales, como que 2+2=4…, etc.

Es un hecho que los conjuntos finitos nos pueden crear infinitos problemas; problemas no triviales, y tanto la Teoría de números como la Combinatoria, intrínsecamente relacionada con ella, son ramas de la matemática actual extremadamente activas, profundas y con aplicaciones de espectacular importancia.

El problema de demostrar la desigualdad τ(n) * φ(n) ≥ n

Se trata de funciones aritméticas clásicas. Tanto τ como φ desempeñan un gran papel en toda la matemática, pero de manera especial y protagonista en la teoría de números.

Se define, para todo entero positivo n, τ(n) = número de divisores de n enteros positivos. Por ejemplo, τ(1) =1 ; τ(2) =2 ; τ(3) =2, τ(360) =24, τ(400) = 15, etc. De hecho, que 360 tenga 24 divisores (más que 400, que solo tiene 15) hace más cómodo e intuitivo el sistema sexagesimal que el centesimal para medir ángulos.

Una función aritmética f es multiplicativa cuando sucede que si (m,n)=1, o dicho de otro modo, si Máximo Común Divisor de m y n es 1, o aún de otra manera expresado, si m y n son primos entre sí, entonces f(mn) = f(m) f(n).

Si para todo par m,n, sin ninguna condición adicional, sucede

f(mn) = f(m) f(n), la función se llama totalmente multiplicativa.

La función τ es multiplicativa; en efecto, supongamos (m,n) = 1.

Necesitamos expresar la función τ de alguna manera algorítmica que pueda usarse en la demostración. Para ello, veamos cómo calcular τ(n).

Supongamos que la descomposición de n en factores primos es:

n = p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ , donde p₁, p₂, … p ⱼ son números primos diferentes y sus exponentes respectivos son γ₁, γ₂, … γ ⱼ son cualesquiera enteros positivos.

Cualquier número d de la forma d = p₁^λ₁ * p₂^λ₂ * …* p ⱼ ^ λ ⱼ,

con λ₁ ≤ γ₁ ; λ₂ ≤ γ₂ …, λ ⱼ ≤ γ ⱼ es, evidentemente, divisor de n; y viceversa,

si un número d es divisor de n (se escribe d | n ), no puede contener en su descomposición en factores primos ningún número primo que no figure en n, puesto que la descomposición de cualquier número en factores primos es única, salvo el orden de los factores (Teorema Fundamental de la Aritmética).

Luego d será de la forma:

d = p₁^λ₁ * p₂^λ₂ * …* p ⱼ ^ λ ⱼ, con λ₁ ≤ γ₁ ; λ₂ ≤ γ₂ …, λ ⱼ ≤ γ ⱼ.

Naturalmente, estas desigualdades en los exponentes provienen del hecho de que n contiene todos los factores de su divisor d y tal vez alguno más, pero nunca menos. Ahora bien, por un sencillo argumento combinatorio, vemos que para elegir el exponente λ₁ tenemos γ₁+1 posibilidades: λ₁ = 0, 1, 2, …γ₁ ;

lo mismo para λ₂ = 0, 1, 2, …γ₂ , habrá γ₂+1 posibilidades, etc.

Luego el número de maneras de elegir un divisor de n será el mismo que el número de maneras de elegir λ₁ , λ₂, … λ ⱼ ; por la regla del producto, será el producto (γ₁+1) * (γ₂+1) *…* (γ ⱼ+1), de modo que:

τ(n) = (γ₁+1) * (γ₂+1) *…* (γ ⱼ+1).

Afirma Castillionei en ARITHMETICA UNIVERSALIS, de Isaac Newton, edición de 1761 (en latín), (página 61 del texto principal de Newton, Sectio Prima , Capítulo VIII) que si la descomposición de un número natural N en factores primos a, b, c… es: N = aᵐ bⁿ cᵖ…, su número de divisores naturales es (m+1)*(n+1)*(p+1)…etc. Al parecer, ésta es la primera vez en que se publica tal fórmula, mientras no aparezca alguna publicación anterior.

La función φ de Euler : (También llamada indicador o totalizador, o totient)

Dado el entero positivo n, se define φ(n) = número de enteros positivos menores que n y primos con n, es decir, que no tengan ningún factor común con n. Otra manera más visual de definir el indicador de n es:

φ(n) = número de fracciones irreducibles entre {1/n, 2/n ,… (n-1)/n }.

Se tiene, evidentemente, φ(1) = 1.

Si n > 1, por ejemplo, n=6, vemos que en {1/6, 2/6, 3/6, 4/6, 5/6} sólo hay dos fracciones que son irreducibles: 1/6 y 5/6. Luego φ(6) =2.

Sobre la función indicador de Euler hay problemas fascinantes, varios de ellos abiertos y algunos resueltos con gran esfuerzo. Está detrás de muchos resultados matemáticos insospechadamente alejados, a primera vista, de su definición; por ejemplo, la condición necesaria y suficiente para que un polígono regular convexo se pueda dibujar exactamente con solo regla y compás es que φ(n) sea una potencia de 2; como φ(7) = 6, que no es potencia de 2, por eso el heptágono regular no es constructible exactamente con solo regla y compás; mientras que sí es exactamente constructible el heptadecágono con solo regla y compás, pues φ(17) = 16 = 2⁴ , potencia de 2.

De las muchas demostraciones conocidas para calcular φ(n) a partir de la descomposición de n en factores primos, mi favorita es una demostración combinatoria. Hay otras interesantes: aritméticas, algebraicas (basadas en teoría de grupos)…

En general, si k ≤ n, con k entero positivo, la cantidad de enteros positivos menores o iguales que n, que son múltiplos de k se puede calcular como [n/k], donde [x] representa la parte entera de x ; puesto que los múltiplos de k entre 1 y n son de la forma kh, con h entero positivo tal que: 1 ≤ kh ≤ n →

1 ≤ h ≤ n/k → 1 ≤ h ≤ [n/k ] → hay exactamente [n/k] valores de h que cumplan estas desigualdades, es decir, hay [n/k] múltiplos de k que sean menores o iguales que n.

Dado que n = p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ , contemos cuántos enteros positivos menores o iguales que n son múltiplos de al menos uno de los p₁, p₂, …, p ⱼ.

También cuántos son múltiplos de al menos dos de los primos p₁, p₂, …, p ⱼ.

etc. etc…

Y así sucesivamente, hasta cuántos son múltiplos de todos los primos

p₁, p₂, …, p ⱼ.

Los múltiplos de p₁, menores o iguales que n, serán en total:

M₁ = [n/p₁] = n/p₁ (puesto que n es múltiplo de p₁) ;

Los múltiplos de p₂, menores o iguales que n, serán en total:

M₂ = [n/ p₂] = n/ p₂ ; etc. hasta M ⱼ = [n/p ⱼ] = n/ p ⱼ , que es el número de los múltiplos de p ⱼ que son menores o iguales que n.

Del mismo modo, el número de enteros menores o iguales que n, que son múltiplos de p₁ y p₂ será M₁₂ = n/(p₁ p₂)…y análogamente , Mᵣₛ = n/(pᵣ pₛ) será el nº de múltiplos de pᵣ pₛ, con 1 ≤ r ≤ n ; 1 ≤ s ≤ n (r≠s).

En general, representemos por Mᵣₛₜ…ᵥ = n/(pᵣ pₛ pₜ… pᵥ) el nº de enteros positivos menores o iguales que n que son múltiplos de pᵣ, pₛ, pₜ,… , pᵥ.

Representemos el conjunto de enteros positivos menores o iguales que n, que son múltiplos de p₁, por A₁, cuyo cardinal - su nº de elementos- es M₁ ; análogamente, sea A₂ el conjunto de enteros positivos menores o iguales que n, que son múltiplos de p₂, cuyo cardinal es M₂, y así sucesivamente, sea Aᵣₛₜ…ᵥ el conjunto de enteros positivos menores o iguales que n que son múltiplos de pᵣ pₛ pₜ… pᵥ, cuyo cardinal es Mᵣₛₜ…ᵥ.

El conjunto A₁ ∪ A₂ ∪ …∪ A ⱼ es el conjunto de enteros menores o iguales que n que tienen con n al menos algún factor primo común, esto es, alguno de los primos p₁, p₂, …, p ⱼ.

Las intersecciones de dos conjuntos A son del tipo A₁ ∩ A₂ = A₁₂, y lo mismo para las intersecciones de más de dos conjuntos, que cumplen:

Aᵣ ∩ Aₛ ∩… ∩ Aᵥ = Aᵣₛₜ…ᵥ. Representemos con N(A) = cardinal de A.

Ahora, tras esta digresión terminológica, podemos ver claramente que si n > 1

n - N (A₁ ∪ A₂ ∪ …∪ A ⱼ) será exactamente el número de enteros positivos menores que n (no pueden ser iguales) y primos con n. Esto es,

φ(n) = n - N (A₁ ∪ A₂ ∪ …∪ A ⱼ).

Para calcular N (A₁ ∪ A₂ ∪ …∪ A ⱼ) empleamos la fórmula debida a Sylvester, la llamada fórmula de inclusión-exclusión (o principio de clasificación cruzada):

N (A₁ ∪ A₂ ∪ …∪ A ⱼ) = Σ₁-Σ₂+Σ₃-….+ (-1) ʲ⁺¹ Σ ⱼ ,

donde Σ₁ = N(A₁)+N(A₂)+…+N(A ⱼ),

Σ₂ = N(A₁₂) + N(A₁₃)+…(todas las intersecciones binarias),

Σ₃ = N(A₁₂₃) + …(intersecciones de todas las ternas posibles)

………………………………………………. etc. …………………………………………

y Σ ⱼ = N(A₁₂…ⱼ) (la intersección de todos). Así,

Σ₁ = M₁ + M₂ +…+ M ⱼ ; Σ₂ = M₁₂+M₁₃+… ; Σ₃ = M₁₂₃ +… ; Σ ⱼ = M₁₂ … ⱼ .

Por tanto, partimos de

N (A₁ ∪ A₂ ∪ …∪ A ⱼ) = Σ₁ - Σ₂ + Σ₃ - …+ (-1) ʲ⁺¹ Σ ⱼ .

Luego,

φ(n) = n - Σ n/p₁ + Σ n/(p₁ p₂) - Σ n/(p₁ p₂p₃) - …+ (–1) ʲ * n/(p₁ p₂…p ⱼ).

Sacando n como factor común, resulta:

φ(n) = n [1- Σ 1/p₁ + Σ 1/(p₁ p₂) - Σ 1/(p₁ p₂p₃) - …+ (–1) ʲ * 1/(p₁ p₂…p ⱼ) ].

Aunque parezca un galimatías, cualquiera que haya trasteado con productos de binomios, especialmente en la demostración de las relaciones de Cardano-Vieta, que verifican las n raíces de toda ecuación polinómica de grado n, reconoce este producto:

(x-a)(x-b)(x-c)…(x-l)(x-m) =

= xⁿ-(a+b+c+…+l)xⁿ⁻¹+ (ab+ac+…+lm)xⁿ⁻² - (abc+abd+…)xⁿ⁻³ +…+

+(-1)^n * abc…lm.

Los coeficientes de cada potencia de x, a partir del segundo término, son, con signos alternos, la suma de las combinaciones monarias, la suma de las binarias, la suma de las ternarias…hasta la suma de las n-arias (solo hay una).

Puede probarse por inducción o también simple y elegantemente por un razonamiento combinatorio transparente : para cualquier r tal que 0 ≤ r ≤ n, elegimos x en r factores binomios y n-r segundos términos elegidos de todos los modos posibles entre a,b,c…l,m, y aparece la fórmula al instante. También sirve este desarrollo para demostrar la fórmula del Binomio de Newton, haciendo a=b=c=…=l=m=-y, y obtendríamos el desarrollo de (x+y) ⁿ.

Por tanto, 1- Σ 1/p₁ + Σ 1/(p₁ p₂) - Σ 1/(p₁ p₂p₃) - …+ (–1) ʲ * 1/(p₁ p₂…p ⱼ) =

1-(1/p₁ + 1/ p₂ +…+ 1/p ⱼ) + [(1/(p₁ p₂) + /(p₁ p₃)+ …] -…+

+ (–1) ʲ * 1/(p₁ p₂…p ⱼ) = (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ), sustituyendo en la expresión de φ(n) → φ(n) =

= n [1- Σ 1/p₁ + Σ 1/(p₁ p₂) - Σ 1/(p₁ p₂ p₃) - …+ (–1) ⁿ * 1/(p₁ p₂…p ⱼ) ] =

n * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ), de modo que finalmente tenemos la relativamente sencilla expresión algorítmica para el indicador de Euler :

φ(n) = n * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ) ; en particular, si p es primo,

φ(p) = p-1, como era esperable a simple vista.

LA DEMOSTRACIÓN QUE SOLICITA LA PREGUNTA:

Se nos pide demostrar que "para todo n entero positivo" (así lo suponemos, para que tenga sentido la pregunta, aunque no lo advierte su redacción) se verifica:

τ(n) * φ(n) ≥ n. Supongamos que la descomposición de n en factores primos es

n = p₁^γ₁ * p₂^γ₂ * …* p ⱼ^γ ⱼ , donde p₁, p₂, … p ⱼ son números primos diferentes y sus exponentes respectivos γ₁, γ₂, … γ ⱼ son cualesquiera enteros positivos. Tendremos, por lo ya expuesto, que:

τ(n) = (γ₁+1) (γ₂+1)…(γ ⱼ+1) ; φ(n) = n * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ).

Que ambas son funciones multiplicativas se desprende de las anteriores fórmulas; en efecto:

Sean m = q₁^λ₁ * q₂^λ₂ * …* qₛ^λₛ ; n = p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ , las descomposiciones respectivas de m y n en factores primos, siendo los primos

p ᵢ (1 ≤ i ≤ j ) distintos dos a dos, y los primos q ᵢ (1 ≤ i ≤ r), también distintos entre sí dos a dos; como consecuencia de que m y n son primos entre sí, serán todos los primos p ᵢ (1 ≤ i ≤ j ) distintos de todos los primos q ᵢ (1 ≤ i ≤ r), y se cumplirá:

τ(mn) = τ(q₁^λ₁ * q₂^λ₂ * …* qₛ^λₛ* p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ) =

= (λ₁+1) (λ₂+1)…(λₛ+1) (γ₁+1) (γ₂+1)…(γ ⱼ+1) =

= [(λ₁+1) (λ₂+1)…(λₛ+1) ] * [(γ₁+1) (γ₂+1)…(γ ⱼ+1) ] = τ(m) τ(n) ; C.Q.D.

Respecto a la función de Euler,

φ(mn) = φ(q₁^λ₁ * q₂^λ₂ * …* qₛ^λₛ* p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ) =

q₁^λ₁ * q₂^λ₂ * …* qₛ^λₛ* p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ (1–1/q₁) (1–1/q₂) …

…(1–1/qₛ) * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ) = (reordenando) =

= [ q₁^λ₁ * q₂^λ₂ * …* qₛ^λₛ* (1–1/q₁) (1–1/q₂) …(1–1/qₛ) ] *

[ p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ) ] =

= [m (1–1/q₁) (1–1/q₂) …(1–1/qₛ) ] * [n (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ) ] =

= φ(m) φ(n) , de modo que tanto τ como φ son multiplicativas, C.Q.D.

Ahora estamos en disposición de probar la desigualdad deseada:

τ(n) * φ(n) ≥ n.

En efecto, si n = 1, tenemos φ(1) τ(1) = 1*1 = 1 ≥ 1. (Se da la igualdad).

Si n = 2 → τ(2) * φ(2) = 2 * 1 = 2 ≥ 2. (Se da la igualdad).

Si n > 2, será n = p₁^γ₁ * p₂^γ₂ * …* p ⱼ ^ γ ⱼ

(suponemos ordenados los primos de menor a mayor: p₁ < p₂ < … < p ⱼ, en el caso en que haya más de uno, o sea, el caso en que j > 1).

τ(n) * φ(n) = (γ₁+1) (γ₂+1)…(γ ⱼ+1) * n * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ) (&)

Bastará probar que τ(n) * φ(n) /n =

= (γ₁+1) (γ₂+1)…(γ ⱼ+1) * (1–1/p₁) (1–1/p₂) …(1–1/p ⱼ) ≥ 1, puesto que entonces, multiplicando ambos miembros por n se obtendrá:

τ(n) * φ(n) ≥ n y habremos demostrado lo que se nos pedía.

Observemos que cada uno de los primos p₁, p₂, … ,p ⱼ distintos (y ordenados de menor a mayor p₁ < p₂ < … < p ⱼ ) es mayor o igual que 2.

Por ejemplo, si p₁ > 2 → 1/p₁ < 1/2 → -1/p₁ > - 1/2 ; sumando 1 a los dos miembros, 1-1/p₁ > 1/2 ; pero el exponente correspondiente a p₁ en la descomposición factorial canónica de n es, por hipótesis, γ₁ ≥ 1 →

γ₁+1 ≥ 2 ; 1-1/p₁ > 1/2 ,

de modo que, multiplicando miembro a miembro (son los cuatro positivos),

(γ₁+1) * (1-1/p₁) > 2 * (1/2) = 1. Exactamente del mismo modo (solo cambiando el subíndice1 por cualquier subíndice r ), se prueba, en caso de que haya más de un primo p ᵢ , y todos mayores que 2, que cada producto del tipo (γ ᵣ+1) (1-1/pᵣ) es > 1 ; desigualdad estricta, pues pᵣ > p₁ > 2 → pᵣ > 2 →1/pᵣ < 1/2 → -1/pᵣ > -1/2

1-1/pᵣ > 1/2 junto con γᵣ+1 ≥ 2 → (γ ᵣ+1) (1-1/pᵣ) > 1, así que, según (&) :

τ(n) * φ(n) /n = [ (γ₁+1)(1–1/p₁) ] * [(γ₂+1)(1–1/p₂) ] * …[(γ ⱼ+1)(1–1/p ⱼ) ]; siendo todos los corchetes mayores que 1, será τ(n) * φ(n) /n > 1 →

τ(n) * φ(n) > n, que es aún más fuerte que la desigualdad que queríamos probar, puesto que es estricta (>), no "amplia" (≥).

En el caso singular en que p₁ = 2 y ya no hay más primos, por ser j=1, entonces

n = 2^γ₁, y como es n > 2 ha de ser γ₁ > 1 → τ(2^γ₁) * φ(2^γ₁) =

= (γ₁+1) (2^γ₁) (1–1/2) > (γ₁+1) (2^γ₁) * (1/2) > (γ₁+1) [2^(γ₁-1) ] > 2*1 = 2, se da la desigualdad estricta.

Mientras que si p₁ = 2, pero hay al menos otro primo más, p₂ >2, será igualmente estricta la desigualdad porque γ₂+1 ≥ 2 ; 1–1/p₂ > 1/2 →

(γ₂+1)(1–1/p₂) > 2 * 1/2 =1 ; de nuevo, siendo todos los corchetes ≥ 1

y al menos uno estrictamente mayor que 1, será

τ(n) * φ(n) /n = [(γ₁+1)(1–1/p₁) ] * [(γ₂+1)(1–1/p₂)] * …[(γ ⱼ+1)(1–1/p ⱼ) ] >1,

luego τ(n) * φ(n) /n >1 → τ(n) * φ(n) > n, la desigualdad estricta.

Sólo se da la igualdad en τ(n) * φ(n) ≥ n en el caso n=1 →τ(1) * φ(1) = 1*1 = 1 ≥ 1 y, como hemos visto, en el caso n = 2, que da τ(2) * φ(2) = 2*1=2 ≥ 2 .

En todos los demás casos, con n > 2, la desigualdad es estricta:

τ(n) * φ(n) > n para cada n>2 ; y así termina la demostración pedida.