Divisibilidad কী?

Ejemplo 6.3 (Numeración posicional por divisiones sucesivas)

Escríbase $2026$ en base $7$. Divídase repetidamente por $7$, guardando los restos:

Leyendo los restos del último al primero: $2026 = (5\,6\,2\,3)_7$. Comprobación: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$. La unicidad de la división euclídea es exactamente lo que hace que cada cifra quede forzada: en cada paso, el resto es el único entero de $\intint06$ congruente con el valor actual módulo $7$, así que la escritura en base $7$ es única — hecho que se usa en silencio siempre que el problema del fin de semana manipula «las cifras de $n$ en base $p$».

Ejemplo 6.9 (Resolución de una ecuación diofántica lineal)

Hállense todos los $(x, y) \in \Z^2$ con $6x + 10y = 4$. Primero, el test de existencia: $\gcd(6, 10) = 2$ divide a $4$, luego hay soluciones (si el mcd no dividiese al miembro derecho, el izquierdo sería siempre múltiplo suyo y no habría ninguna). Divídase todo: $3x + 5y = 2$. Se ve una solución particular: $(x_0, y_0) = (-1, 1)$. Para la general, réstese: $3(x + 1) = -5(y - 1)$, luego $3 \mid 5(y-1)$, y el lema de Gauss ($\gcd(3,5) = 1$) da $3 \mid y - 1$: $y = 1 - 3k$ y después $x = -1 + 5k$. Recíprocamente, todo par así sirve:

El patrón es general: una solución particular más los múltiplos enteros de $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — la misma estructura de «particular más homogénea» que en el Capítulo 5, con el lema de Gauss haciendo el papel de la unicidad.