1. Definición básica

Un número entero (a) es divisible entre un número entero (b \neq 0) si existe un entero (k) tal que (a = b \cdot k). Se denota (b \mid a) y se lee: (b) divide a (a).

• Si (b \mid a), decimos que (a) es múltiplo de (b), y que (b) es divisor de (a).
• Si (b) no divide a (a), se escribe (b \nmid a).

2. Propiedades fundamentales

• Reflexividad: (a \mid a) para todo (a \neq 0).
• Transitividad: Si (a \mid b) y (b \mid c), entonces (a \mid c).
• Combinación lineal: Si (a \mid b) y (a \mid c), entonces (a \mid (mb + nc)) para cualesquiera enteros (m, n).
• Divisibilidad y producto: Si (a \mid b), entonces (a \mid bc) para cualquier entero (c).
• Igualdad y divisibilidad recíproca: Si (a \mid b) y (b \mid a), entonces (a = b) o (a = -b).
• Cotas: Si (a \mid b) y (b \neq 0), entonces (|a| \le |b|).

3. Algoritmo de la división

Dados (a) y (b) (con (b > 0)), existen únicos enteros (q) (cociente) y (r) (residuo) tales que:

[ a = bq + r, \quad 0 \le r < b. ]

• Si (r = 0), entonces (b \mid a).
• El residuo también se denota como (a \bmod b) (módulo).

4. Reglas de divisibilidad más comunes

5. Números primos y compuestos

• Primo: entero mayor que 1 con exactamente dos divisores positivos: 1 y sí mismo.
• Compuesto: entero mayor que 1 que no es primo, es decir, tiene más de dos divisores.
• Teorema fundamental de la aritmética: todo entero mayor que 1 se expresa de forma única como producto de primos (ignorando el orden). [ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} ]

6. Criba de Eratóstenes

Método para encontrar todos los primos menores que un número dado:

1. Escribir la lista de enteros desde 2 hasta (n).
2. Comenzar con el primer primo (2) y tachar todos sus múltiplos.
3. Tomar el siguiente número no tachado (primo) y tachar sus múltiplos.
4. Repetir hasta que el cuadrado del primo supere (n).

7. Máximo Común Divisor (MCD)

El MCD de dos o más enteros es el mayor divisor común positivo. Se denota (\gcd(a,b)).

• A partir de la factorización prima, se toman los factores comunes con el menor exponente.
• Si (\gcd(a,b) = 1), se dice que (a) y (b) son coprimos o primos entre sí.

Algoritmo de Euclides

Para (a > b):

1. Dividir (a) entre (b): (a = bq + r).
2. Si (r = 0), entonces (\gcd(a,b) = b).
3. Si (r \neq 0), reemplazar ((a,b)) por ((b,r)) y repetir.

8. Mínimo Común Múltiplo (mcm)

El mcm de dos o más enteros es el menor múltiplo común positivo. Se denota (\operatorname{lcm}(a,b)).

• Se obtiene tomando los factores primos comunes y no comunes con el mayor exponente.
• Relación con el MCD: [ \gcd(a,b) \cdot \operatorname{lcm}(a,b) = |a \cdot b| ]

9. Divisibilidad y congruencias

• (a) es congruente con (b) módulo (m) si (m \mid (a - b)). Se escribe (a \equiv b \pmod{m}).
• Las congruencias son útiles para simplificar problemas de divisibilidad y restos.

10. Ejemplos rápidos

• Verificar si 12345 es divisible entre 3: suma de cifras (1+2+3+4+5=15), que es múltiplo de 3. Sí.
• Calcular (\gcd(48, 36)): (48 = 2^4 \cdot 3), (36 = 2^2 \cdot 3^2). Factores comunes: (2^2 \cdot 3 = 12).
• Calcular (\operatorname{lcm}(4,6)): (4=2^2), (6=2\cdot3). Tomamos (2^2\cdot3 = 12).