Divisibilidad

La divisibilidad es el punto de partida real de la teoría de números porque convierte a los enteros en un sistema con estructura: ya no miras números como “cantidades”, sino como piezas que encajan o no encajan entre sí. Con una sola estructura, a\mid b, puedes expresar desde criterios de simplificación y factorización hasta el corazón de algunos procedimientos como el algoritmo de Euclides, que hace posible calcular máximos comunes divisores en segundos incluso con números grandes. Además, es la base técnica de ideas que aparecen una y otra vez en matemática aplicada y computación: congruencias, aritmética modular, validaciones, códigos, y (más adelante) criptografía. Dominar divisibilidad es, en esencia, aprender a detectar patrones invisibles en los enteros y a convertirlos en procedimientos que funcionan siempre.

Objetivos de Aprendizaje
Al finalizar este apunte el estudiante será capaz de:

1. Comprender la relación de divisibilidad entre números enteros.
2. Comprender la definición de divisibilidad y sus propiedades.
3. Desarrollar demostraciones matemáticas de resultados y teoremas relacionados con la divisibilidad.

ÍNDICE DE CONTENIDOS
Definición de divisibilidad
Propiedades fundamentales de la divisibilidad
Ejercicios Propuestos

Definición de divisibilidad

La idea informal de “a divide a b” se vuelve precisa cuando la expresamos como una relación entre enteros. Diremos que un entero a divide a un entero b si b puede escribirse como un múltiplo exacto de a. Esta definición es la base del resto del apunte, porque transforma frases del tipo “encaja exacto” en un criterio verificable.

Definición. Sean a,b\in\mathbb{Z} con a\neq 0. Decimos que a divide a b, y escribimos a\mid b, si y solo si existe un entero k\in\mathbb{Z} tal que b=ka. En caso contrario, escribimos a\nmid b.

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

En esta definición, el número k se llama cociente (o factor) asociado a la divisibilidad. Por ejemplo, afirmar 6\mid 42 equivale a afirmar que existe k\in\mathbb{Z} tal que 42=6k; en este caso, basta tomar k=7.

Es importante considerar

• La condición a\neq 0 es esencial. Porque si intentáramos permitir a=0, la condición de divisibilidad exigiría que existiera k\in\mathbb{Z} tal que b=0\cdot k. Pero 0\cdot k=0 para todo k, así que la única posibilidad sería b=0. En ese caso, no habría un k “determinado” por la relación, ya que cualquier k\in\mathbb{Z} satisface 0=0\cdot k. Dicho de otra forma, la expresión informal k=b/a se vuelve k=0/0, que no está definida. Para evitar esta degeneración (donde la noción de cociente deja de ser significativa), se exige a\neq 0. Por este motivo no se considera válida la relación 0\mid b.
• En cambio, a\mid 0 es verdadero para todo a\in\mathbb{Z} con a\neq 0, porque basta tomar k=0 y se cumple 0=a\cdot 0.

Desde esta definición se desprende una equivalencia que usaremos de manera recurrente: decir que a\mid b es lo mismo que decir que b pertenece al conjunto de múltiplos enteros de a, es decir, b\in a\mathbb{Z}, donde a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}. Esta forma de escribirlo enfatiza que la divisibilidad no es un “truco”, sino una forma de describir subconjuntos muy estructurados dentro de \mathbb{Z}.

Propiedades fundamentales de la divisibilidad

• Reflexividad: a\mid a.
  Demostración:

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Neutro Multiplicativo en $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Int. Exitencial (1)}\\ (3) &\vdash a \mid a &\text{; Def. de divisibilidad (2)} \\ &\blacksquare & \end{array}

• Transitividad: si a\mid b y b\mid c, entonces a\mid c.

  Demostración:

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Def. de divisibilidad, Presunción}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Def. de divisibilidad, Presunción}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-Compactación(1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; De(3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; De(4)}\\ &\text{Álgebra dentro del cuantificador}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; De(5)}\\ &\text{Cerradura de $\mathbb{Z}$ para la multiplicación}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Def. de divisibilidad (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD(7)}\\ &\blacksquare& \end{array}

