O que é Divisibilidade?

Exemplo 6.3 (Numeração posicional por divisões sucessivas)

Escreva $2026$ na base $7$. Divida repetidamente por $7$, guardando os restos:

Lendo os restos do último ao primeiro: $2026 = (5\,6\,2\,3)_7$. Verificação: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$. A unicidade da divisão euclidiana é exatamente o que torna cada algarismo forçado: em cada passo, o resto é o único inteiro de $\intint06$ congruente ao valor corrente módulo $7$, de modo que a escrita na base $7$ é única — fato usado silenciosamente sempre que o problema de fim de semana manipula “os algarismos de $n$ na base $p$”.

Exemplo 6.9 (Resolvendo uma equação diofantina linear)

Encontre todos os $(x, y) \in \Z^2$ com $6x + 10y = 4$. Primeiro, o teste de existência: $\gcd(6, 10) = 2$ divide $4$, de modo que há soluções (se o mdc não dividisse o lado direito, o lado esquerdo seria sempre um múltiplo dele e não haveria nenhuma). Divida tudo: $3x + 5y = 2$. Uma solução particular está à vista: $(x_0, y_0) = (-1, 1)$. Para a geral, subtraia: $3(x + 1) = -5(y - 1)$, de modo que $3 \mid 5(y-1)$ e o lema de Gauss ($\gcd(3,5) = 1$) dá $3 \mid y - 1$: $y = 1 - 3k$, e então $x = -1 + 5k$. Reciprocamente, todo par desses serve:

O padrão é geral: uma solução particular mais os múltiplos inteiros de $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — a mesma estrutura “particular mais homogênea” do Capítulo 5, com o lema de Gauss desempenhando o papel da unicidade.