Matematika Sekolah Dasar dan Menengah · Grades 1–9

64Aritmetika: Pembagi dan Bilangan Prima

Aritmetika mempelajari bilangan bulat dan cara bilangan yang satu membagi yang lain. Tokoh utamanya adalah bilangan prima, yaitu balok pembangun yang darinya setiap bilangan bulat disusun lewat perkalian. Bab ini berakhir dengan faktor persekutuan terbesar, alat yang tepat untuk menyederhanakan pecahan sekali untuk selamanya. Kisah ini berlanjut, jauh lebih jauh, di buku Sekolah Menengah dan sesudahnya.

64.1 Pembagi dan kelipatan

Definisi 64.1 (Pembagi, kelipatan)

Misalkan $a$ dan $b$ bilangan bulat positif. Kita katakan bahwa $b$ membagi $a$ (atau bahwa $b$ pembagi $a$ , atau bahwa $a$ adalah kelipatan $b$ ) ketika $a = b \times k$ untuk suatu bilangan bulat $k$ — yaitu ketika pembagian $a$ oleh $b$ meninggalkan sisa $0$ .

Contoh 64.2

Pembagi $24$ adalah $1, 2, 3, 4, 6, 8, 12, 24$ — semuanya datang berpasangan yang hasil kalinya $24$ : $(1,24)$ , $(2,12)$ , $(3,8)$ , $(4,6)$ . Kelipatan $7$ adalah $7, 14, 21, 28, \dots$

Proposisi 64.3 (Aturan keterbagian)

Sebuah bilangan bulat habis dibagi:

$2$ ketika angka terakhirnya genap ( $0, 2, 4, 6, 8$ );
$5$ ketika angka terakhirnya $0$ atau $5$ ;
$10$ ketika angka terakhirnya $0$ ;
$3$ (berturut-turut $9$ ) ketika jumlah angkanya habis dibagi $3$ (berturut-turut $9$ );
$4$ ketika dua angka terakhirnya membentuk bilangan yang habis dibagi $4$ .

Bukti. Diterima tanpa bukti pada tingkat ini. ∎

Contoh 64.4

$7\,215$ berakhir dengan $5$ : jadi habis dibagi $5$ . Jumlah angkanya $7 + 2 + 1 + 5 = 15$ , yang habis dibagi $3$ tetapi tidak habis dibagi $9$ : jadi $7\,215$ habis dibagi $3$ , tidak habis dibagi $9$ . Memang $7\,215 = 3 \times 5 \times 481$ .

64.2 Bilangan prima

Definisi 64.5 (Bilangan prima)

Bilangan prima adalah bilangan bulat $\geq 2$ yang pembaginya hanya $1$ dan dirinya sendiri. Bilangan prima di bawah $30$ adalah

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

Bilangan $1$ bukan prima (menurut kesepakatan), dan bilangan bulat $\geq 2$ yang bukan prima disebut komposit.

Teorema 64.6 (Pemfaktoran prima)

Setiap bilangan bulat $\geq 2$ adalah hasil kali bilangan prima, dan pemfaktoran itu tunggal kecuali urutan faktornya.

Bukti. Diterima tanpa bukti pada tingkat ini. ∎

Metode 64.7 (Memfaktorkan bilangan bulat)

Bagilah dengan bilangan prima terkecil yang mungkin, berulang-ulang, sampai mencapai $1$ :

cobalah $2$ selama bilangannya genap;
lalu cobalah $3$ , lalu $5$ , lalu $7$ , … (hanya yang prima);
berhentilah ketika hasil baginya $1$ ; kumpulkan faktornya beserta eksponennya.

Cukup mencoba bilangan prima $p$ dengan $p^2$ tidak melampaui bilangan yang sedang dikerjakan: kalau tidak ada yang membaginya, maka bilangannya sendiri prima.

Contoh 64.8

Faktorkan $360$ , satu pembagian setiap kalinya:

360 = 2 \times 180, \quad 180 = 2 \times 90, \quad 90 = 2 \times 45, \quad 45 = 3 \times 15, \quad 15 = 3 \times 5,

jadi

360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5 .

