Dos observaciones sobre divisores

Dos argumentos combinatorios para dos resultados que serán útiles:

1
Si n = \prod p_i^{r_i} es la descomposición de un n \in \mathbb{N} en producto de factores primos y n=x \cdot y, con x,y \in \mathbb{N}, las descomposiciones de x e y serán x = \prod p_i^{s_i} e y = \prod p_i^{r_i-s_i} , y como para cada s_i podemos elegir entre los r_i +1 valores \{ 0,1,\ldots,r_i\}, el número de soluciones (x,y), \ \ x,y \in \mathbb{N}, de x\cdot y = n, o, lo que es lo mismo, el número de divisores de n, es igual a \prod (r_i+1).

2
Sea a > 1, \  d_1(n) el número de divisores de n que son \equiv 1 \pmod{a}, y d_{-1}(n) el número de divisores de n que son \equiv -1 \pmod{a}.
Si n= s \cdot t   y s,t son primos entre sí, y t solo tiene factores primos \equiv -1  \pmod{a}, entonces
d_1(n)-d_{-1}(n) = \left\{ \begin{array}{ll}  0 &\mbox{ si } t \mbox{ no es un cuadrado} \\  d_1(s)-d_{-1}(s) &\mbox{ si }t \mbox{ es un cuadrado }   \end{array} \right.
porque si q \equiv -1 \pmod{a} no divide a m y el conjunto de divisores de m es \{ m_i \}, el de mq^h será \{ m_i \} \cup \{ qm_i \} \cup \{ q^2m_i \} \cup \ldots \cup \{ q^hm_i \} y entonces, como al multiplicar por un número \equiv -1 \pmod{a} se invierte el signo de los restos:
d_1(mq^h) = d_1(m) + d_{-1}(m)+ d_1(m) + \ldots + d_{\pm 1}(m) donde el último término es d_1(m) o d_{-1}(m) según h sea par o impar. De la misma forma:
d_{-1}(mq^h) = d_{-1}(m) + d_{1}(m)+ d_{-1}(m) + \ldots + d_{\mp 1}(m).
Entonces si h es par d_1(mq^h) - d_{-1}(mq^h) =  d_1(m) - d_{-1}(m) y si h es impar d_1(mq^h) = d_{-1}(mq^h).

Primos gaussianos

En la entrada anterior obtuvimos que todo entero gaussiano se descompone en forma única en producto de factores primos. En esta determinamos cuáles son los primos gaussianos.
Descomposición de en primos (formato a+bi):

[-113+319i] = [-i][1+i][1+2i][3+2i][16+25i]


Todo primo (a+bi) de \mathbb{Z}[i] divide a algún primo de \mathbb{Z}, porque (a+bi) divide a su norma (a+bi)(a-bi) que es un entero de \mathbb{Z} y por el teorema de factorización única en \mathbb{Z}[i], si (a+bi) es primo divide a alguno de los primos de \mathbb{Z} que son factores de la norma. Basta entonces considerar los divisores de los primos en \mathbb{Z} para obtener todos los primos de \mathbb{Z}[i].
Por otro lado, si la norma de w \in \mathbb{Z}[i] es un primo de \mathbb{Z}, w es un primo en \mathbb{Z}[i], porque como la norma es múltiplicativa, la norma de un divisor propio (distinto de un asociado y de una unidad) de w es un divisor propio de la norma de w, lo que no es posible si esta es un primo. Entonces w no tiene divisores propios y por tanto es primo.

Como 2=-i(1+i)^2, y la norma de 1+i es 2, \ (1+i) y sus asociados son primos de \mathbb{Z}[i].
Si p es un primo de \mathbb{Z} de la forma 4k+1, por el teorema de Girard-Fermat, p=a^2+b^2= (a+bi)(a-bi), y estos dos factores son primos de \mathbb{Z}[i] porque su norma es un primo.
La norma de un divisor propio de un primo p de \mathbb{Z} de la forma 4k+3, tendría que ser p, pero considerando restos al dividir por 4, p no puede ser suma de dos cuadrados, y entonces no tiene divisores propios y p y sus asociados son primos en \mathbb{Z}[i].

Por tanto los primos en \mathbb{Z}[i] son:

  • 1+i y sus asociados

  • los divisores (a+bi) y (a-bi) de los primos de \mathbb{Z} de la forma 4k+1, y sus asociados

  • los primos de \mathbb{Z} de la forma 4k+3 y sus asociados

Como uno de los 4 asociados g, ig, -g, -ig, está en el primer cuadrante del plano complejo, todo entero gaussiano se descompone en forma única como producto de una unidad por primos del primer cuadrante.

Los enteros gaussianos son euclídeos

MCD DE ENTEROS GAUSSIANOS
Anotar números en formato a+bi, \ a,b \in \mathbb{Z}
mcd( , )= [-1+i]

[-51+33i] = [81-17i] [-1] + [30+16i]
[81-17i] = [30+16i] [2-2i] + [-11+11i]
[30+16i] = [-11+11i] [-1-2i] + [-3+5i]
[-11+11i] = [-3+5i] [3+i] + [3-i]
[-3+5i] = [3-i] [-1+i] + [-1+i]
[3-i] = [-1+i] [-2-i]

[-1+i] = [-51+33i][19] + [81-17i][13-5i]

El conjunto \mathbb{Z}[i] de los enteros gaussianos son los números a+bi, con a y b enteros, y i=\sqrt{-1}. Es claro que son un subanillo del cuerpo de los complejos.

El recuadro utiliza el algoritmo de Euclides para obtener el máximo comun divisor de los dos enteros gaussianos que se anoten.

Es posible aplicar el algoritmo de Euclides porque los enteros gaussianos son un dominio euclídeo, es decir, un dominio de integridad en el cual cada elemento a tiene asociado un entero concreto \phi(a), y la función \phi satisface las siguientes condiciones:
E1. Si b divide a a, entonces \phi(b) \le \phi(a).
E2. Para cada par de elementos a,b del dominio, con {}b \neq 0, existen elementos q y r del dominio tales que a=bq+r con \phi(r) < \phi(b).

Demostración.
Usamos como función \phi la norma, N(a+bi), que es el producto de a+bi por su conjugado: N(a+bi)  = (a+bi)(a-bi) = a^2 + b^2, y es un entero igual al cuadrado del módulo del número complejo.

Se verifica E1 porque la norma es multiplicativa:  N(z_1 z_2) = z_1z_2\overline{z_1z_2} = N(z_1)N(z_2), porque el conjugado del producto es el producto de los conjugados. Entonces si a,b \in \mathbb{Z}[i], y b|a, \ N(b)|N(a), y por tanto N(b) \le N(a).

Que se verifica E2 se ve claro gráficamente.
Al multiplicar el retículo \mathbb{Z}[i] del plano complejo por un número z, el retículo se transforma en otro generado por z e iz, y, cualquier número en el plano es suma de un número en el retículo más otro cuyo módulo es menor o igual que \frac{\sqrt{2}}{2}|z|, es decir cuya norma es menor o igual que la mitad de la norma de z.

Por tanto para a,b \in \mathbb{Z}[i], con {}b \neq 0, existen q,r \in \mathbb{Z}[i] tales que a=bq+r con N(r) < N(b).

Entonces los enteros gaussianos son un dominio euclídeo, y en consecuencia un dominio de factorización única.

Girard-Fermat via Minkowski

“La proposición fundamental de los triángulos rectángulos es que todo número primo, que sobrepase en una unidad un múltiplo de 4, está compuesto de dos cuadrados.”
(Fermat, carta a Frenicle, 15 jun 1641)

Ese resultado se conoce a veces como teorema de Fermat, pero sería más apropiado llamarlo teorema de Girard-Fermat-Euler, teniendo en cuenta que Girard lo enunció primero y que el primero en publicar una demostración fue Euler.

Una de la demostraciones del teorema está basada en el teorema de Minkowski.

Si p es un número primo de la forma 4k+1, por el criterio de Euler existe un a tal que a^2 \equiv -1 \pmod{p}.

En el retículo generado por (p,0) y (a,1), el área del paralelogramo fundamental es p.
Cada punto (x,y) de ese retículo es de la forma (np+ma,m) \  n,m \in \mathbb{Z} y x^2 + y^2 es múltiplo de p, porque (np+ma)^2 + m^2 \equiv m^2a^2 + m^2 \equiv 0 \pmod{p} .

La circunferencia con centro en (0,0) y radio \frac{4}{3}\sqrt{p} tiene área \frac{16\pi}{9}p ,mayor que 4 veces el área p de una celda y por tanto, por el teorema de Minkowski, existe un punto (x,y) del retículo distinto de (0,0) en el interior de la circunferencia.

Como, para ese punto (x,y), \ x^2+y^2 es múltiplo de p, y x^2 + y^2 < \frac{16}{9}p, cuadrado del radio de la circunferencia, tendrá que ser x^2 + y^2 = p, y por tanto todo primo de la forma 4k+1 es suma de dos cuadrados, como queríamos demostrar.

Una nota de A. Girard sobre Diofanto

En las páginas 405-677 de la edición de la Aritmética de Simon Stevin, en 1625, por Albert Girard, están traducidos al francés los libros I-VI de la Aritmética de Diofanto, los cuatro primeros por Simon Stevin y los restantes por Albert Girard.

Albert Girard anota, sin demostración, en el problema V.12 de Diofanto (página 622):

“Determinación de los números que se pueden dividir en dos cuadrados enteros:
I. Todo número cuadrado.
II. Todo número primo que exceda a un número cuaternario en una unidad.
III.El producto de números tales
(sumas de dos cuadrados).
IV. Y el doble de cada uno de ellos.”


Es la primera vez que aparece enunciada la condición necesaria y suficiente para que un entero sea suma de dos cuadrados, y que equivale a decir que un entero positivo es representable como suma de dos cuadrados si y solo si en su descomposición en factores primos los primos de la forma 4k+3 tienen exponente par.

El criterio de Euler

Para un primo p impar, si a,b \in \{1\ldots p-1\}, es fácil demostrar que:

  • la ecuación ax \equiv b \pmod{p} tiene una única solución
  • la ecuación x^2 \equiv a \pmod{p} tiene ninguna o dos soluciones.

A partir de esos hechos Gauss demuestra en el artículo 77 de las Disquisitiones el teorema de Wilson. Con el mismo método se demuestra a continuación el criterio de Euler, que dice que un elemento a del sistema de restos \{1,\cdots,p-1\} de un primo p es o no es un cuadrado según a^{\frac{p-1}{2}} sea \equiv 1 ó \equiv -1 \pmod{p}.

Para un resto a, formamos todos los pares (x,y), con \ x \le y, \ x\cdot y \equiv a \pmod{p}.

Si a no es un cuadrado módulo p, los elementos de todos los pares serán diferentes, y como hay p-1 términos x,y, habrá \frac{p-1}{2} pares y el producto de todos los elementos de todos los pares será  a^{\frac{p-1}{2}} \equiv (p-1)! \equiv -1 \pmod{p}, por el teorema de Wilson.

Si a es un cuadrado módulo p, habrá dos pares (\sqrt{a}, \sqrt{a}), \ (-\sqrt{a}, -\sqrt{a}), y en el resto de los pares los términos serán diferentes. Entonces habrá un total de \frac{p+1}{2} pares. Multiplicando todos los términos de todos los pares tenemos a^{\frac{p+1}{2}} \equiv -a(p-1)! \pmod{p}, es decir a^{\frac{p-1}{2}} \equiv 1 \pmod{p}, por el teorema de Wilson.

Corolarios.
El pequeño teorema de Fermat (a^{p-1} \equiv 1) no se ha usado en la demostración del teorema de Wilson por el artículo 77 de Gauss ni más arriba, y es un corolario evidente.
Otro corolario es que \sqrt{-1} existe en los sistemas de restos para los primos de la forma 4k+1 y no existe para los primos de la forma 4k+3.

Hacen falta nociones y no notaciones

C.F.Gauss escribe en el artículo 76 de las Disquisitiones Arithmeticae, tras haber demostrado el teorema de Wilson mediante raices primitivas:

Este elegante teorema suele enunciarse así: el producto de todos los números menores que un número primo dado, sumado a uno, es divisible por este primo. Fue publicado primero por el célebre Waring, y adscrito a Wilson, (Meditt.algebr., tercera edición, p. 380). Pero ninguno pudo demostrarlo, y el célebre Waring confesó que la demostración parecía más difícil porque ninguna notación puede confeccionarse para expresar un número primo. Pero a nuestro juicio tales verdades deberían percibirse por medio de las nociones más que por las notaciones.

A continuación menciona las demostraciones de Lagrange y Euler y añade:
Pero si tan distinguidos matemáticos no han considerado sin mérito a este teorema para sus meditaciones, esperamos no ser censurados si adjuntamos todavía otra demostración:

Gauss dixit.


Referencia: C.F.Gauss. Disquisitiones Arithmeticae. Versión española por Hugo Barrantes, Michael Josephy y Angel Ruiz, Seccion III, arts.76-77.

Dominios euclídeos

En la proposición primera del libro VII de los Elementos, el primero de los tres dedicados a lo que hoy se llama teoría de números, Euclides presenta el hoy conocido como algoritmo de Euclides, que permite obtener el máximo común divisor de dos números.
En la proposición 30 del libro VII, Euclides deduce que si p es primo y p divide a ab, entonces p divide a a ó p divide a b, de donde se puede obtener el teorema de descomposición única en producto de factores primos, llamado teorema fundamental de la aritmética.

Siguiendo los pasos de Euclides, hoy se demuestra que un dominio de integridad que tenga un algoritmo de división es un dominio de factorización única.

A continuación está esbozada la demostración de ese hecho que dan Oscar Zariski y Pierre Samuel en su “Commutative Algebra” (Ch.I.$14,$15.):
Leer más