Divisibilidad

Teoría

La divisibilidad es la relación fundamental en la teoría de números que describe cómo un entero puede dividirse exactamente entre otro. De forma técnica, para enteros $a$ y $b$ con $a \neq 0$, decimos que $a$ divide a $b$ (se escribe $a \mid b$) si existe un entero $k$ tal que $b = ak$. Este concepto va más allá de la aritmética simple para explorar la estructura multiplicativa de los enteros. Sirve como la base para temas más avanzados como la factorización prima, la aritmética modular y las ecuaciones diofánticas.

En las olimpiadas de matemáticas, la divisibilidad es clave para simplificar expresiones complejas y resolver ecuaciones sobre los enteros. El poder de la divisibilidad está en sus propiedades de linealidad y orden. Por ejemplo, si un número divide a otros dos, también tiene que dividir a cualquier combinación lineal entera de ellos. Esta idea te permite reducir números grandes a componentes más manejables, usando seguido el Máximo Común Divisor (MCD) y el Mínimo Común Múltiplo (mcm) para analizar cómo se relacionan los enteros.

La mejor forma de entender la intuición detrás de la divisibilidad es a través del Algoritmo de la División. Aunque no todas las divisiones dan un entero, el Algoritmo de la División garantiza que cualquier entero se puede dividir entre un entero distinto de cero para obtener un cociente único y un residuo. Esto cierra la brecha entre la divisibilidad perfecta y la "distancia" al siguiente múltiplo, dándote la base rigurosa para la aritmética modular y el Algoritmo de Euclides.

Fórmulas Clave

Definición de Divisibilidad $$a \mid b \iff \exists k \in \mathbb{Z} \text{ tal que } b = ak$$

Propiedades Fundamentales

• Reflexividad: $a \mid a$.
• Transitividad: Si $a \mid b$ y $b \mid c$, entonces $a \mid c$.
• Linealidad: Si $a \mid b$ y $a \mid c$, entonces para cualquier par de enteros $x, y$: $$a \mid (bx + cy)$$
• Comparación: Si $a \mid b$ y $b \neq 0$, entonces $|a| \le |b|$.

El Algoritmo de la División Para cualquier par de enteros $a$ y $b$ con $b > 0$, existen enteros únicos $q$ (cociente) y $r$ (residuo) tales que: $$a = bq + r, \quad 0 \le r < b$$

Relación entre MCD y mcm Para enteros positivos $a$ y $b$: $$\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$$

Identidad de Bézout Sea $d = \gcd(a, b)$. Existen enteros $x$ e $y$ tales que: $$ax + by = d$$ Además, todos los enteros de la forma $ax + by$ son múltiplos de $d$.

Lema de Euclides Si