Pohon faktor 360: tiap langkahnya memisahkan faktor prima terkecilnya (berwarna merah). Membaca daun merahnya dan 5 yang terakhir: 360 = 23 × 32 × 5. — Pohon faktor $360$ : tiap langkahnya memisahkan faktor prima terkecilnya (berwarna merah). Membaca daun merahnya dan $5$ yang terakhir: $360 = 2^3 \times 3^2 \times 5$ .

Teorema 64.9 (Euclid)

Bilangan prima ada tak berhingga banyaknya.

Bukti. Andaikan banyaknya berhingga saja, katakanlah $p_1, p_2, \dots, p_k$ , lalu tinjaulah

N = p_1 \times p_2 \times \dots \times p_k + 1 .

Membagi $N$ dengan $p_i$ mana pun meninggalkan sisa $1$ , jadi tidak ada $p_i$ yang membagi $N$ . Tetapi $N \geq 2$ punya sedikitnya satu pembagi prima (Teorema 64.6) — yaitu bilangan prima yang tidak ada dalam daftar kita. Kontradiksi: tidak ada daftar berhingga yang dapat memuat semua bilangan primanya. ∎

64.3 Faktor persekutuan terbesar

Definisi 64.10 (FPB)

Faktor persekutuan terbesar dua bilangan bulat positif $a$ dan $b$ , yang ditulis $\gcd(a, b)$ , adalah bilangan bulat terbesar yang membagi keduanya. Ketika $\gcd(a, b) = 1$ , kedua bilangan bulatnya disebut saling prima: keduanya tidak berbagi pembagi selain $1$ .

Contoh 64.11

Pembagi $18$ : $1, 2, 3, 6, 9, 18$ . Pembagi $24$ : $1, 2, 3, 4, 6, 8, 12, 24$ . Pembagi bersamanya: $1, 2, 3, 6$ ; jadi $\gcd(18, 24) = 6$ . Bilangan bulat $15$ dan $28$ saling prima.

Proposisi 64.12 (FPB dari pemfaktorannya)

FPB dua bilangan bulat adalah hasil kali bilangan prima yang muncul pada kedua pemfaktorannya, masing-masing diambil dengan eksponen yang lebih kecil dari kedua eksponennya.

Bukti. Diterima tanpa bukti pada tingkat ini. ∎

Contoh 64.13

$360 = 2^3 \times 3^2 \times 5$ dan $84 = 2^2 \times 3 \times 7$ . Bilangan prima bersamanya: $2$ (eksponennya $3$ dan $2$ : ambil $2$ ) dan $3$ (eksponennya $2$ dan $1$ : ambil $1$ ). Jadi

\gcd(360, 84) = 2^2 \times 3 = 12 .

Teorema 64.14 (Algoritma Euclid)

Kalau $a = bq + r$ adalah pembagian $a$ oleh $b$ dengan sisa $r$ , maka

\gcd(a, b) = \gcd(b, r).

Dengan mengulang pembagiannya sampai sisanya $0$ , FPB dari $a$ dan $b$ adalah sisa terakhir yang bukan nol.

Bukti. Dari $a = bq + r$ : setiap bilangan bulat yang membagi $b$ dan $r$ membagi $bq + r = a$ ; dan dari $r = a - bq$ : setiap bilangan bulat yang membagi $a$ dan $b$ membagi $r$ . Jadi pasangan $(a, b)$ dan $(b, r)$ punya pembagi bersama yang persis sama — khususnya yang terbesarnya sama. Karena sisanya menurun secara tegas, algoritmanya berhenti, dan $\gcd(x, 0) = x$ memberi sisa terakhir yang bukan nol. ∎

Contoh 64.15

Hitunglah $\gcd(1071, 462)$ :

\begin{align*} 1071 &= 462 \times 2 + 147, \\ 462 &= 147 \times 3 + 21, \\ 147 &= 21 \times 7 + 0 . \end{align*}

Sisa terakhir yang bukan nol adalah $21$ : $\gcd(1071, 462) = 21$ .

Metode 64.16 (Menyederhanakan pecahan sepenuhnya)

Untuk menulis $\dfrac ab$ sesederhana mungkin:

hitunglah $d = \gcd(a, b)$ , misalnya dengan algoritma Euclid;
bagilah pembilang dan penyebutnya dengan $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
pecahan yang dihasilkan bersifat tak tersederhanakan: pembilang dan penyebutnya saling prima.

Contoh 64.17

$\dfrac{462}{1071} = \dfrac{462 \div 21}{1071 \div 21} = \dfrac{22}{51}$ , dan $\gcd(22, 51) = 1$ : jadi tak tersederhanakan.

64.4 Latihan

Latihan 64.1 ★

Sebutkan semua pembagi $36$ , pembagi $45$ , dan pembagi $17$ .

Solusi

Solusi Latihan 64.1.

Pembagi $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$ . Pembagi $45$ : $1, 3, 5, 9, 15, 45$ . Pembagi $17$ : hanya $1$ dan $17$ ( $17$ adalah prima).

Latihan 64.2 ★

Dengan memakai aturan keterbagiannya, tentukan apakah $2\,346$ habis dibagi $2$ , $3$ , $4$ , $5$ , dan $9$ .

Solusi

Solusi Latihan 64.2.

$2\,346$ berakhir dengan $6$ : habis dibagi $2$ , tidak habis dibagi $5$ . Jumlah angkanya $2 + 3 + 4 + 6 = 15$ : habis dibagi $3$ , tidak habis dibagi $9$ . Dua angka terakhirnya $46$ , dan $46 = 4 \times 11 + 2$ tidak habis dibagi $4$ : jadi $2\,346$ tidak habis dibagi $4$ .

Latihan 64.3 ★

Berikan pemfaktoran prima $72$ , $150$ , $210$ dan $121$ .

Solusi

Solusi Latihan 64.3.

$72 = 2^3 \times 3^2$ ; $150 = 2 \times 3 \times 5^2$ ; $210 = 2 \times 3 \times 5 \times 7$ ; $121 = 11^2$ .

Latihan 64.4 ★

Apakah $101$ prima? Apakah $91$ ? Apakah $143$ ? Berilah alasan dengan memakai aturan berhenti pada Metode 64.7.

Solusi

Solusi Latihan 64.4.

$101$ : ujilah bilangan prima $p$ dengan $p^2 \leq 101$ , yaitu $2, 3, 5, 7$ . Tidak ada yang membagi $101$ (ganjil, jumlah angkanya $2$ , tidak berakhir dengan $0/5$ , dan $101 = 7 \times 14 + 3$ ): jadi $101$ prima.

$91 = 7 \times 13$ : bukan prima.

$143 = 11 \times 13$ : bukan prima.

Latihan 64.5 ★

Hitunglah $\gcd(48, 60)$ dengan dua cara: dengan menyebutkan pembagi bersamanya, dan dari pemfaktoran primanya.

Solusi

Solusi Latihan 64.5.

Pembagi bersama $48$ dan $60$ : pembagi 48 adalah $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ ; pembagi $60$ adalah $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ ; yang bersamanya adalah $1, 2, 3, 4, 6, 12$ , jadi $\gcd(48,60) = 12$ .

Dengan pemfaktoran: $48 = 2^4 \times 3$ dan $60 = 2^2 \times 3 \times 5$ ; bilangan prima bersamanya dengan eksponen yang lebih kecil: $2^2 \times 3 = 12$ .

Latihan 64.6 ★★

Pakailah algoritma Euclid untuk menghitung $\gcd(255, 154)$ , lalu $\gcd(1053, 325)$ . Tulislah tiap baris pembagiannya.

Solusi

Solusi Latihan 64.6.

$\gcd(255, 154)$ :

\begin{align*} 255 &= 154 \times 1 + 101, \\ 154 &= 101 \times 1 + 53, \\ 101 &= 53 \times 1 + 48, \\ 53 &= 48 \times 1 + 5, \\ 48 &= 5 \times 9 + 3, \\ 5 &= 3 \times 1 + 2, \\ 3 &= 2 \times 1 + 1, \\ 2 &= 1 \times 2 + 0 . \end{align*}

Sisa terakhir yang bukan nol: $\gcd(255, 154) = 1$ (keduanya saling prima).

$\gcd(1053, 325)$ :