• Compatibilidad con suma y resta: si a\mid b y a\mid c, entonces a\mid (b+c) y a\mid (b-c).
  Demostración:

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Def. de divisibilidad, Presunción}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Def. de divisibilidad, Presunción}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-Compactación(1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; De(3)}\\ &\text{Álgebra dentro del cuantificador.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; De(4)}\\ &\text{Cerradura de $\mathbb{Z}$ para la suma.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Def, de divisibilidad (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD(6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; De(3)}\\ &\text{Álgebra dentro del cuantificador.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; De(8)}\\ &\text{Cerradura de $\mathbb{Z}$ para la resta.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Def, de divisibilidad (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD(10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{;$\wedge$-Int. en consecuente(7,11) }\\ &\blacksquare& \end{array}

• Compatibilidad con productos: si a\mid b, entonces a\mid (bc) para todo c\in\mathbb{Z}.
  Demostración:

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Def. de divisibilidad, Presunción}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; De(1), $\forall$-Int (c arbitrario)}\\ &\text{Álgebra en }\mathbb{Z}\text{ dentro del cuantificador existencial.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; De(2), cerradura: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Def. de divisibilidad (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD(4)}\\ &\blacksquare& \end{array}

Teorema: cota del divisor

Si b\neq 0 y a\mid b, entonces |a|\le |b|.

Demostración:

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Presunción} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Def. de divisibilidad, Presunción} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Prop. valor absoluto, De(2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; De(1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; De(4), si }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; De(5)} \\ &\blacksquare& \end{array}

Ejercicios Propuestos

1. Muestre que el teorema «cota del divisor» no es necesariamente cierto si b=0
2. Consideremos un conjunto A y una relación \rho sobre ese conjunto. Si los elementos x,y\in A fueran tales que x está relacionado con y mediante \rho, entonces se escribe x\rho y. La relación \rho se dice que es de orden parcial sobre A si:

   a)(\forall x\in A) (x\rho x),
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).

   Demuestra que la relación de divisibilidad es una relacíon de orden parcial sobre los números enteros.

3. Pruebe por inducción que si a\mid b_1, a\mid b_2, \cdots, a\mid b_n, entonces a\mid \sum_{i=1}^n b_i x_i para cualquier conjunto \{x_i\}_{i=1}^n \subset \mathbb{Z}. Ademas pruebe que si a\mid b_i, con i\in \{1,2,3,\cdots, n\} y c puede ser escrito como una combinación lineal de esos b_i, entonces a\mid c.
4. Si a\neq 0, muestre que el conjunto \{x\;:\; d\mid a\} es un conjunto finito.
5. Considere un n\in\mathbb{Z}^+ fijo, y sea

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   Pruebe:

   1. d\in S \leftrightarrow n/d\in S
   2. Si los elementos de S son puestos en orden creciente: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n, entonces los elementos correspondientes n\mid d_i con i \in \{1,2,\cdots, t\} están en orden decreciente.
6. Suponga que a,b\in\mathbb{Z}^+ y ab=c. Demuestre que \min\{a,b\}\le \sqrt{c}.
7. Un entero n se dice que es par si 2\mid n, e impar si 2\nmid n. Demuestre que la suma y la diferencia de:
   1. dos pares es un número par.
   2. dos impares es un número par.
   3. de un par y un impar es un número impar.
8. Si n es un impar distinto de \pm 1, prueba que n no puede dividir dos pares consecutivos.
9. Sean a,b,n\in\mathbb{Z} tales que |a-b|\lt |n|. Pruebe que n no puede dividir ni a a ni a b.
10. Suponga que a\in\mathbb{Z}. Pruebe que:
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. Sean a,b,c\in\mathbb{Z} y supongamos que c\neq 0. Muestre que ac\mid bc implica que a\mid b