Apa itu Keterbagian?

Contoh 6.3 (Penomoran posisional lewat pembagian berulang)

Tulis $2026$ dalam basis $7$. Bagilah berulang kali dengan $7$, sambil menyimpan sisanya:

Dengan membaca sisanya dari yang terakhir ke yang pertama: $2026 = (5\,6\,2\,3)_7$. Periksa: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$. Ketunggalan pembagian Euclid itulah yang membuat setiap angkanya terpaksa demikian: pada setiap langkah sisanya adalah satu-satunya bilangan bulat di $\intint06$ yang kongruen dengan nilai berjalannya modulo $7$, sehingga penulisan basis $7$ bersifat tunggal — fakta yang dipakai diam-diam setiap kali soal akhir pekan mengolah “angka $n$ dalam basis $p$”.

Contoh 6.9 (Menyelesaikan persamaan Diophantus linear)

Carilah semua $(x, y) \in \Z^2$ dengan $6x + 10y = 4$. Pertama, uji keberadaannya: $\gcd(6, 10) = 2$ membagi $4$, jadi penyelesaiannya ada (seandainya FPB-nya tidak membagi ruas kanan, ruas kirinya akan selalu menjadi kelipatannya dan tak akan ada penyelesaian). Bagilah seluruhnya: $3x + 5y = 2$. Sebuah penyelesaian khusus terlihat: $(x_0, y_0) = (-1, 1)$. Untuk yang umum, kurangkan: $3(x + 1) = -5(y - 1)$, jadi $3 \mid 5(y-1)$, dan lema Gauss ($\gcd(3,5) = 1$) memberikan $3 \mid y - 1$: sehingga $y = 1 - 3k$, lalu $x = -1 + 5k$. Sebaliknya setiap pasangan semacam itu memenuhi:

Polanya berlaku umum: satu penyelesaian khusus ditambah kelipatan bulat $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — yaitu struktur “khusus ditambah homogen” yang sama seperti pada Bab 5, dengan lema Gauss memainkan peran ketunggalannya.