\begin{align*} 1053 &= 325 \times 3 + 78, \\ 325 &= 78 \times 4 + 13, \\ 78 &= 13 \times 6 + 0 . \end{align*}

$\gcd(1053, 325) = 13$ .

Latihan 64.7 ★★

Jadikan pecahan $\dfrac{588}{504}$ tak tersederhanakan. (Hitunglah FPB-nya dengan cara pilihanmu, lalu bagilah.)

Solusi

Solusi Latihan 64.7.

Algoritma Euclid: $588 = 504 \times 1 + 84$ ; $504 = 84 \times 6 + 0$ : jadi $\gcd(588, 504) = 84$ . Lalu

\frac{588}{504} = \frac{588 \div 84}{504 \div 84} = \frac{7}{6},

yang tak tersederhanakan.

Latihan 64.8 ★★

Seorang penjual bunga punya $84$ mawar dan $126$ tulip lalu ingin membuat rangkaian yang identik, dengan memakai semua bunganya, dan dengan rangkaian sebanyak mungkin. Berapa rangkaian yang dapat dibuatnya, dan apa isi masing-masingnya?

Solusi

Solusi Latihan 64.8.

Banyaknya rangkaian harus membagi $84$ dan $126$ ; yang terbesar mungkin adalah $\gcd(84, 126)$ . Pemfaktorannya: $84 = 2^2 \times 3 \times 7$ , $126 = 2 \times 3^2 \times 7$ , jadi FPB-nya $2 \times 3 \times 7 = 42$ . Ia dapat membuat $42$ rangkaian, yang masing-masing berisi $\frac{84}{42} = 2$ mawar dan $\frac{126}{42} = 3$ tulip.

Latihan 64.9 ★★

Dua kapal feri berangkat dari dermaga yang sama pukul 8:00. Yang satu berangkat tiap $24$ menit, yang lain tiap $36$ menit. Pukul berapa keduanya berikutnya berangkat bersama-sama? (Carilah kelipatan bersama terkecil dari $24$ dan $36$ ; pemfaktorannya membantu.)

Solusi

Solusi Latihan 64.9.

Kita perlu kelipatan bersama terkecilnya. $24 = 2^3 \times 3$ dan $36 = 2^2 \times 3^2$ ; dengan mengambil tiap bilangan prima beserta eksponen yang lebih besar: $\lcm = 2^3 \times 3^2 = 72$ . Ferinya berikutnya berangkat bersama $72$ menit sesudah pukul 8:00, yaitu pukul 9:12.

Latihan 64.10 ★★★

Misalkan $n$ sebuah bilangan bulat positif.

Tunjukkan bahwa $\gcd(n, n+1) = 1$ (bilangan bulat yang berurutan selalu saling prima).
Simpulkan bahwa pecahan $\dfrac{n}{n+1}$ selalu tak tersederhanakan.

Solusi

Solusi Latihan 64.10.

1. Setiap pembagi bersama $d$ dari $n$ dan $n+1$ juga membagi selisihnya $(n+1) - n = 1$ , jadi $d = 1$ : yaitu $\gcd(n, n+1) = 1$ .

2. Sebuah pecahan tak tersederhanakan persis ketika pembilang dan penyebutnya saling prima, dan itulah keadaan $n$ dan $n + 1$ menurut bagian 1.

64.5 Soal: Kendi air, jangkrik dan seratus loker

Soal 64.1

Soal akhir pekan — FPB memutuskan takaran mana yang dapat diukur dua kendi; bilangan prima melindungi jangkrik; dan loker yang tetap terbuka adalah kuadrat sempurna

Tiga teka-teki yang tampak seperti tebakan padahal sungguh-sungguh aritmetika: menakar air dengan kendi tanpa tanda ukur (yaitu FPB dalam samaran), daur hidup serangga yang berkembang menjadi bilangan prima, dan sebuah lorong terkenal berisi seratus loker yang keadaan akhirnya ditentukan dengan membilang pembagi. Semuanya berjalan dengan mesin bab ini: keterbagian, pemfaktoran prima (Teorema 64.6) dan algoritma Euclid (Teorema 64.14).

