---
title: "Aritmetika: Pembagi dan Bilangan Prima"
book: "Matematika Sekolah Dasar dan Menengah"
subject: math
language: id
chapter: 64
exercises: 10
source: https://one-course.com/books/math/1/id/chapter/64-aritmetika-pembagi-dan-bilangan-prima
---

# Bab 64 — Aritmetika: Pembagi dan Bilangan Prima

Aritmetika mempelajari bilangan bulat dan cara bilangan yang satu membagi yang lain. Tokoh utamanya adalah [bilangan prima](#def-g9-arith-prime), yaitu balok pembangun yang darinya setiap bilangan bulat disusun lewat perkalian. Bab ini berakhir dengan [faktor persekutuan terbesar](#def-g9-arith-gcd), alat yang tepat untuk menyederhanakan [pecahan](https://one-course.com/books/math/1/id/chapter/63-pecahan-dan-pangkat#def-g9-fractions-fraction) 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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) $0$.

**Contoh 64.2.**

[Pembagi](#def-g9-arith-divisor) $24$ adalah $1, 2, 3, 4, 6, 8, 12, 24$ — semuanya datang berpasangan yang [hasil kalinya](https://one-course.com/books/math/1/id/chapter/10-perkalian-langkah-pertama#def-g2-mult-def) $24$: $(1,24)$, $(2,12)$, $(3,8)$, $(4,6)$. [Kelipatan](https://one-course.com/books/math/1/id/chapter/32-pembagian-dan-kelipatan#def-g5-division-multiple) $7$ adalah $7, 14, 21, 28, \dots$

**Proposisi 64.3 (Aturan keterbagian).**

Sebuah bilangan bulat [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible):

- $2$ ketika angka terakhirnya [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) ( $0, 2, 4, 6, 8$ );
- $5$ ketika angka terakhirnya $0$ atau $5$ ;
- $10$ ketika angka terakhirnya $0$ ;
- $3$ (berturut-turut $9$ ) ketika [jumlah](https://one-course.com/books/math/1/id/chapter/2-penjumlahan-langkah-pertama#def-g1-addition-def) angkanya [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $3$ (berturut-turut $9$ );
- $4$ ketika dua angka terakhirnya membentuk bilangan yang [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $4$ .

**Bukti.** *Diterima tanpa bukti pada tingkat ini.* ∎

**Contoh 64.4.**

$7\,215$ berakhir dengan $5$: jadi [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $5$. [Jumlah](https://one-course.com/books/math/1/id/chapter/2-penjumlahan-langkah-pertama#def-g1-addition-def) angkanya $7 + 2 + 1 + 5 = 15$, yang [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $3$ tetapi tidak [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $9$: jadi $7\,215$ [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $3$, tidak [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $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](#def-g9-arith-divisor) 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](https://one-course.com/books/math/1/id/chapter/10-perkalian-langkah-pertama#def-g2-mult-def) [bilangan prima](#def-g9-arith-prime), dan pemfaktoran itu tunggal kecuali urutan faktornya.

**Bukti.** *Diterima tanpa bukti pada tingkat ini.* ∎

**Metode 64.7 (Memfaktorkan bilangan bulat).**

Bagilah dengan [bilangan prima](#def-g9-arith-prime) terkecil yang mungkin, berulang-ulang, sampai mencapai $1$:

1. cobalah $2$ selama bilangannya [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) ;
2. lalu cobalah $3$ , lalu $5$ , lalu $7$ , … (hanya yang prima);
3. berhentilah ketika [hasil baginya](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) $1$ ; kumpulkan faktornya beserta [eksponennya](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) .

Cukup mencoba [bilangan prima](#def-g9-arith-prime) $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.](https://one-course.com/images/onecourse/chapters/math-1/g9-arith/fig-aae7345aa9ba.svg)

*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](#def-g9-arith-prime) 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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) $1$, jadi tidak ada $p_i$ yang membagi $N$. Tetapi $N \geq 2$ punya sedikitnya satu [pembagi](#def-g9-arith-divisor) prima ([Teorema 64.6](#thm-g9-arith-factorization)) — yaitu [bilangan prima](#def-g9-arith-prime) yang tidak ada dalam daftar kita. Kontradiksi: tidak ada daftar berhingga yang dapat memuat semua [bilangan primanya](#def-g9-arith-prime). ∎

## 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](#def-g9-arith-divisor) selain $1$.

**Contoh 64.11.**

[Pembagi](#def-g9-arith-divisor) $18$: $1, 2, 3, 6, 9, 18$. [Pembagi](#def-g9-arith-divisor) $24$: $1, 2, 3, 4, 6,
8, 12, 24$. [Pembagi](#def-g9-arith-divisor) bersamanya: $1, 2, 3, 6$; jadi $\gcd(18, 24) = 6$. Bilangan bulat $15$ dan $28$ [saling prima](#def-g9-arith-gcd).

**Proposisi 64.12 (FPB dari pemfaktorannya).**

FPB dua bilangan bulat adalah [hasil kali](https://one-course.com/books/math/1/id/chapter/10-perkalian-langkah-pertama#def-g2-mult-def) [bilangan prima](#def-g9-arith-prime) yang muncul pada *kedua* pemfaktorannya, masing-masing diambil dengan [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) yang *lebih kecil* dari kedua [eksponennya](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def).

**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](#def-g9-arith-prime) bersamanya: $2$ ([eksponennya](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) $3$ dan $2$: ambil $2$) dan $3$ ([eksponennya](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) $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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) $r$, maka

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

Dengan mengulang pembagiannya sampai [sisanya](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) $0$, FPB dari $a$ dan $b$ adalah *[sisa](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) terakhir yang bukan [nol](https://one-course.com/books/math/1/id/chapter/1-membilang-sampai-20#def-g1-counting-zero)*.

**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](#def-g9-arith-divisor) bersama yang persis sama — khususnya yang terbesarnya sama. Karena [sisanya](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) menurun secara tegas, algoritmanya berhenti, dan $\gcd(x, 0) = x$ memberi [sisa](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) terakhir yang bukan [nol](https://one-course.com/books/math/1/id/chapter/1-membilang-sampai-20#def-g1-counting-zero). ∎

**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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) terakhir yang bukan [nol](https://one-course.com/books/math/1/id/chapter/1-membilang-sampai-20#def-g1-counting-zero) adalah $21$: $\gcd(1071, 462) = 21$.

**Metode 64.16 (Menyederhanakan pecahan sepenuhnya).**

Untuk menulis $\dfrac ab$ sesederhana mungkin:

1. hitunglah $d = \gcd(a, b)$ , misalnya dengan algoritma Euclid;
2. bagilah [pembilang](https://one-course.com/books/math/1/id/chapter/24-pecahan-pertama#def-g4-fractions-def) dan [penyebutnya](https://one-course.com/books/math/1/id/chapter/24-pecahan-pertama#def-g4-fractions-def) dengan $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
3. [pecahan](https://one-course.com/books/math/1/id/chapter/63-pecahan-dan-pangkat#def-g9-fractions-fraction) yang dihasilkan bersifat *tak tersederhanakan* : [pembilang](https://one-course.com/books/math/1/id/chapter/24-pecahan-pertama#def-g4-fractions-def) dan [penyebutnya](https://one-course.com/books/math/1/id/chapter/24-pecahan-pertama#def-g4-fractions-def) [saling prima](#def-g9-arith-gcd) .

**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](#def-g9-arith-divisor) $36$, [pembagi](#def-g9-arith-divisor) $45$, dan [pembagi](#def-g9-arith-divisor) $17$.

**Solusi Latihan 64.1.**

[Pembagi](#def-g9-arith-divisor) $36$: $1, 2, 3, 4, 6, 9, 12, 18, 36$. [Pembagi](#def-g9-arith-divisor) $45$: $1, 3, 5, 9, 15, 45$. [Pembagi](#def-g9-arith-divisor) $17$: hanya $1$ dan $17$ ($17$ adalah prima).

**Latihan 64.2 ★.**

Dengan memakai aturan keterbagiannya, tentukan apakah $2\,346$ [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $2$, $3$, $4$, $5$, dan $9$.

**Solusi Latihan 64.2.**

$2\,346$ berakhir dengan $6$: [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $2$, tidak [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $5$. [Jumlah](https://one-course.com/books/math/1/id/chapter/2-penjumlahan-langkah-pertama#def-g1-addition-def) angkanya $2 + 3 + 4 + 6 = 15$: [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $3$, tidak [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $9$. Dua angka terakhirnya $46$, dan $46 = 4 \times 11 + 2$ tidak [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $4$: jadi $2\,346$ tidak [habis dibagi](https://one-course.com/books/math/1/id/chapter/37-bilangan-cacah#def-g6-wholes-divisible) $4$.

**Latihan 64.3 ★.**

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

**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](#met-g9-arith-factorization).

**Solusi Latihan 64.4.**

$101$: ujilah [bilangan prima](#def-g9-arith-prime) $p$ dengan $p^2 \leq 101$, yaitu $2, 3, 5, 7$. Tidak ada yang membagi $101$ ([ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd), [jumlah](https://one-course.com/books/math/1/id/chapter/2-penjumlahan-langkah-pertama#def-g1-addition-def) 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](#def-g9-arith-divisor) bersamanya, dan dari pemfaktoran primanya.

**Solusi Latihan 64.5.**

[Pembagi](#def-g9-arith-divisor) bersama $48$ dan $60$: [pembagi](#def-g9-arith-divisor) 48 adalah $1, 2, 3, 4, 6, 8,
12, 16, 24, 48$; [pembagi](#def-g9-arith-divisor) $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](#def-g9-arith-prime) bersamanya dengan [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) 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 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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) terakhir yang bukan [nol](https://one-course.com/books/math/1/id/chapter/1-membilang-sampai-20#def-g1-counting-zero): $\gcd(255, 154) = 1$ (keduanya [saling prima](#def-g9-arith-gcd)).

$\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](https://one-course.com/books/math/1/id/chapter/63-pecahan-dan-pangkat#def-g9-fractions-fraction) $\dfrac{588}{504}$ tak tersederhanakan. (Hitunglah FPB-nya dengan cara pilihanmu, lalu bagilah.)

**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 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](#def-g9-arith-divisor) bersama terkecil dari $24$ dan $36$; pemfaktorannya membantu.)

**Solusi Latihan 64.9.**

Kita perlu [kelipatan](#def-g9-arith-divisor) bersama terkecilnya. $24 = 2^3 \times 3$ dan $36 = 2^2 \times 3^2$; dengan mengambil tiap [bilangan prima](#def-g9-arith-prime) beserta [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) 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.

1. Tunjukkan bahwa $\gcd(n, n+1) = 1$ (bilangan bulat yang berurutan selalu [saling prima](#def-g9-arith-gcd) ).
2. Simpulkan bahwa [pecahan](https://one-course.com/books/math/1/id/chapter/63-pecahan-dan-pangkat#def-g9-fractions-fraction) $\dfrac{n}{n+1}$ selalu tak tersederhanakan.

**Solusi Latihan 64.10.**

*1.* Setiap [pembagi](#def-g9-arith-divisor) bersama $d$ dari $n$ dan $n+1$ juga membagi [selisihnya](https://one-course.com/books/math/1/id/chapter/3-pengurangan-langkah-pertama#ex-g1-subtraction-difference) $(n+1) - n = 1$, jadi $d = 1$: yaitu $\gcd(n, n+1) = 1$.

*2.* Sebuah [pecahan](https://one-course.com/books/math/1/id/chapter/63-pecahan-dan-pangkat#def-g9-fractions-fraction) tak tersederhanakan persis ketika [pembilang](https://one-course.com/books/math/1/id/chapter/24-pecahan-pertama#def-g4-fractions-def) dan [penyebutnya](https://one-course.com/books/math/1/id/chapter/24-pecahan-pertama#def-g4-fractions-def) [saling prima](#def-g9-arith-gcd), 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](#def-g9-arith-prime), dan sebuah lorong terkenal berisi seratus loker yang keadaan akhirnya ditentukan dengan membilang [pembagi](#def-g9-arith-divisor). Semuanya berjalan dengan mesin bab ini: keterbagian, pemfaktoran prima ([Teorema 64.6](#thm-g9-arith-factorization)) dan algoritma Euclid ([Teorema 64.14](#thm-g9-arith-euclidalgo)).

**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.

1. Takarlah tepat $1$ L. (Uraikan urutan gerakanmu dan isi kedua kendinya sesudah masing-masingnya.)
2. Takarlah tepat $4$ L — yaitu teka-teki dari sebuah film laga yang terkenal. (Hal itu dapat dilakukan dalam enam gerakan.)
3. 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.
4. 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](#def-g9-arith-divisor) $2$ , jadi setiap takaran yang tercapai bernilai [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) .
5. Alasan pada pertanyaan 4 berlaku umum: dengan kendi $a$ dan $b$ liter, setiap takaran yang tercapai adalah [kelipatan](#def-g9-arith-divisor) $\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.**

6. Hitunglah dengan algoritma Euclid: $\gcd(91, 65)$ dan $\gcd(2\,026, 46)$ .
7. Jelaskan, dengan kata-katamu sendiri, mengapa takaran yang muncul pada kendinya adalah [sisa](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) 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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) pada algoritma Euclid untuk $(13, 5)$ .
8. 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)$ .
9. Bukti kilat tentang [saling prima](#def-g9-arith-gcd) dengan gaya [Latihan 64.10](#exo-g9-arith-10) : tunjukkan bahwa $\gcd(n, 2n + 1) = 1$ untuk setiap bilangan bulat positif $n$ . (Apa yang harus dibagi oleh [pembagi](#def-g9-arith-divisor) bersama $n$ dan $2n + 1$ ?)
10. 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](#def-g9-arith-divisor) bersama pertamanya) $\times$ $\gcd$ $=$ [hasil kali](https://one-course.com/books/math/1/id/chapter/10-perkalian-langkah-pertama#def-g2-mult-def) kedua bilangannya — lalu ujilah sekali lagi pada $5$ dan $3$ .

**Bagian III — Jangkrik, [pembagi](#def-g9-arith-divisor) dan loker.**

11. 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* .
12. Dengan memakai pemfaktoran $360 = 2^3 \times 3^2 \times 5$ , bilanglah [pembagi](#def-g9-arith-divisor) $360$ tanpa menyebutkannya satu per satu: sebuah [pembagi](#def-g9-arith-divisor) memilih [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) untuk $2$ (empat pilihan: $0, 1, 2, 3$ ), satu untuk $3$ , satu untuk $5$ . Berapa [pembagi](#def-g9-arith-divisor) seluruhnya?
13. Tunjukkan bahwa pada pemfaktoran kuadrat sempurna $n = m^2$ , setiap [bilangan primanya](#def-g9-arith-prime) membawa [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) yang *[genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd)* . Simpulkan, tanpa menghitung akar kuadrat apa pun, bahwa $360$ bukan kuadrat sempurna.
14. Pasangkan tiap [pembagi](#def-g9-arith-divisor) $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](#def-g9-arith-divisor) menjadi pasangannya sendiri? Simpulkan kriterianya: $n$ punya banyak [pembagi](#def-g9-arith-divisor) yang *[ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd)* persis ketika $n$ adalah kuadrat sempurna. Periksalah pada $36$ dan pada $360$ .
15. 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](#def-g9-arith-divisor) $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 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](#def-g9-arith-divisor) $2$. Mengisi menetapkan isinya menjadi $6$ atau $4$: [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd). Mengosongkan menetapkannya menjadi $0$: [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd). Menuang memindahkan sebagian airnya antara kendi yang isinya [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd), dan banyaknya yang dituang adalah [selisih](https://one-course.com/books/math/1/id/chapter/3-pengurangan-langkah-pertama#ex-g1-subtraction-difference) [bilangan genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) (ruang yang tersisa, atau banyaknya yang tersedia): jadi semua isinya tetap [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) selamanya. Sasaran [ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) seperti $1$ L tidak tercapai.

**5.** $\gcd(6, 4) = 2$: jadi hanya takaran [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) — 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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) $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](https://one-course.com/books/math/1/id/chapter/17-membagi-rata-dan-pembagian#def-g3-division-remainder) 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](#def-g9-arith-divisor) 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](#def-g9-arith-divisor) bersama pertama $12$ dan $18$. Hukumnya: $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times
18$. Untuk $5$ dan $3$: [kelipatan](#def-g9-arith-divisor) 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](#def-g9-arith-divisor) 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](#def-g9-arith-divisor) $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](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) untuk $2$, tiga untuk $3$, dua untuk $5$: jadi $4 \times 3 \times 2 = 24$ [pembagi](#def-g9-arith-divisor).

**13.** Kalau $m = 2^{a} \times 3^{b} \times \cdots$, maka $m^2 = 2^{2a} \times 3^{2b} \times \cdots$: setiap [eksponennya](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) berlipat dua, jadi [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd). Pada $360 = 2^3 \times 3^2 \times 5$, [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) $2$ dan [eksponen](https://one-course.com/books/math/1/id/chapter/56-pangkat#def-g8-powers-def) $5$ [ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd): jadi $360$ bukan kuadrat sempurna.

**14.** Sebuah [pembagi](#def-g9-arith-divisor) menjadi pasangannya sendiri persis ketika $d = \frac nd$, yaitu $n = d^2$: hanya kuadrat yang punya [pembagi](#def-g9-arith-divisor) tengah seperti itu. Untuk semua $n$ yang lain [pembaginya](#def-g9-arith-divisor) terbelah menjadi pasangan, jadi banyaknya [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd). Jadi: banyak [pembagi](#def-g9-arith-divisor) yang [ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) $\Leftrightarrow$ kuadrat sempurna. Periksa: $36$ punya [pembagi](#def-g9-arith-divisor) $1, 2, 3, 4, 6, 9, 12, 18, 36$ — sembilan buah, yaitu [ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd), dan $36 = 6^2$; sedangkan $360$ punya $24$ (pertanyaan 12), yaitu [genap](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd), dan bukan kuadrat (pertanyaan 13).

**15.** Loker $n$ terbalik keadaannya sekali oleh tiap murid $k$ yang nomornya membagi $n$: seluruhnya sebanyak [pembagi](#def-g9-arith-divisor) yang dipunyai $n$. Sebuah loker berakhir *terbuka* ketika keadaannya terbalik sebanyak [bilangan ganjil](https://one-course.com/books/math/1/id/chapter/14-bilangan-sampai-10-000#def-g3-numbers-evenodd) 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.