ℤ = {…, −n, …, −3, −2, −1, 0, 1, 2, 3, …, n, … | n ∈ ℕ}.
Suponemos que el lector está familiarizado con la suma y la multiplicación de números enteros. Es decir, en ℤ podemos sumar y multiplicar elementos: 2 + 3 = 5 o (−3)3 = −9. (Más adelante, diremos que ℤ con estas operaciones es un anillo). También utilizamos que ℤ es un conjunto con un orden: 3 > 0, −5 ≤ 5 o 2 ≤ 2.
Estamos acostumbrados a dividir dos números enteros n y m, y obtener un dividendo d y un resto r. Este es el llamado algoritmo de división.
Teorema 1.12 (algoritmo de división) Sean n ∈ ℤ y 0 < m ∈ ℕ. Entonces existen dos únicos enteros d y r tales que n = dm + r con 0 ≤ r < m.
Demostración. Consideremos el conjunto A = {n−dm | d ∈ ℤ y n−dm ≥ 0}. Es decir, A está formado por los números naturales de la forma n − dm, con d ∈ ℤ. Si n ≥ 0, entonces n − (−n)m = n(1 + m) ≥ 0, y deducimos que n(1 + m) ∈ A. Si n ≤ 0, entonces n − nm = n(1 − m) ≥ 0, y deducimos que n − nm ∈ A. En cualquier caso, concluimos que A ≠ ∅. Por el teorema 1.9, sea r el menor elemento de A. Como r ∈ A, entonces existe d ∈ ℤ tal que n − dm = r. Por tanto, n = dm + r. Si r ≥ m, tendríamos que
0 ≤ r − m = (n − dm) − m = n − (d + 1)m ∈ A.
Pero r es el menor elemento de A y r − m < r. Esta contradicción prueba que r < m. Por tanto, hemos hallado d y r tales que n = dm + r con r < m.
Supongamos finalmente que d1 y 0 ≤ r1 < m también satisfacen que n = d1m + r1. Supongamos que r1 ≥ r, por ejemplo. Como n = dm + r = d1m + r1, tendremos que 0 ≤ r1 − r = (d − d1)m ≤ r1 < m. Necesariamente, d − d1 = 0 y por tanto r1 = r.
Vemos que el algoritmo de división es una consecuencia del teorema del buen orden en ℕ. Otra consecuencia de este es el llamado principio de inducción. En la práctica funciona así: Queremos probar que a partir de un cierto número natural k (habitualmente el 0 o el 1), todos los naturales mayores o iguales que k satisfacen una cierta propiedad. La estrategia que seguimos es la siguiente: primero probamos que k satisface la propiedad; y después probamos que si n ≥ k la satisface, entonces n + 1 también la satisface. El principio de inducción garantiza, entonces, que cualquier n ≥ k satisface la propiedad. En efecto, sea A el conjunto de números naturales mayores o iguales que k que satisfacen la propiedad, y sea B = {n ∈ ℕ | n ≥ k}. Queremos probar que A = B. Como A ⊆ B, en caso contrario tendríamos que
∅ ≠ B − A = {b ∈ B | b ∉ A} ⊆ ℕ.
Por el teorema del buen orden en ℕ, sea n el menor elemento de B − A. Notar que n > k, pues k ∈ A (ya que k satisface la propiedad). Entonces n − 1 no está en B − A, pues n es el menor elemento de B − A. Así, n − 1 ≥ k satisface la propiedad y por hipótesis también la satisface
n = (n − 1) + 1.
Esta es la contradicción final.
Ejemplo 1.3 Probamos que
por inducción. Primero comprobamos que la igualdad es cierta para n = 1. Después suponemos que es cierta para n y la probamos para n + 1. Tenemos que
como queríamos probar.
El concepto fundamental en ℤ es la divisibilidad. Si a, b ∈ ℤ, con b ≠ 0, decimos que b divide a a si existe c ∈ ℤ tal que cb = a. A menudo se escribe b | a. En tal caso se dice que b es un divisor de a, y notamos que |c||b| = |a| (donde el valor absoluto |a| = a si a ≥ 0 y −a si a < 0). Si a ≠ 0, observamos que |b| ≤ |a|, por lo que concluimos que un entero a no cero solo tiene un número finito de divisores. Dados dos enteros n, m ∈ ℤ no cero, existe por tanto un mayor número natural 1 ≤ d que divide a ambos. Se dice que d es el máximo común divisor de n y m, y se escribe d = mcd(n, m). Si d = 1, entonces n y m se dice que son coprimos.
Ejercicio 1.5 Si a divide a b y a c, probar que a divide a b + c. Si a divide a b, entonces a divide a bz para todo z ∈ ℤ.
Teorema 1.13 (máximo comú divisor) Sean n, m ∈ ℤ no cero, y sea d = mcd(n, m).
(a) Entonces d es el menor elemento del conjunto
{un + vm | u, v ∈ ℤ, un + vm > 0}.
En particular, existen enteros u, v ∈ ℤ tales que d = un + vm.
(b) Si e divide a n y a m, entonces e divide a d.
Demostración. Consideramos el conjunto
A = {un + vm | u, v ∈ ℤ, un + vm > 0},
que claramente no es vacío. (Por ejemplo, si n > 0 y m < 0, n + m2 ∈ A). Sea f = un + vm el menor elemento de A. Por el algoritmo de división, n = qf + r con 0 ≤ r < f. Entonces,
r = n − qf = n − q(un + vm) = (1 − qu)n + (−vq)m.
Como r < f, esto solo puede ser cierto si r = 0. Deducimos que f divide a n y, análogamente, a m. En particular, f ≤ d, por definición de d. Como n = n1d, y m = m1d, tenemos que 0 < f = un1d + vm1d = (un1 + vm1)d ≥ d, y concluimos que d = f.
Para la parte (b), si e divide a n y a m, por el ejercicio 1.1, concluimos que e divide a un + vm = d.