Bagian I — Kendi airnya. Kamu berdiri di sebuah pancuran dengan dua kendi tanpa tanda ukur, berukuran $5$ L dan $3$ L. Gerakan yang diizinkan: mengisi sebuah kendi sampai penuh, mengosongkan sebuah kendi sepenuhnya, menuang satu kendi ke kendi yang lain sampai sumbernya kosong atau tujuannya penuh.

Takarlah tepat $1$ L. (Uraikan urutan gerakanmu dan isi kedua kendinya sesudah masing-masingnya.)
Takarlah tepat $4$ L — yaitu teka-teki dari sebuah film laga yang terkenal. (Hal itu dapat dilakukan dalam enam gerakan.)
Bilangan bulat liter yang mana dari $1$ sampai $8$ yang dapat kamu tunjukkan (dalam satu kendi, atau terbagi pada keduanya)? Lengkapilah daftarnya, dengan memakai ulang urutanmu.
Kendi yang baru: $6$ L dan $4$ L. Cobalah menakar $1$ L — lalu jelaskan mengapa hal itu sia-sia: periksalah bahwa masing-masing dari ketiga gerakan yang diizinkan menjaga isi tiap kendinya tetap kelipatan $2$ , jadi setiap takaran yang tercapai bernilai genap.
Alasan pada pertanyaan 4 berlaku umum: dengan kendi $a$ dan $b$ liter, setiap takaran yang tercapai adalah kelipatan $\gcd(a, b)$ . Hitunglah $\gcd(6, 4)$ dan $\gcd(5, 3)$ , lalu katakan apa yang diramalkan hukumnya untuk tiap pasangan kendinya.

Bagian II — Euclid di pancuran.

Hitunglah dengan algoritma Euclid: $\gcd(91, 65)$ dan $\gcd(2\,026, 46)$ .
Jelaskan, dengan kata-katamu sendiri, mengapa takaran yang muncul pada kendinya adalah sisa milik Euclid dalam samaran: dengan kendi $13$ L dan $5$ L, isilah kendi kecilnya berulang-ulang lalu tuangkan ke kendi besarnya (dengan mengosongkan kendi besarnya setiap kali ia penuh). Takaran baru yang mana yang muncul lebih dahulu — lalu bandingkan semuanya dengan sisa pada algoritma Euclid untuk $(13, 5)$ .
Simpulkan jawaban sang juara: dengan kendi $13$ dan $5$ liter, dapatkah kamu menakar tepat $1$ L? Berilah alasan dalam satu baris dengan pertanyaan 5 dan $\gcd(13, 5)$ .
Bukti kilat tentang saling prima dengan gaya Latihan 64.10: tunjukkan bahwa $\gcd(n, 2n + 1) = 1$ untuk setiap bilangan bulat positif $n$ . (Apa yang harus dibagi oleh pembagi bersama $n$ dan $2n + 1$ ?)
Dua bus berangkat bersama dari terminal pukul 7:00; yang satu berangkat tiap $12$ menit, yang lain tiap $18$ . Sebutkan waktu keberangkatan berikutnya untuk masing-masingnya lalu carilah saat pertama keduanya berangkat bersama lagi. Periksalah pada contoh ini hukum yang indah: (kelipatan bersama pertamanya) $\times$ $\gcd$ $=$ hasil kali kedua bilangannya — lalu ujilah sekali lagi pada $5$ dan $3$ .

Bagian III — Jangkrik, pembagi dan loker.

