What is Divisibility?

Example 6.3 (Positional numeration by repeated division)

Write $2026$ in base $7$. Divide repeatedly by $7$, keeping the remainders:

Reading the remainders from last to first: $2026 = (5\,6\,2\,3)_7$. Check: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$. The uniqueness of Euclidean division is exactly what makes each digit forced: at every step the remainder is the only integer in $\intint06$ congruent to the current value mod $7$, so base-$7$ writing is unique — the fact silently used whenever the weekend problem manipulates “the digits of $n$ in base $p$”.

Example 6.9 (Solving a linear Diophantine equation)

Find all $(x, y) \in \Z^2$ with $6x + 10y = 4$. First, the existence test: $\gcd(6, 10) = 2$ divides $4$, so solutions exist (if the gcd did not divide the right-hand side, the left side would always be a multiple of it and there would be none). Divide through: $3x + 5y = 2$. A particular solution is visible: $(x_0, y_0) = (-1, 1)$. For the general one, subtract: $3(x + 1) = -5(y - 1)$, so $3 \mid 5(y-1)$, and Gauss’s lemma ($\gcd(3,5) = 1$) gives $3 \mid y - 1$: $y = 1 - 3k$, then $x = -1 + 5k$. Conversely every such pair works:

The pattern is general: one particular solution plus the integer multiples of $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — the same “particular plus homogeneous” structure as in Chapter 5, with Gauss’s lemma playing the uniqueness role.