Divisibilidad

Conceptos básicos
El concepto fundamental en el que estaremos interesados ahora, será el de divisibilidad, por ello introduciremos la siguiente definición .
Definición 1.1 Sean a y b dos números enteros. Decimos que a divide a b (lo que simbolizamos con a|b) si existe un entero c tal que
b = ac. Esto equivale a decir que b es múltiplo de a , o a que la división b ÷a no deja residuo.
Si a no divide a b, escribimos:



Esto es lo mismo que decir que la división b ÷a deja residuo.
Ejemplos:
3|12 pues 12 =4×3
4|20 ya que si c=5, 20= 4c.
3|0 dado que 0=3c cuando c=0




Para cualquier entero a, a+1 | a² -1, ya que a ² -1 =(a +1) × k con k = a-1.
De la definición podemos derivar ciertas propiedades básicas:
1.Todo número se divide a sí mismo: a | a
2.Si a | b, entonces a |-b. Como 4 |8 (8=4×2), 4|-8. (pues -8=4×(-2)).
3.Si a | b, entonces a |bc para todo entero c. (4|12, entonces 4|12×5).
4.Si a y b son positivos y a |b, entonces a≤ b.
5.Si a | b y b | c entonces a | c. Ejemplo: 2|10 y 10 |30, entonces 2 |30.
Si a |b y a |c entonces a | (b+c).Así 2|4 y 2|6 implica 2 | (4+6)
La prueba de la última propiedad es típica de las pruebas de problemas de divisibilidad, así que se incluye para tener un modelo.
Prueba. Si a | b y a |c, entonces existen números enteros m y n tales que b =am y c= an. Entonces b+c = am+ an = a (m+n). Como b + c = ak cuando k = (m+n), la definición de divisibilidad nos dice que a | b +c. La prueba queda terminada.
La prueba anterior puede extenderse a varios sumandos:
Teorema 10.1 Si a |x₁ ,a |x₂, a |x₃,... a |x_n, entonces
A | (c₁x₁ +c₂x₂+c₃x₄+...+c_nx_n)
Para cualquier combinación de enteros, c₁,c₂,c₃,...c_n.

Dados a y b, un número de la forma ax + by se denomina una combinación lineal de a y b. En general dados x₁,x₂,...,x_n, un número de la forma u₁x₁ + u₂x₂+...+u_nx_n se conoce como una combinación lineal de los números x₁,x₂,....x_n. Entonces el teorema anterior lo enunciamos: “Si un número divide a un conjunto de enteros, divide a cualquier combinación lineal de los mismos.”

Por ejemplo dado que 3 |6 , 3|12 y 3|15, aplicando el teorema anterior con c₁=5, c₂= -7, c₃=2, deducimos que 3 | (6 ×5 + 12× (-7) +15 ×2 )
El concepto de divisibilidad puede generalizarse de la siguiente manera:
Teorema 10.2 (Algoritmo de la división)Sean a y b dos enteros con b > 0. Entonces existen enteros únicos c y r tales que a = bc+r y 0≤ r < b.
Lo importante a notar es que el residuo es positivo y cumple o ≤ r < b, y si



Entonces 0 < r < b. Básicamente, el entero c es el cociente de la división a÷b y r es el residuo.
Ejemplos:A= 12, b= 5. a=b×2+2.
A= 38, b= 8. a=b×4+6.
A= 20, b= 4. a=b×5+0.
A= 7, b= 10. a=b×0+7.
A= -15, b= 4. a=b×(-4)+1.
A= 18, b= -5. a=b×(-3)+3.
A= -14, b= -3. a=b×5+1.

Este algoritmo adquirirá mayor importancia en la siguiente sección.
Definición 10.2
Un número positivo se llama número primo si tiene solo dos divisores positivos distintos. Un número mayor a 1 que no es primo se denomina compuesto.
Teorema 10.3
Todo número mayor a 1 es divisible por algún primo.
Prueba. Sea n >1. Supongamos que no es divisible por ningún primo. En particular, n mismo no puede ser primo pues seria divisible entre si mismo. Como n no es primo, tiene algún divisor positivo d₁ distinto de 1 y n, es decir 1 < d₁ < n. Pero d₁ no puede ser primo porque dividiría a n. Entonces existe un d₂ que divide a d₁ tal que 1 < d₂ < d₁ < n. Como d₂ no puede ser primo porque divide a n, repetimos el argumento con d₂ para obtener un d₃ tal que 1 < d₃ < d₂ < d₁ < n. Como d₃ no puede ser primo existe un d₄ que divide a d₃ y así sucesivamente. Esto lleva a una contradicción pues no es posible continuar indefinidamente este proceso ya que entre 1 y n solo hay un número finito de términos. Por tanto n debe ser divisible entre algún primo.
Este tipo de pruebas se conoce como por descenso infinito y se basa en que si la condición pedida no se cumple se crea una sucesión infinita decreciente de elementos positivos, lo cual es imposible porque los enteros positivos tienen elemento mínimo. Las pruebas por descenso infinito fueron ampliamente usadas por Fermat.
El teorema anterior será usado en muchas pruebas en la siguiente forma “Si n es un número compuesto , hay un primo p que lo divide”.
Sea n un entero mayor a 1. Si n es primo, es igual a sí mismo. Si no es primo existe un primo p₁ que lo divide y entonces p = p₁n₁. Si n₁ es primo, n es igual a un producto de primos, de lo contrario existe un primo p₂ que divide a n₁ y así p=p₁p₁n₂. Si n₂ es primo, n es igual a un producto de primos, en caso contrario existe un primo p₃ que lo divide. Continuamos aplicando este argumento y construimos una sucesión n₁,n₁,n₃... decreciente de enteros positivos que debe terminar, es decir en algún momento n_k es un número primo. De esta manera ya probamos el siguiente teorema:
Teorema 10.4 Todo número mayor a 1 puede escribirse como producto de primos.
Es decir, un número n> 1 puede escribirse de la forma:

Donde cada p_j es un número primo.
Por ejemplo 12=2²×3, 60=2²×3×5, 101=101,99=3²×11. Ahora bien, al igual que 12= 2×6=3×4 tiene varias factorizaciones, nada nos garantiza que un número dado no se pueda factorizar de maneras diferentes en producto de primos (sin importar el orden). Pero después probaremos que para cada número dado la factorización en primos sí es única. Así podemos establecer el siguiente teorema (aunque la prueba de la unicidad la posponemos hasta tener las herramientas necesarias).
Teorema 10.5 (Teorema fundamental d la aritmética)Todo número se puede factorizar de manera única como producto de primos.
Para finalizar la sección probaremos uno de los resultados clásicos de la teoría de los números y que fue establecido hace cerca de 2000 años.
Teorema 10.6 (Euclides) Hay una cantidad infinita de números primos.
Prueba. Supongamos que hay una cantidad finita de números primos y sea p₁,p₂,...p_n la lista de todos ellos. Consideremos el número p₁×p₂×... ×p_n+1. Como ese número es mayor a 1 hay un primo que lo divide. Sea p tal que p | p₁×p₂×... ×_np+1. Como p | p×p₂×... ×p_n+1 se sigue que p |1 , lo cual es imposible. Concluimos que debe existir una cantidad infinita de primos.