Jangkrik Amerika Utara tertentu keluar hanya tiap $17$ tahun; andaikan populasi pemangsanya memuncak tiap $4$ tahun. Kalau keduanya terjadi tahun ini, berapa tahun lagi kemunculan jangkriknya berikutnya berbarengan dengan puncaknya? Pertanyaan yang sama kalau daur jangkriknya $16$ tahun — seberapa sering mereka lalu dibantai? Jelaskan dalam satu kalimat mengapa evolusi mendorong daurnya ke panjang yang prima.
Dengan memakai pemfaktoran $360 = 2^3 \times 3^2 \times 5$ , bilanglah pembagi $360$ tanpa menyebutkannya satu per satu: sebuah pembagi memilih eksponen untuk $2$ (empat pilihan: $0, 1, 2, 3$ ), satu untuk $3$ , satu untuk $5$ . Berapa pembagi seluruhnya?
Tunjukkan bahwa pada pemfaktoran kuadrat sempurna $n = m^2$ , setiap bilangan primanya membawa eksponen yang genap. Simpulkan, tanpa menghitung akar kuadrat apa pun, bahwa $360$ bukan kuadrat sempurna.
Pasangkan tiap pembagi $d$ dari $n$ dengan pasangannya $\frac{n}{d}$ (untuk $n = 36$ : $1 \leftrightarrow 36$ , $2 \leftrightarrow 18$ , $3 \leftrightarrow 12$ , $4 \leftrightarrow 9$ , $6 \leftrightarrow 6$ ). Kapan sebuah pembagi menjadi pasangannya sendiri? Simpulkan kriterianya: $n$ punya banyak pembagi yang ganjil persis ketika $n$ adalah kuadrat sempurna. Periksalah pada $36$ dan pada $360$ .
Seratus lokernya. Loker $1$ sampai $100$ bermula tertutup. Murid $1$ membalik keadaan setiap loker; murid $2$ membalik loker $2, 4, 6, \dots$ ; murid $k$ membalik kelipatan $k$ ; dan seterusnya sampai murid $100$ . Jelaskan murid mana saja yang menyentuh loker $n$ , berapa kali loker itu terbalik keadaannya, dan — dengan memakai pertanyaan 14 — loker mana persisnya yang berakhir terbuka. Berapa banyak yang terbuka?

Solusi

Solusi Soal 64.1.

1. Isilah kendi $3$ lalu tuangkan ke kendi $5$ (isinya $0/3 \to 3$ pada yang besar). Isilah kendi $3$ lagi lalu tuangkan ke kendi $5$ sampai penuh: kendi besarnya hanya menerima $2$ lagi, sehingga meninggalkan

3 - 2 = 1 \text{ L pada kendi kecilnya.}

Gerakannya: isi $3$ ; tuang $3 \to 5$ ; isi $3$ ; tuang $3 \to 5$ .

2. Isilah kendi $5$ ; tuangkan ke kendi $3$ (sehingga tersisa $2$ pada yang besar); kosongkan kendi $3$ ; tuangkan $2$ -nya ke kendi $3$ ; isilah kendi $5$ ; tuangkan ke kendi $3$ sampai penuh — kendi itu menerima $1$ , sehingga meninggalkan $\mathbf{4}$ L pada kendi besarnya. Enam gerakan.

3. Semuanya: $1$ (pertanyaan 1), $2$ (sesudah dua gerakan pada pertanyaan 2), $3$ dan $5$ (sekali pengisian), $4$ (pertanyaan 2), $6 = 3 + 3$ (kendi kecil yang penuh ditambah $3$ yang dituang ke yang besar), $7 = 5 + 2$ , $8 = 5 + 3$ (keduanya penuh). Setiap takaran bulat dari $1$ sampai $8$ L dapat ditakar dengan kendi $5$ dan $3$ .

4. Awalnya: kedua kendinya memuat $0$ , yaitu kelipatan $2$ . Mengisi menetapkan isinya menjadi $6$ atau $4$ : genap. Mengosongkan menetapkannya menjadi $0$ : genap. Menuang memindahkan sebagian airnya antara kendi yang isinya genap, dan banyaknya yang dituang adalah selisih bilangan genap (ruang yang tersisa, atau banyaknya yang tersedia): jadi semua isinya tetap genap selamanya. Sasaran ganjil seperti $1$ L tidak tercapai.

5. $\gcd(6, 4) = 2$ : jadi hanya takaran genap — yang dibenarkan pertanyaan 4. $\gcd(5, 3) = 1$ : setiap takaran bulat diizinkan hukumnya, dan pertanyaan 3 mewujudkan semuanya. FPB itu persis satuan ukur kedua kendinya.

6. $91 = 1 \times 65 + 26$ ; $65 = 2 \times 26 + 13$ ; $26 = 2 \times 13 + 0$ : jadi $\gcd(91, 65) = 13$ . Dan $2\,026 = 44 \times 46 + 2$ ; $46 = 23 \times 2 + 0$ : jadi $\gcd(2\,026, 46) = 2$ .

