Divisibilidad, primos y algoritmo de Euclides

No es una desigualdad ni una división decimal. Admitimos signos: un divisor negativo puede dar un producto positivo. Con esta definición, cualquier entero divide cero y cero solo divide cero.

Si d divide a y b, también divide ax+by para cualesquiera enteros x,y: de a=dr y b=ds sale ax+by=d(rx+sy). Esta estabilidad de combinaciones será el motivo por el que Euclides conserva toda la información común.

Para a entero y b>0 existen únicos q,r enteros con a=bq+r y 0≤r<b. Elegimos q=floor(a/b), el entero inmediatamente inferior o igual a a/b.

La derecha tiene módulo menor que b y es múltiplo de b, así que debe ser cero. Los cocientes y restos coinciden. Las cotas son parte de la regla, también con dividendo negativo.

Si a,b no son ambos cero, sus divisores comunes positivos forman una lista finita no vacía y tienen máximo d. La propiedad más fuerte que demostraremos es que cada divisor común divide a d. No se deduce solo de que d sea el mayor por tamaño.

Podemos fijar mcd(0,0)=0 como convención, aunque en ese caso no exista máximo divisor común positivo. Dos enteros son coprimos si el mcd es uno; pueden ser ambos compuestos.

Los dos pares tienen exactamente los mismos divisores comunes: mcd(a,b)=mcd(b,r).

Repetimos con restos no negativos que disminuyen estrictamente, así que termina.

Con entradas negativas usamos valores absolutos; si una es cero, la respuesta se obtiene directamente.

Cada resto es una combinación entera de las cantidades anteriores, así que también de las entradas originales.

Como todo divisor común divide esa combinación, divide d: queda demostrada la propiedad fuerte del mcd.

Los coeficientes no son únicos.

Es fundamental leerlos en el orden del enunciado: empezar Euclides con el número mayor no cambia qué incógnita multiplica a cada entrada.

Para a,b no ambos cero, ax+by=c tiene soluciones enteras si y solo si d=mcd(a,b) divide c. Necesidad: d divide toda combinación. Suficiencia: multiplicamos una identidad de Bézout por c/d, que es entero.

Restar dos soluciones y dividir por d deja coeficientes coprimos que fuerzan esa forma. Si alguno de a,b es cero, la ecuación se trata directamente y la misma parametrización también refleja la incógnita libre.

Primo significa n>1 con únicos divisores positivos 1 y n.

Uno no es ninguno de los dos; dos es el único primo par. Para probar compuesto basta una factorización con dos factores entre uno y n.

Lema de Euclides: si p es primo y p∣ab, entonces p∣a o p∣b. Si no divide a, mcd(p,a)=1; Bézout up+va=1, multiplicado por b, muestra p∣b. Para un divisor compuesto puede fallar: diez divide 2·5 sin dividir a ninguno de esos factores.

Todo n>1 se descompone en primos por descenso de factores. Para la unicidad, un primo de una factorización divide el producto de la otra y por Euclides coincide con algún primo de ella; cancelamos y repetimos. Solo cambia el orden de los factores.

Para a,b positivos, mcd toma el menor exponente de cada primo y mcm el mayor.

Para enteros no nulos de cualquier signo usamos |ab|. Los cuadrados tienen exponentes primos pares, también cuando expresamos una fracción racional como cuadrado.

Si una lista finita p₁,…,pᵣ contuviera todos los primos, N=p₁…pᵣ+1 sería mayor que uno y tendría un divisor primo. Ninguno de los de la lista lo divide: todos dejan resto uno al dividir N. Aparece un primo fuera de la lista y se contradice que fuera completa.

No se deduce que N sea siempre primo. Puede ser compuesto y, aun así, sus divisores primos serán nuevos respecto de esa lista. Calcular un mcd, factorizar y probar primalidad son tareas relacionadas con salidas y dificultades diferentes.