7. Menuang kendi $5$ ke kendi $13$ berulang-ulang: sesudah dua kali pengisian kendi besarnya memuat $10$ ; pengisian ketiganya hanya muat $3$ , sehingga meninggalkan $5 - 3 = 2$ pada kendi kecilnya — sisa $13$ dibagi $5$ adalah $3$ , dan takaran $3$ (ruangnya) dan $2$ (kelebihannya) persis bilangan milik Euclid ( $13 = 2 \times 5 + 3$ , $5 = 1 \times 3 + 2$ ). Kalau dilanjutkan, $3 - 2 = 1$ muncul: yaitu sisa berikutnya pada algoritmanya. Pancurannya menjalankan pembagian Euclid dengan air.

8. $\gcd(13, 5) = 1$ , jadi hukum pada pertanyaan 5 mengizinkan setiap takaran bulat — dan air terjun pada pertanyaan 7 memang menghasilkan $1$ L. Ya, dapat.

9. Pembagi bersama $n$ dan $2n + 1$ membagi $2n + 1 - 2 \times n = 1$ : jadi ia haruslah $1$ . Karena itu $\gcd(n, 2n+1) = 1$ selalu.

10. Bus A: 7:12, 7:24, 7:36, 7:48, 8:00 …; bus B: 7:18, 7:36, 7:54 … Keberangkatan bersama yang pertama: 7:36, sesudah $36$ menit — yaitu kelipatan bersama pertama $12$ dan $18$ . Hukumnya: $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times 18$ . Untuk $5$ dan $3$ : kelipatan bersama pertamanya $15$ , dan $15 \times \gcd(5,3) = 15 \times 1 = 15 = 5 \times 3$ .

11. Dengan daur $17$ tahun: keberbarengan berikutnya adalah kelipatan bersama pertama $17$ dan $4$ ; karena $\gcd(17, 4) = 1$ , itu berarti $17 \times 4 = 68$ tahun — jangkriknya bertemu puncaknya sekali dalam empat kemunculan. Dengan daur $16$ tahun: $16$ adalah kelipatan $4$ , jadi setiap kemunculannya mengenai sebuah puncak. Panjang daur yang prima tidak berbagi faktor dengan daur pemangsa yang lebih pendek mana pun, sehingga mendorong keberbarengannya sejauh mungkin: aritmetika sebagai penyamaran.

12. Empat pilihan eksponen untuk $2$ , tiga untuk $3$ , dua untuk $5$ : jadi $4 \times 3 \times 2 = 24$ pembagi.

13. Kalau $m = 2^{a} \times 3^{b} \times \cdots$ , maka $m^2 = 2^{2a} \times 3^{2b} \times \cdots$ : setiap eksponennya berlipat dua, jadi genap. Pada $360 = 2^3 \times 3^2 \times 5$ , eksponen $2$ dan eksponen $5$ ganjil: jadi $360$ bukan kuadrat sempurna.

14. Sebuah pembagi menjadi pasangannya sendiri persis ketika $d = \frac nd$ , yaitu $n = d^2$ : hanya kuadrat yang punya pembagi tengah seperti itu. Untuk semua $n$ yang lain pembaginya terbelah menjadi pasangan, jadi banyaknya genap. Jadi: banyak pembagi yang ganjil $\Leftrightarrow$ kuadrat sempurna. Periksa: $36$ punya pembagi $1, 2, 3, 4, 6, 9, 12, 18, 36$ — sembilan buah, yaitu ganjil, dan $36 = 6^2$ ; sedangkan $360$ punya $24$ (pertanyaan 12), yaitu genap, dan bukan kuadrat (pertanyaan 13).

15. Loker $n$ terbalik keadaannya sekali oleh tiap murid $k$ yang nomornya membagi $n$ : seluruhnya sebanyak pembagi yang dipunyai $n$ . Sebuah loker berakhir terbuka ketika keadaannya terbalik sebanyak bilangan ganjil kali — menurut pertanyaan 14, persis ketika $n$ adalah kuadrat sempurna. Loker yang terbuka: $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$ — sepuluh buah.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium