---
title: "Aritmetika Bilangan Bulat"
book: "Matematika Universitas — Tahun 1"
subject: math
language: id
chapter: 6
exercises: 12
source: https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat
---

# Bab 6 — Aritmetika Bilangan Bulat

Aritmetika — yaitu telaah [keterbagian](#def-b1-arith-divides) di $\Z$ — sudah dimulai pada jilid sekolah menengah. Bab ini membangunnya kembali sepenuhnya dari pembagian Euclid, dengan bukti lengkap: [faktor persekutuan terbesar](#thm-b1-arith-gcd) dan [algoritma Euclid](#met-b1-arith-euclid), kesamaan Bézout dan lema Gauss, [pemfaktoran prima](#thm-b1-arith-fta), serta kalkulus [kekongruenan](#def-b1-arith-congruence) sampai teorema kecil Fermat. Di luar pesonanya sendiri, bahan ini adalah model yang ditiru [Bab 8](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly) untuk polinomial.

## 6.1 Keterbagian dan pembagian Euclid

**Definisi 6.1 (Keterbagian).**

Untuk $a, b \in \Z$, dikatakan $b$ *membagi* $a$ (ditulis $b \mid
a$) bila $a = bq$ untuk suatu $q \in \Z$. Akibat dasarnya: jika $b \mid a$ dan $b \mid a'$ maka $b \mid (ua + va')$ untuk setiap $u, v \in \Z$; jika $b \mid a$ dan $a \neq 0$ maka $\abs b \leq
\abs a$; dan $a \mid b$ bersama $b \mid a$ memaksa $b = \pm a$.

**Teorema 6.2 (Pembagian Euclid).**

Untuk setiap $a \in \Z$ dan $b \in \N^*$, ada tepat satu pasangan $(q, r)
\in \Z \times \N$ dengan

$$
a = bq + r, \qquad 0 \leq r < b .
$$

**Bukti.** *Keberadaan.* [Himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $A = \{a - bk : k \in \Z\} \cap \N$ adalah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian tak kosong dari $\N$ (ambil $k = -\abs a$: $a + b\abs a \geq a +
\abs a \geq 0$). Misalkan $r = a - bq$ unsur terkecilnya. Jika $r \geq b$, maka $r - b = a - b(q+1)$ akan menjadi unsur $A$ yang lebih kecil: kontradiksi. Jadi $0 \leq r < b$.

*Ketunggalan.* Jika $bq + r = bq' + r'$ dengan $0 \leq r, r' < b$, maka $b(q - q') = r' - r$ dan $\abs{r' - r} < b$: kelipatan $b$ pada ruas kiri itu haruslah $0$, jadi $q = q'$ dan $r = r'$. ∎

**Contoh 6.3 (Penomoran posisional lewat pembagian berulang).**

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

$$
2026 = 7 \times 289 + 3, \quad
289 = 7 \times 41 + 2, \quad
41 = 7 \times 5 + 6, \quad
5 = 7 \times 0 + 5 .
$$

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$”.

## 6.2 Faktor persekutuan terbesar

**Teorema 6.4 (Subgrup Z\ZZ; keberadaan FPB).**

1. Setiap subgrup $(\Z, +)$ berbentuk $n\Z = \{nk : k  \in \Z\}$ untuk suatu $n \in \N$ yang tunggal.
2. Untuk $a, b \in \Z$ yang tak keduanya nol, [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $a\Z + b\Z = \{au +  bv : u, v \in \Z\}$ adalah subgrup $\Z$ , sehingga ia sama dengan $d\,\Z$ untuk suatu $d \in \N^*$ yang tunggal. Bilangan $d$ inilah *faktor persekutuan terbesar* $\gcd(a, b)$ : ia [membagi](#def-b1-arith-divides) $a$ dan $b$ , dan setiap pembagi persekutuan $a$ dan $b$ [membagi](#def-b1-arith-divides) $d$ .

**Bukti.** (1) Misalkan $H \subseteq \Z$ sebuah subgrup (tak kosong dan tertutup terhadap pengurangan; definisi formalnya ada pada [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures), dan hanya kedua sifat itu yang dipakai). Jika $H = \{0\}$, ambil $n = 0$. Jika tidak, $H$ memuat sebuah unsur tak nol beserta lawannya, sehingga ia memuat unsur positif tegas terkecil $n$. Maka $n\Z \subseteq H$. Untuk $x
\in H$, tulis $x = nq + r$ dengan $0 \leq r < n$ ([Teorema 6.2](#thm-b1-arith-division)); di sini $r = x - nq \in H$, dan keminimalan $n$ memaksa $r = 0$: jadi $x \in n\Z$. Ketunggalannya: $n$ adalah unsur positif terkecil pada $n\Z$.

(2) [Himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $a\Z + b\Z$ memuat $0$ dan tertutup terhadap pengurangan, jadi ia $d\Z$ dengan $d \geq 1$ (karena ia memuat $a$ atau $b$ yang tak nol). Karena $a, b
\in d\Z$, maka $d$ [membagi](#def-b1-arith-divides) keduanya. Dan jika $c$ [membagi](#def-b1-arith-divides) $a$ dan $b$, maka $c$ [membagi](#def-b1-arith-divides) setiap $au + bv$ — khususnya $c \mid d$, karena $d \in a\Z
+ b\Z$. Itulah sifat yang dinyatakan tadi (dan ia mengakibatkan $\abs c \leq
d$, sehingga $d$ pantas menyandang nama pembagi persekutuan *terbesar*). ∎

**Akibat 6.5 (Kesamaan Bézout).**

Untuk $a, b$ yang tak keduanya nol, ada $u, v \in \Z$ dengan

$$
au + bv = \gcd(a, b) .
$$

Khususnya (bila $\gcd(a,b) = 1$, yaitu kasus *saling prima*): $a$ dan $b$ [saling prima](#cor-b1-arith-bezout) jika dan hanya jika $au + bv = 1$ mempunyai penyelesaian.

**Bukti.** $\gcd(a,b) = d \in d\Z = a\Z + b\Z$. Untuk kesetaraannya: jika $\gcd(a,b) = 1$, Bézout memasok penyelesaiannya; sebaliknya $au + bv =
1$ memaksa setiap pembagi persekutuan $a, b$ [membagi](#def-b1-arith-divides) $1$. ∎

**Metode 6.6 (Algoritma Euclid yang diperluas).**

Untuk menghitung $\gcd(a, b)$ ($a > b > 0$): bagilah $a = bq + r$; maka $\gcd(a, b) = \gcd(b, r)$ (karena pembagi persekutuan $(a,b)$ dan $(b,r)$ berimpit, sebab $r = a - bq$); iterasikan sampai sisanya $0$; lalu sisa tak nol yang terakhir adalah FPB-nya. Menjalankan pembagiannya secara mundur (atau memelihara koefisiennya sambil turun) menghasilkan sepasang bilangan Bézout $(u, v)$.

**Contoh 6.7.**

$\gcd(120, 23)$: $120 = 5 \times 23 + 5$; $23 = 4 \times 5 + 3$; $5 =
1\times 3 + 2$; $3 = 1 \times 2 + 1$; $2 = 2 \times 1 + 0$. Jadi $\gcd = 1$. Secara mundur:

$$
\begin{align*}
1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\
&= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23)
= 47 \times 23 - 9 \times 120 .
\end{align*}
$$

Periksa: $47 \times 23 = 1081$, $9 \times 120 = 1080$.

**Teorema 6.8 (Lema Gauss dan akibatnya).**

Misalkan $a, b, c \in \Z$.

1. (Lema Gauss) Jika $a \mid bc$ dan $\gcd(a, b) = 1$ , maka $a \mid c$ .
2. Jika $a \mid c$ , $b \mid c$ dan $\gcd(a,b) = 1$ , maka $ab \mid  c$ .
3. Jika $\gcd(a, b) = \gcd(a, c) = 1$ , maka $\gcd(a, bc) = 1$ .

**Bukti.** (1) Bézout: $au + bv = 1$. Kalikan dengan $c$: $acu + bcv = c$. Kedua sukunya habis dibagi $a$ (yang kedua karena $a \mid bc$), jadi $a
\mid c$.

(2) Tulis $c = aq$; dari $b \mid aq$ dan $\gcd(a, b) = 1$, butir (1) memberikan $b \mid q$, sehingga $ab \mid aq = c$.

(3) Di sini $au + bv = 1$ dan $au' + cv' = 1$. Kalikan kedua hubungan itu:

$$
1 = (au + bv)(au' + cv')
= a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') ,
$$

yaitu hubungan Bézout antara $a$ dan $bc$: jadi menurut [Akibat 6.5](#cor-b1-arith-bezout), $\gcd(a, bc) = 1$. ∎

**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](#def-b1-arith-divides) $4$, jadi penyelesaiannya ada (seandainya FPB-nya tidak [membagi](#def-b1-arith-divides) 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:

$$
(x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z .
$$

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](https://one-course.com/books/math/3/id/chapter/5-persamaan-diferensial-linear#ch-b1-diffeq), dengan lema Gauss memainkan peran ketunggalannya.

**Definisi 6.10 (Kelipatan persekutuan terkecil).**

$\operatorname{lcm}(a, b)$ adalah pembangkit di $\N$ bagi subgrup $a\Z \cap b\Z$: ia kelipatan persekutuan $a$ dan $b$ yang [membagi](#def-b1-arith-divides) setiap kelipatan persekutuan, dan untuk $a, b \in \N^*$,

$$
\gcd(a,b) \times \operatorname{lcm}(a,b) = ab
\qquad (\text{buktinya pada } \text{Latihan 6.5}).
$$

**Contoh 6.11 (Masalah pensejajaran adalah masalah KPK).**

Dua roda gigi yang bertautan mempunyai $84$ dan $36$ gigi. Setelah berapa gigi gerak bersama keduanya kembali ke kedudukan awalnya bersamaan? Konfigurasinya berulang ketika banyaknya gigi yang berlalu merupakan kelipatan persekutuan $84$ dan $36$; dan pertama kalinya adalah

$$
\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)}
= \frac{3024}{12} = 252
$$

gigi — yaitu $3$ putaran roda besar dan $7$ putaran roda kecil ($252/84$ dan $252/36$). Perhatikan jalur praktisnya: *hitung FPB-nya lebih dulu* (Euclid: $84 = 2\times36 + 12$, $36
= 3\times12$), lalu bagi — jangan pernah membangun KPK-nya dengan mendaftar kelipatannya. Setiap pertanyaan kebetulan berkala (roda gigi, pensejajaran planet, desimal berulang yang bertemu) menyusut menjadi satu perhitungan ini.

## 6.3 Bilangan prima

**Definisi 6.12.**

Bilangan bulat $p \geq 2$ disebut *prima* bila pembagi positifnya hanya $1$ dan $p$. Untuk $p$ prima dan $a \in \Z$: entah $p \mid a$, atau $\gcd(p, a) = 1$. Akibatnya ([Teorema 6.8](#thm-b1-arith-gauss)), berlaku *lema Euclid*: jika $p \mid
ab$ maka $p \mid a$ atau $p \mid b$.

**Catatan 6.13 (Menguji keprimaan lewat pembagian coba-coba).**

Jika $n = ab$ dengan $2 \leq a \leq b$, maka $a^2 \leq ab = n$, jadi $a
\leq \sqrt n$: sebuah $n$ yang komposit selalu mempunyai pembagi [prima](#def-b1-arith-prime) $\leq
\sqrt n$. Jadi untuk menguji apakah $n$ [prima](#def-b1-arith-prime) cukup dicoba [bilangan prima](#def-b1-arith-prime) sampai $\sqrt n$. Untuk $n = 271$: $\sqrt{271} < 17$, dan $271$ tak habis dibagi satu pun dari $2, 3, 5, 7, 11, 13$ (ia ganjil, jumlah angkanya $10$, tak berakhir dengan $0$ atau $5$, dan $271 = 7\cdot38 + 5 =
11\cdot24 + 7 = 13\cdot20 + 11$): jadi [prima](#def-b1-arith-prime), setelah enam pembagian alih-alih dua ratus. Batas $\sqrt n$ itu ambang yang sungguhan: melampauinya secara efisien untuk bilangan beratus angka menuntut uji keprimaan modern yang tumbuh dari [Teorema 6.23](#thm-b1-arith-fermat).

**Teorema 6.14 (Euclid).**

[Bilangan prima](#def-b1-arith-prime) ada tak hingga banyaknya.

**Bukti.** Setiap bilangan bulat $n \geq 2$ mempunyai pembagi [prima](#def-b1-arith-prime): pembagi terkecilnya yang $\geq 2$ bersifat [prima](#def-b1-arith-prime) (karena pemfaktoran sejatinya akan menghasilkan pembagi $n$ yang lebih kecil). Sekarang andaikan $p_1, \dots, p_k$ semua [bilangan primanya](#def-b1-arith-prime), lalu tulis $N = p_1 p_2 \cdots p_k + 1 \geq 2$. Suatu [prima](#def-b1-arith-prime) $p_i$ [membagi](#def-b1-arith-divides) $N$; tetapi $p_i$ juga [membagi](#def-b1-arith-divides) $N - 1 = p_1\cdots p_k$, sehingga $p_i
\mid 1$ — yang mustahil. ∎

**Teorema 6.15 (Teorema dasar aritmetika).**

Setiap bilangan bulat $n \geq 2$ adalah hasil kali [bilangan prima](#def-b1-arith-prime), dan pemfaktoran

$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\qquad (p_1 < p_2 < \dots < p_k \text{ prima},\ \alpha_i \in \N^*)
$$

bersifat tunggal.

**Bukti.** *Keberadaannya* lewat induksi kuat ([Teorema 1.12](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#thm-b1-logic-induction)): $n = 2$ [prima](#def-b1-arith-prime); untuk $n > 2$, entah $n$ [prima](#def-b1-arith-prime), atau $n = ab$ dengan $2 \leq a, b < n$, dan hipotesis induksinya memfaktorkan $a$ dan $b$.

*Ketunggalannya.* Andaikan $p_1 \cdots p_r = q_1 \cdots q_s$ (dengan [bilangan prima](#def-b1-arith-prime) didaftar beserta pengulangannya, katakanlah $r \leq s$), lalu berinduksilah pada $r$. Jika $r = 0$ ruas kirinya $1$, yang memaksa $s = 0$ (karena hasil kali tak kosong [bilangan prima](#def-b1-arith-prime) melebihi $1$). Untuk $r \geq 1$: [prima](#def-b1-arith-prime) $p_1$ [membagi](#def-b1-arith-divides) $q_1(q_2\cdots q_s)$, jadi menurut lema Euclid entah $p_1
\mid q_1$ atau $p_1 \mid q_2\cdots q_s$; dengan mengiterasikannya, $p_1$ [membagi](#def-b1-arith-divides) suatu $q_j$. Tetapi $q_j$ [prima](#def-b1-arith-prime) dan $p_1 \geq 2$: jadi mau tak mau $p_1
= q_j$. Hapuskan faktor persekutuan itu (yang sah karena $\Z$ daerah integral) sehingga diperoleh

$$
p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s
$$

(dengan topinya menandai penghilangan), yaitu kesamaan antara dua hasil kali yang lebih pendek; hipotesis induksinya mengatakan kedua daftar $p_2, \dots, p_r$ dan $q_1, \dots, \widehat{q_j}, \dots, q_s$ berimpit sampai urutannya, sehingga demikian pula daftar aslinya. Bentuk eksponennya mengelompokkan [bilangan prima](#def-b1-arith-prime) yang sama. ∎

**Proposisi 6.16 (Valuasi).**

Untuk $p$ [prima](#def-b1-arith-prime) dan $n \in \N^*$, tulis $v_p(n)$ untuk eksponen $p$ pada pemfaktoran $n$ (dengan $v_p(n) = 0$ bila $p \nmid n$). Maka

$$
v_p(mn) = v_p(m) + v_p(n),
\qquad
m \mid n \iff \forall p,\ v_p(m) \leq v_p(n),
$$

$$
v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr),
\qquad
v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m),
v_p(n)\bigr).
$$

**Bukti.** Kesamaan pertamanya berlaku karena pemfaktorannya terkalikan dan pemfaktoran $mn$ bersifat tunggal. Jika $m \mid n$, tulis $n = mq$ lalu terapkan kesamaan itu. Sebaliknya, jika setiap $v_p(m) \leq v_p(n)$, bilangan bulat $q =
\prod_p p^{\,v_p(n) - v_p(m)}$ memenuhi $mq = n$. Rumus FPB-nya: bilangan $d = \prod p^{\min}$ [membagi](#def-b1-arith-divides) keduanya menurut kriterianya, dan setiap pembagi persekutuan $c$ memenuhi $v_p(c) \leq \min$ untuk setiap $p$, sehingga $c
\mid d$; penalaran yang sama untuk KPK dengan $\max$. ∎

**Contoh 6.17 (Kuadrat dan pangkat tiga lewat valuasi).**

Bilangan bulat $n \geq 1$ merupakan kuadrat sempurna jika dan hanya jika setiap $v_p(n)$ genap (jika $n = m^2$, maka $v_p(n) = 2v_p(m)$; sebaliknya paruhkan setiap eksponennya). Demikian pula untuk pangkat tiga dengan kelipatan $3$. Jadi $21168 = 2^4 \times 3^3 \times 7^2$ bukan kuadrat (karena $v_3 = 3$ ganjil) dan bukan pangkat tiga (karena $v_2 = 4$); bilangan bulat positif terkecil $m$ yang membuat $21168\,m$ *menjadi* pangkat tiga ditemukan dengan menambah setiap eksponennya sampai kelipatan $3$ berikutnya:

$$
m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28,
\qquad
21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3
= 84^3 .
$$

Inti gagasannya: pertanyaan perkalian (kuadrat, pangkat tiga, pembagi, FPB, KPK) berubah menjadi pertanyaan *koordinat demi koordinat* pada vektor eksponen $(v_2, v_3, v_5, \dots)$ — dan ketunggalan pemfaktoran adalah [pernyataan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-statement) bahwa koordinat itu ada dan terdefinisi dengan baik.

## 6.4 Kekongruenan

**Definisi 6.18.**

Untuk $n \in \N^*$: $a \equiv b \pmod n$ bila $n \mid
a - b$. Ini [relasi ekuivalensi](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-equiv) yang serasi dengan penjumlahan dan perkalian: jika $a \equiv b$ dan $a' \equiv b'$ (modulo $n$), maka $a + a' \equiv b + b'$, $aa' \equiv bb'$, dan $a^k \equiv b^k$ untuk $k \in \N$.

**Contoh 6.19 (Uji buang sembilan).**

Keserasiannya dengan $+$ dan $\times$ adalah alat pemeriksa yang setua perniagaan. Karena $10 \equiv 1 \pmod 9$, setiap bilangan bulat kongruen modulo $9$ dengan jumlah angkanya (dibuktikan pada [Latihan 6.2](#exo-b1-arith-2)). Untuk memeriksa klaim $1234 \times 567 =
699\,678$: jumlah angkanya memberikan $1234 \equiv 1$ dan $567 \equiv 18
\equiv 0 \pmod 9$, jadi hasil kalinya haruslah $\equiv 1 \times 0 =
0$; dan memang $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. Pemeriksaannya lolos (dan hasil kalinya memang benar). Seandainya ada yang melaporkan $699\,478$, jumlah angkanya $43 \equiv 7 \not\equiv 0$ akan menghukumnya seketika. Ujinya bersifat sepihak — ia menangkap sebuah kesalahan kecuali bila kesalahannya sendiri kelipatan $9$ — dan itu persis pelajaran pseudoprima pada [Contoh 6.24](#ex-b1-arith-pseudoprime) dalam wujud mini: pemeriksaan [kekongruenan](#def-b1-arith-congruence) membantah, tetapi tidak mengesahkan.

**Proposisi 6.20 (Keterbalikan mod nnn).**

$a$ disebut *terbalikkan modulo $n$* (yakni $ab \equiv 1 \pmod n$ untuk suatu $b$) jika dan hanya jika $\gcd(a, n) = 1$. Inversnya lalu tunggal modulo $n$ dan dihitung dengan [algoritma Euclid](#met-b1-arith-euclid) yang diperluas.

**Bukti.** $ab \equiv 1 \pmod n$ berarti $ab + nk = 1$ untuk suatu $k$: yaitu hubungan Bézout, yang ada jika dan hanya jika $\gcd(a,n) = 1$ ([Akibat 6.5](#cor-b1-arith-bezout)). Ketunggalannya: jika $ab \equiv ab' \equiv 1$, maka $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎

**Contoh 6.21 (Membalikkan 777 modulo 262626).**

Karena $\gcd(7, 26) = 1$, kelas $7$ terbalikkan modulo $26$. Euclid yang diperluas:

$$
26 = 3 \times 7 + 5, \qquad
7 = 1 \times 5 + 2, \qquad
5 = 2 \times 2 + 1 ,
$$

lalu secara mundur:

$$
1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7
= 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .
$$

Jadi $7 \times (-11) \equiv 1 \pmod{26}$, yakni $7^{-1} \equiv
-11 \equiv 15 \pmod{26}$; periksa: $7 \times 15 = 105 = 4 \times 26
+ 1$. Dengan inversnya di tangan, sebarang [kekongruenan](#def-b1-arith-congruence) $7x \equiv c
\pmod{26}$ diselesaikan dalam satu perkalian: $x \equiv 15c$. Pembalikan mekanis inilah kuda beban aritmetika modular — dan juga kuda beban protokol kunci publik yang disebut pada [Catatan 6.27](#rem-b1-arith-whereused), yang di sana modulusnya beratus angka tetapi algoritmanya persis yang ini.

**Contoh 6.22 (Ketika koefisiennya tak terbalikkan).**

Selesaikan $12x \equiv 8 \pmod{20}$. Di sini $\gcd(12, 20) = 4$, jadi $12$ tak terbalikkan modulo $20$ — tetapi persamaannya tetap tertangani. [Kekongruenan](#def-b1-arith-congruence) itu mengatakan $20 \mid 12x - 8$; dengan membagi seluruh hubungannya dengan $4$ (pembagi ketiga bahannya), ia setara dengan $5 \mid 3x - 2$, yakni

$$
3x \equiv 2 \pmod 5 .
$$

Sekarang $\gcd(3, 5) = 1$ dan $3^{-1} \equiv 2 \pmod 5$ (karena $3 \times 2 =
6 \equiv 1$), jadi $x \equiv 4 \pmod 5$: penyelesaiannya adalah $x
\equiv 4, 9, 14, 19 \pmod{20}$ — *empat* kelas modulo $20$, yang cocok dengan FPB-nya. (Seandainya ruas kanannya tak habis dibagi $4$, katakanlah $12x \equiv 6 \pmod{20}$, tak akan ada penyelesaian sama sekali: karena ruas kirinya selalu $\equiv 0 \pmod 4$.) Bentuk umumnya: $ax
\equiv b \pmod n$ terselesaikan jika dan hanya jika $\gcd(a, n) \mid b$, dan lalu ia mempunyai tepat $\gcd(a, n)$ kelas penyelesaian — bagi semuanya dengan FPB-nya lalu balikkan.

**Teorema 6.23 (Teorema kecil Fermat).**

Misalkan $p$ [prima](#def-b1-arith-prime). Untuk setiap $a \in \Z$:

$$
a^p \equiv a \pmod p,
$$

dan jika $p \nmid a$, maka $a^{p-1} \equiv 1 \pmod
p$.

**Bukti.** Pertama, untuk $1 \leq k \leq p - 1$, [koefisien binomial](https://one-course.com/books/math/3/id/chapter/2-pencacahan#def-b1-counting-objects) $\binom pk
= \frac{p!}{k!(p-k)!}$ habis dibagi $p$: memang $k!\,(p-k)!\,
\binom pk = p!$ dan $p$ [membagi](#def-b1-arith-divides) $p!$ tetapi [saling prima](#cor-b1-arith-bezout) dengan $k!(p-k)!$ (karena semua faktornya $< p$), jadi lema Gauss memberikan $p \mid \binom pk$.

Sekarang buktikan $a^p \equiv a$ untuk $a \in \N$ dengan induksi. Benar untuk $a =
0$. Jika $a^p \equiv a$, maka menurut teorema binomial

$$
(a+1)^p = \sum_{k=0}^{p} \binom pk a^k
\equiv a^p + 1 \equiv a + 1 \pmod p,
$$

dengan semua suku tengahnya lenyap modulo $p$. Untuk $a < 0$, terapkan hasilnya pada $-a$ lalu pisahkan $p = 2$ (yang di situ $x \equiv -x$) dari $p$ ganjil (yang di situ $(-a)^p = -a^p$). Akhirnya, jika $p \nmid a$, kalikan $a^p \equiv a$ dengan sebuah invers $a$ modulo $p$ ([Proposisi 6.20](#prop-b1-arith-invmod)). ∎

**Contoh 6.24 (Konvers Fermat gugur: 341341341).**

Teorema kecil Fermat memberikan uji *kekompositan* yang murah: jika $a^{n-1} \not\equiv 1 \pmod n$ untuk suatu $a$ yang [saling prima](#cor-b1-arith-bezout) dengan $n$, maka $n$ tidak [prima](#def-b1-arith-prime). Dapatkah ujinya juga mengesahkan keprimaan? Tidak: ambil $n = 341 = 11 \times 31$, yang komposit, dan $a = 2$. Karena $2^{10} = 1024 = 3 \times 341 + 1$,

$$
2^{10} \equiv 1 \pmod{341}
\qquad\Longrightarrow\qquad
2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :
$$

bilangan komposit $341$ lolos uji Fermat untuk basis $2$ (dan ia *pseudoprima* terkecil semacam itu). Basis $3$ menyingkap topengnya ($3^{340} \not\equiv 1$), sehingga uji keprimaan yang praktis menjalankan ujinya pada beberapa basis, ditambah penghalusan — versi industri gagasan inilah yang mengesahkan [bilangan prima](#def-b1-arith-prime) besar pada [Catatan 6.27](#rem-b1-arith-whereused). Moralnya: sebuah implikasi dan konversnya hidup secara terpisah ([Catatan 1.10](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#rem-b1-logic-pitfalls)), bahkan untuk teorema.

**Contoh 6.25 (Perhitungan kekongruenan yang praktis).**

Berapa sisa $7^{2026}$ modulo $11$? Menurut Fermat, $7^{10}
\equiv 1 \pmod{11}$. Karena $2026 = 10 \times 202 + 6$:

$$
7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4
\pmod{11}.
$$

Sisanya adalah $4$. Strateginya: susutkan eksponennya modulo orde yang disediakan Fermat, lalu susutkan pangkat antaranya pada setiap langkah.

**Catatan 6.26 (Jebakan yang lazim dalam aritmetika).**

1. *[Membagi](#def-b1-arith-divides) sebuah [kekongruenan](#def-b1-arith-congruence).* Dari $ac \equiv bc \pmod n$ kita *tidak* boleh menyimpulkan $a \equiv b$ kecuali bila $\gcd(c,  n) = 1$ : misalnya $6 \equiv 2 \pmod 4$ tetapi $3 \not\equiv 1 \pmod  4$ . Kaidah umum yang benar [membagi](#def-b1-arith-divides) modulusnya juga: $ac  \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
2. *Menyalahgunakan lema Euclid.* Bahwa $a \mid bc$ mengakibatkan $a  \mid b$ atau $a \mid c$ hanya berlaku untuk $a$ yang *[prima](#def-b1-arith-prime)* (atau yang [saling prima](#cor-b1-arith-bezout) dengan salah satu faktornya): $6 \mid 4 \times 9$ padahal $6$ tak [membagi](#def-b1-arith-divides) satu pun faktornya.
3. *[Saling prima](#cor-b1-arith-bezout) itu relasi, bukan sifat.* “ $8$ dan $9$ [saling prima](#cor-b1-arith-bezout) ” itu benar meskipun tak satu pun [prima](#def-b1-arith-prime) ; “ [saling prima](#cor-b1-arith-bezout) dua-dua” lebih kuat daripada “ [saling prima](#cor-b1-arith-bezout) secara menyeluruh” ( $\gcd(6, 10, 15) = 1$ tetapi tak ada pasangan yang [saling prima](#cor-b1-arith-bezout) ).
4. *Eksponen tidak hidup modulo $n$.* Pada $a^k \bmod n$ , eksponennya hanya boleh disusutkan modulo *orde* $a$ (misalnya $p - 1$ ketika Fermat berlaku), jangan pernah modulo $n$ : $2^{10} \bmod 11$ adalah $1$ , bukan $2^{10 \bmod  11} = 2^{10}$ — penyusutan yang berhasil adalah yang dilakukan [Contoh 6.25](#ex-b1-arith-congruences) .

**Catatan 6.27 (Di mana bab ini dipakai).**

Bab ini adalah cetakan sekaligus kotak perkakas. Seluruh rantainya — pembagian Euclid, FPB, Bézout, Gauss, ketunggalan pemfaktoran — diputar ulang kata demi kata untuk polinomial pada [Bab 8](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly), yang di sana “derajat” memainkan peran nilai mutlak; membandingkan kedua bab itu berdampingan adalah cara terbaik memahami keduanya. Kalkulus [kekongruenannya](#def-b1-arith-congruence) menjelma menjadi ring $\Z/n\Z$ pada [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures), yang unsur terbalikkannya ([Proposisi 6.20](#prop-b1-arith-invmod)) membentuk contoh tak sepele pertama sebuah grup satuan. Valuasi kembali pada soal akhir pekan di bawah (rumus Legendre) dan menggerakkan bukti keirasionalan pada [Bab 10](https://one-course.com/books/math/3/id/chapter/10-bilangan-real#ch-b1-reals). Di luar jilid ini, pembalikan Bézout modulo $n$ menjadi mesin kriptografi kunci publik, dan teorema kecil Fermat adalah kakek moyang uji keprimaan yang mengesahkan [bilangan prima](#def-b1-arith-prime) besar yang dipakai di sana.

**Catatan 6.28 (Selingan: Z\ZZ sebagai cetakan).**

Mundurlah dari teorema satu per satu lalu amati arsitektur bab ini: satu perkakas (pembagian Euclid) menghasilkan sebuah penggolongan (subgrup $n\Z$), yang menghasilkan teorema keberadaan (FPB, Bézout), yang menghasilkan kalkulus [keterbagian](#def-b1-arith-divides) (Gauss), yang menghasilkan ketunggalan pemfaktoran — setiap lantainya bersandar hanya pada lantai di bawahnya. Bangunan yang sama akan didirikan dua kali lagi dalam jilid ini dengan lantai dasar yang berbeda: pada [Bab 8](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly), yang di sana pembagian menurut derajat menggantikan pembagian menurut ukuran dan segala yang di atasnya berulang *kata demi kata*; dan, dalam wujud mini, di dalam setiap $\Z/n\Z$ pada [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures), yang di sana pertanyaan keterbalikan (yaitu [Proposisi 6.20](#prop-b1-arith-invmod) bab ini) menjadi [pernyataan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-statement) struktural tentang ring dan lapangan. Mengenali sebuah argumen sebagai “argumen $\Z$ yang dicangkokkan” adalah cara tercepat mempelajari bab itu — dan cicipan pertama kebiasaan inti aljabar, yaitu membuktikan teorema tentang *aksioma* alih-alih tentang objek.

![Baris 0 sampai 7 segitiga Pascal dengan entri yang ganjil diarsir: baris n memuat 2s_2(n) di antaranya, dengan s_2(n) banyaknya angka satu pada penulisan biner n (baris 1, 2, 4: dua entri ganjil; baris 7 = (111)_2: kedelapannya). Pola serupa-dirinya — setiap “segitiga entri ganjil” melahirkan dua salinan dirinya — adalah teorema Kummer dalam wujud gambar, yang dibuktikan pada soal akhir pekan di bawah.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg)

*Baris $0$ sampai $7$ segitiga Pascal dengan entri yang *ganjil* diarsir: baris $n$ memuat $2^{s_2(n)}$ di antaranya, dengan $s_2(n)$ banyaknya angka satu pada penulisan biner $n$ (baris $1, 2, 4$: dua entri ganjil; baris $7 = (111)_2$: kedelapannya). Pola serupa-dirinya — setiap “segitiga entri ganjil” melahirkan dua salinan dirinya — adalah teorema Kummer dalam wujud gambar, yang dibuktikan pada soal akhir pekan di bawah.*

## 6.5 Latihan

**Latihan 6.1 ★.**

Hitung $\gcd(1\,001, 777)$ dengan [algoritma Euclid](#met-b1-arith-euclid), beserta sepasang bilangan Bézout untuknya.

**Solusi Latihan 6.1.**

$1001 = 1 \times 777 + 224$; $777 = 3 \times 224 + 105$; $224 = 2
\times 105 + 14$; $105 = 7 \times 14 + 7$; $14 = 2 \times 7 + 0$. Jadi $\gcd(1001, 777) = 7$. Secara mundur:

$$
7 = 105 - 7 \times 14
= 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224
$$

$$
= 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224
= 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 .
$$

Periksa: $67 \times 777 = 52\,059$ dan $52 \times 1001 = 52\,052$; selisihnya $7$. Pasangan Bézout: $(u, v) = (-52, 67)$ untuk $1001u + 777v =
7$.

**Latihan 6.2 ★.**

Buktikan kaidah [keterbagian](#def-b1-arith-divides) dalam basis $10$: sebuah bilangan bulat kongruen modulo $9$ dengan jumlah angkanya, dan modulo $11$ dengan jumlah berselang-seling angkanya. Berapa $123\,456\,789$ modulo $9$ dan modulo $11$?

**Solusi Latihan 6.2.**

Karena $10 \equiv 1 \pmod 9$: $10^k \equiv 1$, jadi $\sum_k d_k 10^k
\equiv \sum_k d_k \pmod 9$. Karena $10 \equiv -1 \pmod{11}$: $10^k
\equiv (-1)^k$, jadi bilangannya kongruen dengan jumlah berselang-seling $\sum_k (-1)^k d_k$ modulo $11$ (dimulai dari angka *satuannya* dengan tanda $+$).

Untuk $123\,456\,789$: jumlah angkanya $45 \equiv 0 \pmod 9$. Jumlah berselang-selingnya dari satuan: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$, jadi bilangan itu $\equiv 5 \pmod{11}$.

**Latihan 6.3 ★.**

Selesaikan di $\Z$: $91x \equiv 1 \pmod{237}$ *(Euclid yang diperluas)*.

**Solusi Latihan 6.3.**

Euclid: $237 = 2 \times 91 + 55$; $91 = 1 \times 55 + 36$; $55 = 1
\times 36 + 19$; $36 = 1 \times 19 + 17$; $19 = 1 \times 17 + 2$; $17
= 8 \times 2 + 1$. Secara mundur:

$$
1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19
= 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19
$$

$$
= 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55
= 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55
$$

$$
= 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237.
$$

Jadi $91 \times 112 \equiv 1 \pmod{237}$: penyelesaiannya adalah $x \equiv
112 \pmod{237}$. (Periksa: $91 \times 112 = 10\,192 = 43 \times 237 +
1$.)

**Latihan 6.4 ★.**

Carilah semua pasangan $(x, y) \in \Z^2$ dengan $17x + 39y = 1$; lalu semua pasangan dengan $17 x + 39 y = 5$.

**Solusi Latihan 6.4.**

$\gcd(17, 39) = 1$: Euclid memberikan $39 = 2\times 17 + 5$, $17 = 3\times
5 + 2$, $5 = 2\times 2 + 1$, dan secara mundur

$$
1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17
= 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 .
$$

Penyelesaian khususnya $(x_0, y_0) = (-16, 7)$. Penyelesaian umum persamaan homogennya $17x + 39y = 0$: $x = 39k$, $y = -17k$ (karena $17 \mid 39y$ dan $\gcd(17,39) = 1$ memaksa $17 \mid y$ — menurut lema Gauss). Jadi

$$
(x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z .
$$

Untuk ruas kanan $5$, kalikan penyelesaian khususnya dengan $5$: $(x, y) = (-80 + 39k,\; 35 - 17k)$, $k \in \Z$.

**Latihan 6.5 ★★.**

Buktikan bahwa untuk $a, b \in \N^*$ berlaku $\gcd(a,b) \times
\operatorname{lcm}(a,b) = ab$. *(Pakai rumus valuasi pada [Proposisi 6.16](#prop-b1-arith-valuation) dan $\min(\alpha,\beta) +
\max(\alpha,\beta) = \alpha + \beta$.)*

**Solusi Latihan 6.5.**

Untuk setiap [prima](#def-b1-arith-prime) $p$, dengan $\alpha = v_p(a)$ dan $\beta = v_p(b)$:

$$
v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr)
= \min(\alpha, \beta) + \max(\alpha, \beta)
= \alpha + \beta = v_p(ab) .
$$

Dua bilangan bulat positif yang valuasinya sama pada setiap [prima](#def-b1-arith-prime) adalah sama ([Proposisi 6.16](#prop-b1-arith-valuation)), jadi $\gcd(a,b)\operatorname{lcm}(a,b)
= ab$.

**Latihan 6.6 ★★.**

Misalkan $a = 2^{10} \times 3^4 \times 5^2$ dan $b = 2^6 \times 3^7 \times
7$. Hitung $\gcd(a, b)$, $\operatorname{lcm}(a,b)$, dan banyaknya pembagi positif $a$. *(Buktikan rumus cacah pembaginya $\prod_i (\alpha_i + 1)$.)*

**Solusi Latihan 6.6.**

Valuasinya: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)}
7^{\min(0,1)} = 2^6\, 3^4 = 5184$; $\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$.

Cacah pembaginya: pembagi positif $n = \prod p_i^{\alpha_i}$ tepat berupa pilihan $\prod p_i^{\beta_i}$ dengan $0 \leq \beta_i \leq
\alpha_i$ ([Proposisi 6.16](#prop-b1-arith-valuation)); pilihannya saling bebas, jadi ada $\prod_i (\alpha_i + 1)$ pembagi. Untuk $a$: $(10+1)(4+1)(2+1) = 165$.

**Latihan 6.7 ★★.**

Buktikan bahwa $\sqrt p$ irasional untuk setiap [prima](#def-b1-arith-prime) $p$, dengan memakai valuasi: bandingkan $v_p$ kedua ruas $p q^2 = r^2$.

**Solusi Latihan 6.7.**

Andaikan $\sqrt p = \frac rq$ dengan $r, q \in \N^*$, yakni $p q^2 =
r^2$. Terapkan $v_p$: $v_p(pq^2) = 1 + 2v_p(q)$ ganjil, sedangkan $v_p(r^2)
= 2 v_p(r)$ genap. Sebuah bilangan bulat tak mungkin bervaluasi $p$ ganjil sekaligus genap: kontradiksi. Jadi $\sqrt p \notin \Q$.

**Latihan 6.8 ★★.**

(Masalah sisa Cina) Carilah semua bilangan bulat $x$ dengan

$$
x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}.
$$

Buktikan sepanjang jalan bahwa untuk $m, n$ yang [saling prima](#cor-b1-arith-bezout), sepasang [kekongruenan](#def-b1-arith-congruence) $x \equiv a \ (m)$, $x \equiv b\ (n)$ selalu mempunyai penyelesaian yang tunggal modulo $mn$.

**Solusi Latihan 6.8.**

*Fakta umumnya.* Dengan $\gcd(m,n) = 1$, Bézout memberikan $mu + nv = 1$. Tulis $x_0 = b\,mu + a\,nv$. Maka $x_0 \equiv a\,nv \equiv a(1 - mu)
\equiv a \pmod m$ dan serupa itu $x_0 \equiv b \pmod n$: itulah keberadaannya. Jika $x$ dan $x'$ dua penyelesaian, maka $m$ dan $n$ [membagi](#def-b1-arith-divides) $x - x'$, sehingga $mn \mid x - x'$ ([Teorema 6.8](#thm-b1-arith-gauss) (2)): itulah ketunggalannya modulo $mn$.

*Secara numerik:* $m = 7$, $n = 11$: $7 \times (-3) + 11 \times 2 =
1$. Jadi $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 +
44 = -61 \equiv 16 \pmod{77}$. Periksa: $16 = 2\times 7 + 2 \equiv 2
\pmod 7$; $16 = 11 + 5 \equiv 5 \pmod{11}$. Penyelesaiannya: $x \equiv 16
\pmod{77}$.

**Latihan 6.9 ★★.**

Hitung $3^{1000}$ modulo $7$, dan dua angka desimal terakhir $7^{100}$ *(modulo $100 = 4 \times 25$: pakai [Latihan 6.8](#exo-b1-arith-8))*.

**Solusi Latihan 6.9.**

Modulo $7$: Fermat memberikan $3^6 \equiv 1$, dan $1000 = 6 \times 166 + 4$, jadi $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Dua angka terakhir $7^{100}$: bekerjalah modulo $4$ dan modulo $25$. Modulo $4$: $7
\equiv -1$, jadi $7^{100} \equiv 1$. Modulo $25$: $7^2 = 49 \equiv -1$, jadi $7^4 \equiv 1$ dan $7^{100} = (7^4)^{25} \equiv 1$. Menurut teorema sisa Cina ([Latihan 6.8](#exo-b1-arith-8)), $7^{100} \equiv 1
\pmod{100}$: jadi dua angka terakhirnya adalah $01$.

**Latihan 6.10 ★★★.**

Untuk $m, n \in \N^*$, buktikan bahwa $\gcd(2^m - 1,\, 2^n - 1) =
2^{\gcd(m,n)} - 1$. *Petunjuk: tunjukkan lebih dulu bahwa sisa $2^m
- 1$ modulo $2^n - 1$ adalah $2^r - 1$ dengan $r$ sisa $m$ modulo $n$; lalu ikuti [algoritma Euclid](#met-b1-arith-euclid).*

**Solusi Latihan 6.10.**

Tulis $m = nq + r$, $0 \leq r < n$. Maka

$$
2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1,
$$

dan $2^n - 1$ [membagi](#def-b1-arith-divides) $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots +
1)$. Jadi modulo $2^n - 1$ berlaku $\;2^m - 1 \equiv 2^r - 1$, dan karena $0 \leq
2^r - 1 < 2^n - 1$, ini *memang* sisa Euclidnya.

Karena itu [algoritma Euclid](#met-b1-arith-euclid) pada pasangan $(2^m - 1, 2^n - 1)$ mencerminkan, eksponen demi eksponen, algoritmanya pada $(m, n)$: setiap langkah pembagiannya mengganti $(m, n)$ dengan $(n, r)$ di lantai atas dan $(2^m - 1,
2^n - 1)$ dengan $(2^n - 1, 2^r - 1)$ di lantai bawah. Algoritma di atasnya berhenti pada $\gcd(m,n)$, jadi di bawahnya ia berhenti pada $2^{\gcd(m,n)} - 1$.

**Latihan 6.11 ★★★.**

(Teorema Wilson) Misalkan $p$ sebuah [prima](#def-b1-arith-prime). Buktikan bahwa

$$
(p-1)! \equiv -1 \pmod p ,
$$

dengan memasangkan setiap faktor $(p-1)!$ dengan inversnya modulo $p$ lalu mengenali faktor yang berpasangan dengan dirinya sendiri (selesaikan $x^2 \equiv 1 \pmod p$ lebih dulu). Periksa konversnya: jika $n \geq 2$ tidak [prima](#def-b1-arith-prime), maka $(n-1)!
\not\equiv -1 \pmod n$.

**Solusi Latihan 6.11.**

Selesaikan dulu $x^2 \equiv 1 \pmod p$: di sini $p \mid (x-1)(x+1)$, jadi menurut lema Euclid $x \equiv 1$ atau $x \equiv -1 \pmod p$.

Pada hasil kali $(p-1)! = 1 \times 2 \times \dots \times (p-1)$, setiap faktor $a$ terbalikkan modulo $p$, dan inversnya $a^{-1}$ kembali menjadi salah satu faktornya ([Proposisi 6.20](#prop-b1-arith-invmod)). Pasangkan setiap $a$ dengan $a^{-1}$: pasangannya berhasil kali $1$, kecuali faktor yang berpasangan dengan dirinya sendiri ($a = a^{-1}$, yakni $a^2 \equiv 1$) yang berdiri sendirian — dan itu tepat $1$ dan $p - 1$. Jadi

$$
(p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p .
$$

(Untuk $p = 2$: $1! = 1 \equiv -1 \pmod 2$; argumen pemasangannya merosot tetapi hasilnya tetap berlaku.)

*Konversnya.* Misalkan $n \geq 2$ komposit, $n = ab$ dengan $1 < a
\leq b < n$. Jika $a < b$, keduanya muncul sebagai faktor $(n-1)!$ yang berbeda, sehingga $n \mid (n-1)!$ dan $(n-1)! \equiv 0 \not\equiv -1$. Jika $a = b$ (yakni $n = a^2$): untuk $a \geq 3$, baik $a$ maupun $2a$ bernilai $< n$, jadi $n = a^2 \mid a \times 2a \mid (n-1)!$, dengan kesimpulan yang sama; adapun untuk $n = 4$, $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$.

**Latihan 6.12 ★★★.**

(Bilangan Fermat) Untuk $n \in \N$, tulis $F_n = 2^{2^n} + 1$.

1. Buktikan bahwa $F_0 F_1 \cdots F_{n-1} = F_n - 2$ untuk $n \geq  1$ (dengan induksi).
2. Simpulkan bahwa bilangan Fermat [saling prima](#cor-b1-arith-bezout) dua-dua.
3. Simpulkan bukti kedua, yang tak bergantung pada [Teorema 6.14](#thm-b1-arith-euclidprimes) , bahwa [bilangan prima](#def-b1-arith-prime) ada tak hingga banyaknya.

**Solusi Latihan 6.12.**

1. Dengan induksi. Untuk $n = 1$: $F_0 = 3 = F_1 - 2 = 5 - 2$. Dengan mengandaikan $F_0\cdots F_{n-1} = F_n - 2$: $$F_0 \cdots F_n = (F_n - 2)F_n  = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr)  = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$$
2. Misalkan $m < n$ dan $d = \gcd(F_m, F_n)$ . Menurut (1), $F_m$ [membagi](#def-b1-arith-divides) $F_n - 2$ , jadi $d$ [membagi](#def-b1-arith-divides) $F_n$ maupun $F_n -  2$ , sehingga ia [membagi](#def-b1-arith-divides) $2$ . Tetapi setiap bilangan Fermat ganjil, jadi $d = 1$ .
3. Setiap $F_n \geq 3$ mempunyai pembagi [prima](#def-b1-arith-prime) $p_n$ (menurut langkah pertama [Teorema 6.14](#thm-b1-arith-euclidprimes) ). Jika $m  \neq n$ , maka $p_m \neq p_n$ , karena [prima](#def-b1-arith-prime) persekutuannya akan [membagi](#def-b1-arith-divides) $\gcd(F_m, F_n) = 1$ . Jadi [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $n \mapsto p_n$ bersifat [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dari $\N$ ke dalam [bilangan prima](#def-b1-arith-prime) : sehingga [bilangan prima](#def-b1-arith-prime) ada tak hingga banyaknya.

## 6.6 Soal: Rumus Legendre dan simpanan Kummer

**Soal 6.1.**

Berapa banyak nol yang mengakhiri penulisan desimal $1000!$ — dan, lebih dalam lagi, berapa pangkat persis sebuah [prima](#def-b1-arith-prime) $p$ yang [membagi](#def-b1-arith-divides) $n!$, atau [membagi](#def-b1-arith-divides) [koefisien binomial](https://one-course.com/books/math/3/id/chapter/2-pencacahan#def-b1-counting-objects)? Jawaban lengkapnya adalah dua permata aritmetika dasar: *rumus Legendre* $v_p(n!) = \sum_{k\geq1}
\lfloor n/p^k \rfloor$, beserta jelmaan digitalnya $v_p(n!) = \frac{n
- s_p(n)}{p-1}$, dan *teorema Kummer*: bahwa $v_p\binom{m+n}m$ mencacah *simpanan* ketika $m$ dan $n$ dijumlahkan dalam basis $p$. Soal ini membuktikan keduanya, mencocokkannya satu sama lain secara numerik, lalu memanen akibat klasiknya — nol penutup, keparitasan segitiga Pascal, dan sebuah batas pertama ke arah teorema [bilangan prima](#def-b1-arith-prime). Di sepanjang soal ini, $p$ sebuah [prima](#def-b1-arith-prime), $\floor{x}$ bagian bulatnya, dan $s_p(n)$ menyatakan jumlah angka $n$ yang ditulis dalam basis $p$.

**Bagian I — Lantai, valuasi, dan rumus Legendre.**

1. Pemanasan: hitung $10!$ lalu bacalah banyaknya nol penutupnya; hitung $v_2(10!)$ dan $v_5(10!)$ langsung dari pemfaktoran setiap faktornya $1, 2, \dots, 10$ .
2. Buktikan bahwa untuk $x \in \R$ dan $n \in \N^*$ berlaku $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor =  \lfloor x/n \rfloor$ .
3. Buktikan bahwa $v_p(a + b) \geq \min\bigl(v_p(a),  v_p(b)\bigr)$ untuk setiap $a, b \in \N^*$ , dengan kesamaan setiap kali $v_p(a) \neq v_p(b)$ .
4. Tunjukkan bahwa banyaknya kelipatan $m$ di $\intint1n$ adalah $\lfloor n/m \rfloor$ .
5. Buktikan *rumus Legendre*: untuk setiap $n \in \N^*$, $$v_p(n!) = \sum_{k=1}^{\infty}  \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$$ (yaitu jumlah yang hingga: sukunya lenyap begitu $p^k > n$). *Cacahlah, untuk setiap $k$, faktor $\intint1n$ yang habis dibagi $p^k$: masing-masing menyumbang tepat satu satuan per aras yang dicapainya.*

**Bagian II — Bentuk digital dan nol penutup.**

6. Hitung $v_5(1000!)$ dan $v_2(1000!)$ , lalu simpulkan: berapa banyak nol yang mengakhiri $1000!$ ?
7. Buktikan bentuk digital rumus Legendre: dengan menulis $n =  \sum_i a_i p^i$ dalam basis $p$, $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$
8. Dua akibat untuk $p = 2$ : tunjukkan bahwa $2^n$ tak pernah [membagi](#def-b1-arith-divides) $n!$ , dan bahwa $2^{n-1}$ [membagi](#def-b1-arith-divides) $n!$ tepat ketika $n$ merupakan pangkat $2$ .
9. Batasi cacatnya: tunjukkan $\frac n{p-1} - \log_p(n) - 1 \leq  v_p(n!) < \frac n{p-1}$ , sehingga $\frac{v_p(n!)}{n} \to  \frac1{p-1}$ : jadi dalam jangka panjang, sebanyak $\frac1{p-1}$ faktor $p$ terkumpul per satuan.
10. Misalkan $Z(n) = v_5(n!)$ banyaknya nol penutup $n!$ . Tunjukkan $Z(n) - Z(n-1) = v_5(n)$ , simpulkan bahwa $Z$ melompati nilai $5$ sama sekali (hitung $Z(24)$ dan $Z(25)$ ), lalu buktikan bahwa tak ada faktorial yang berakhir dengan tepat lima nol.

**Bagian III — Teorema Kummer.**

11. Buktikan bahwa $\lfloor x + y \rfloor - \lfloor x \rfloor -  \lfloor y \rfloor \in \{0, 1\}$ untuk setiap $x, y \in \R$, lalu simpulkan dari rumus Legendre bahwa $$v_p\binom{m+n}m  = \sum_{k\geq1}\Bigl(  \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$$ yaitu jumlah suku yang masing-masing sama dengan $0$ atau $1$.
12. Buktikan *teorema Kummer* : suku ke- $k$ jumlah itu sama dengan $1$ tepat ketika penjumlahan $m$ dan $n$ dalam basis $p$ menghasilkan simpanan ke posisi $k$ ; sehingga $v_p\binom{m+n}m$ adalah banyaknya simpanan seluruhnya. *(Tulis $m = p^km_1 + m_0$ dan $n = p^kn_1 + n_0$ dengan $0 \leq m_0, n_0 < p^k$ lalu periksa $\lfloor (m_0 +  n_0)/p^k \rfloor$.)*
13. Simpulkan bahwa untuk $0 < j < p^k$: $$v_p\binom{p^k}{j} = k - v_p(j) ,$$ dengan mencacah simpanan pada penjumlahan $j + (p^k - j)$. (Khususnya $p \mid \binom p j$ untuk $0 < j < p$: yaitu langkah kunci [Teorema 6.23](#thm-b1-arith-fermat), yang dipulihkan.)
14. Buktikan bahwa $v_2\binom{2n}n = s_2(n)$ . Simpulkan bahwa [koefisien binomial](https://one-course.com/books/math/3/id/chapter/2-pencacahan#def-b1-counting-objects) pusatnya selalu genap, dan bahwa $\binom{2n}n \equiv 2 \pmod 4$ tepat ketika $n$ merupakan pangkat $2$ .
15. Tunjukkan, dengan memakai kesamaan Vandermonde ( [Latihan 2.7](https://one-course.com/books/math/3/id/chapter/2-pencacahan#exo-b1-counting-7) ) dan pertanyaan 13, bahwa $\binom{2p}p \equiv 2 \pmod p$ untuk setiap [prima](#def-b1-arith-prime) $p$ .
16. Hitung $v_3\binom{1000}{500}$ dua kali: sekali dengan Kummer (tulis $500$ dalam basis $3$ lalu cacah simpanan pada $500 +  500$ ), sekali dengan bentuk digital Legendre (hitung $s_3(500)$ dan $s_3(1000)$ ); lalu periksa bahwa keduanya memberikan nilai yang sama.

**Bagian IV — Keparitasan segitiga Pascal, dan sebuah batas kerapatan [bilangan prima](#def-b1-arith-prime).**

17. Buktikan kriteria digitalnya: $\binom nk$ bersifat *ganjil* jika dan hanya jika setiap angka biner $k$ paling besar sama dengan angka $n$ yang bersesuaian. Nyatakan lalu buktikan kriteria yang analog untuk $p \nmid \binom nk$ dalam basis $p$ .
18. Simpulkan bahwa baris $n$ segitiga Pascal memuat tepat $2^{s_2(n)}$ entri ganjil; lalu periksa pada baris $4$ dan $5$ .
19. Simpulkan bahwa semua entri bagian dalamnya $\binom nk$ ( $0 < k < n$ ) genap jika dan hanya jika $n$ merupakan pangkat $2$ .
20. Buktikan bahwa setiap pangkat [prima](#def-b1-arith-prime) yang [membagi](#def-b1-arith-divides) $\binom{m+n}m$ paling besar $m + n$ : yakni jika $p^a \mid \binom{m+n}m$ maka $p^a \leq  m + n$ . *(Berapa banyak suku tak nol yang dapat dimiliki jumlah pertanyaan 11?)*
21. Simpulkan bahwa $\binom{2n}n$ [membagi](#def-b1-arith-divides) $\operatorname{lcm}(1, 2, \dots, 2n)$, lalu gabungkan dengan batas bawah $\binom{2n}n \geq \frac{4^n}{2n+1}$ (yang akan Anda buktikan: entri pusatnya adalah yang terbesar di antara $2n + 1$ entri baris $2n$) untuk memperoleh $$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$$ jadi kelipatan persekutuan bilangan bulat pertama tumbuh *secara eksponensial* — yaitu sekilas kuantitatif pertama tentang limpahnya [bilangan prima](#def-b1-arith-prime).

**Bagian V — Sintesis.**

22. Carilah $n$ terkecil yang membuat $n!$ berakhir dengan sekurang-kurangnya $2026$ nol. *(Taksir $Z(n) \approx n/4$, lalu sesuaikan memakai rumus eksaknya.)*
23. Satu pemeriksaan silang terakhir: tunjukkan bahwa $7$ *tidak* [membagi](#def-b1-arith-divides) $\binom{100}{50}$ , mula-mula dengan menulis $50$ dalam basis $7$ lalu memeriksa bahwa penjumlahan $50 + 50$ bebas simpanan, lalu dengan menghitung $v_7(100!)$ dan $v_7(50!)$ memakai rumus Legendre.
24. Di mana persisnya soal ini memakai: (i) ketunggalan pemfaktoran; (ii) penguraian pembagian Euclid $n = p^k n_1 + n_0$ ; (iii) sebuah argumen pencacahan dari [Bab 2](https://one-course.com/books/math/3/id/chapter/2-pencacahan#ch-b1-counting) ? Satu kalimat untuk masing-masing.
25. Sintesis, dalam satu paragraf pendek: rumus Legendre mengubah pertanyaan [keterbagian](#def-b1-arith-divides) menjadi aritmetika angka, dan teorema Kummer membaca jawabannya dari simpanan satu penjumlahan — berilah komentar atas penerjemahan ini, atas pemeriksaan pada pertanyaan 16, dan atas apa yang disiratkan batas pertanyaan 21 tentang [bilangan prima](#def-b1-arith-prime) ( [pernyataan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-statement) lengkapnya, yaitu teorema [bilangan prima](#def-b1-arith-prime) , jauh di luar jilid ini; adapun analog polinomial bagi kotak perkakas bab ini adalah [Bab 8](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly) ).

**Solusi Soal 6.1.**

**1.** $10! = 3\,628\,800$: dengan dua nol penutup. Valuasinya faktor demi faktor: pangkat $2$ datang dari $2, 4 = 2^2, 6, 8 = 2^3,
10$, sehingga totalnya $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$; sedangkan pangkat $5$ datang dari $5$ dan $10$: $v_5(10!) = 2$. Nol penutupnya $=
\min(v_2, v_5) = 2$, yang sejalan.

**2.** Tulis pembagian Euclid $\lfloor x\rfloor = nq +
r$, $0 \leq r \leq n - 1$. Maka $x = nq + r + \{x\}$ dengan $0 \leq
r + \{x\} < n$, sehingga $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor
x \rfloor / n \bigr\rfloor$.

**3.** Misalkan $\alpha = v_p(a) \leq \beta = v_p(b)$ (tukarkan bila perlu) lalu tulis $a = p^\alpha a'$, $b = p^\beta b'$ dengan $p
\nmid a', b'$. Maka $a + b = p^\alpha\bigl(a' + p^{\beta -
\alpha}b'\bigr)$, jadi $v_p(a + b) \geq \alpha = \min$. Jika $\alpha <
\beta$, kurungnya bernilai $a' + p^{\beta-\alpha}b' \equiv a'
\not\equiv 0 \pmod p$: sehingga valuasinya tepat $\alpha$.

**4.** Kelipatan $m$ di $\intint1n$ adalah $m, 2m, \dots,
qm$ dengan $q$ bilangan bulat terbesar yang memenuhi $qm \leq n$, yakni $q =
\lfloor n/m \rfloor$.

**5.** Menurut ketunggalan pemfaktoran, $v_p(n!) = \sum_{j=1}^{n}
v_p(j)$. Cacahlah secara berbeda: setiap $j$ menyumbang $v_p(j) =
\#\{k \geq 1 : p^k \mid j\}$, sehingga

$$
v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\}
= \sum_{k\geq1} \#\{j \leq n : p^k \mid j\}
= \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor
$$

menurut pertanyaan 4 — itulah rumus Legendre. Jumlahnya hingga: suku dengan $p^k > n$ lenyap.

**6.** $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (dari pembagian dengan $5, 25, 125, 625$); $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 +
7 + 3 + 1 = 994$. Nol penutup $1000!$: setiap nol menghabiskan satu faktor $2$ dan satu faktor $5$, jadi ada $\min(994, 249) = 249$ nol.

**7.** Dengan $n = \sum_i a_ip^i$, pertanyaan 2 memberikan $\lfloor
n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (yakni memenggal ekspansi basis $p$). Dengan menjumlahkan atas $k \geq 1$ lalu menukarkan kedua jumlah hingga itu:

$$
v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k}
= \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1}
= \frac{n - s_p(n)}{p - 1} .
$$

**8.** Untuk $p = 2$: $v_2(n!) = n - s_2(n)$. Karena $n \geq 1$ mempunyai $s_2(n) \geq 1$, selalu berlaku $v_2(n!) \leq n - 1 < n$: jadi $2^n \nmid
n!$. Dan $v_2(n!) = n - 1$ jika dan hanya jika $s_2(n) = 1$, yakni jika dan hanya jika $n$ pangkat $2$.

**9.** Di sini $n$ mempunyai $\lfloor \log_p n \rfloor + 1$ angka basis $p$, masing-masing paling besar $p - 1$, jadi $1 \leq s_p(n) \leq
(p-1)\bigl(\log_p(n) + 1\bigr)$. Dengan mensubstitusikannya pada pertanyaan 7:

$$
\frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1},
$$

lalu dengan membaginya dengan $n$: $\frac{v_p(n!)}n \to \frac1{p-1}$.

**10.** $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$: jadi cacah nol penutupnya melonjak sebesar $v_5(n)$ pada setiap kelipatan $5$ dan tetap di antaranya. Di sini $Z(24) = \lfloor24/5\rfloor = 4$ dan $Z(25) =
5 + 1 = 6$: pada $n = 25$ cacahnya melonjak dari $4$ langsung ke $6$ (karena $v_5(25) = 2$), dan karena $Z$ tidak turun dengan $Z \leq 4$ sebelumnya dan $Z \geq 6$ sesudahnya, nilai $5$ tak pernah tercapai: jadi tak ada faktorial yang berakhir dengan tepat lima nol.

**11.** Tulis $x = \lfloor x\rfloor + \{x\}$: maka $\lfloor x +
y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} +
\{y\}\rfloor$, dan $0 \leq \{x\} + \{y\} < 2$ membuat lantai terakhirnya $0$ atau $1$. Lalu, dengan Legendre yang diterapkan tiga kali,

$$
v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!)
= \sum_{k\geq1}\Bigl(
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),
$$

yaitu jumlah hingga berisi $0$ dan $1$ (terapkan klaim pertamanya pada $x =
m/p^k$, $y = n/p^k$).

**12.** Tetapkan $k \geq 1$ lalu tulis $m = p^km_1 + m_0$, $n =
p^kn_1 + n_0$ dengan $0 \leq m_0, n_0 < p^k$ (lewat pembagian Euclid: $m_0$ adalah bilangan yang dibentuk oleh $k$ angka rendah $m$). Maka

$$
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac m{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac n{p^k}\Bigr\rfloor
= \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor ,
$$

yang bernilai $1$ bila $m_0 + n_0 \geq p^k$ dan $0$ bila tidak. Tetapi $m_0 +
n_0 \geq p^k$ mengatakan persis bahwa menjumlahkan $k$ angka rendah $m$ dan $n$ meluap ke posisi $k$ — yaitu sebuah simpanan ke posisi $k$ pada algoritma penjumlahan seperti di sekolah. Dengan menjumlahkan atas $k$: jadi $v_p\binom{m+n}m$ adalah banyaknya simpanan pada penjumlahan basis $p$ untuk $m + n$. (Kummer, 1852.)

**13.** Terapkan Kummer pada $m = j$, $n = p^k - j$, dengan jumlah $p^k =
(1\underbrace{0\cdots0}_{k})_p$. Misalkan $a = v_p(j)$, sehingga angka basis $p$ dari $j$ pada posisi $0, \dots, a-1$ semuanya $0$ dan angka pada posisi $a$ tak nol. Angka $p^k - j$ di bawah posisi $a$ juga $0$ (karena $p^k - j = p^a(p^{k-a} - j/p^a)$). Pada posisi $a$, kedua angka tak nolnya harus berjumlah $p$ (agar angka hasilnya $0$): yaitu satu simpanan; lalu pada setiap posisi $a+1, \dots, k-1$, angkanya beserta simpanan yang masuk berjumlah $p$ (angka hasilnya $0$ lagi): jadi simpanannya merambat. Totalnya: $k - a$ simpanan, sehingga $v_p\binom{p^k}j = k -
v_p(j)$. Untuk $k = 1$: $v_p\binom pj = 1$ untuk $0 < j < p$, yaitu [keterbagian](#def-b1-arith-divides) yang dipakai pada [Teorema 6.23](#thm-b1-arith-fermat).

**14.** Menurut bentuk digitalnya (pertanyaan 7), dengan memakai $s_2(2n) =
s_2(n)$ (karena menambahkan satu angka nol):

$$
v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n -
s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 :
$$

$\binom{2n}n$ selalu genap, dan $v_2 = 1$ (yakni $\binom{2n}n
\equiv 2 \pmod 4$) tepat ketika $s_2(n) = 1$, yakni ketika $n$ merupakan pangkat $2$.

**15.** Vandermonde dengan $m = n = k = p$: $\binom{2p}p =
\sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$. Untuk $0 < j < p$ berlaku $p \mid \binom pj$ (pertanyaan 13), jadi $\binom
pj^2 \equiv 0 \pmod p$; sedangkan suku ujungnya memberikan $1 + 1$: sehingga $\binom{2p}p \equiv 2 \pmod p$.

**16.** Basis $3$: $500 = 486 + 9 + 3 + 2$, dengan angka (dari rendah ke tinggi) $(2, 1, 1, 0, 0, 2)$, jadi $s_3(500) = 6$; dan $1000 = 729 +
243 + 27 + 1$, dengan angka $(1, 0, 0, 1, 0, 1, 1)$, jadi $s_3(1000) = 4$. *Kummer:* jumlahkan $500 + 500$ dalam basis $3$: posisi $0$: $2 + 2 =
4$, angkanya $1$ dengan simpanan $1$; posisi $1$: $1 + 1 + 1 = 3$, angkanya $0$ dengan simpanan $1$; posisi $2$: $1 + 1 + 1 = 3$, angkanya $0$ dengan simpanan $1$; posisi $3$: $0 + 0 + 1 = 1$, tanpa simpanan; posisi $4$: $0$; posisi $5$: $2 + 2 = 4$, angkanya $1$ dengan simpanan $1$; posisi $6$: simpanannya mendarat: angkanya $1$. Empat simpanan: jadi $v_3\binom{1000}{500} = 4$. *Legendre:* $v_3(1000!) = \frac{1000 - 4}2 = 498$ dan $v_3(500!) = \frac{500 - 6}2 = 247$, sehingga $v_3\binom{1000}{500} =
498 - 2\times247 = 4$. Kedua perhitungannya cocok — dan angka penjumlahannya $(1, 0, 0, 1, 0, 1, 1)$ menghasilkan $1000$, sebagaimana seharusnya.

**17.** Menurut Kummer (dengan $p = 2$, $m = k$, $n' = n - k$): $\binom nk$ ganjil jika dan hanya jika penjumlahan $k + (n - k)$ dalam basis $2$ tak mempunyai simpanan, yakni jika dan hanya jika pada setiap posisi angkanya memenuhi $k_i + (n -
k)_i = n_i$; dan dalam hal itu $k_i \leq n_i$ untuk setiap $i$. Sebaliknya, jika $k_i \leq n_i$ untuk setiap $i$, maka bilangan berangka $n_i -
k_i$ sama dengan $n - k$ dan penjumlahannya bebas simpanan. Bukti yang sama dalam basis $p$: $p \nmid \binom nk$ jika dan hanya jika setiap angka basis $p$ dari $k$ paling besar sama dengan angka $n$ yang bersesuaian.

**18.** Dengan mencacah $k \in \intint0n$ yang angkanya menuruti $k_i \leq n_i$: setiap angka $k$ dipilih secara bebas di antara $n_i + 1$ nilai, sehingga ada $\prod_i (n_i + 1)$ pilihan; dan dalam basis $2$ ini sama dengan $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$. Baris $4 =
(100)_2$: ada $2^1 = 2$ entri ganjil — memang $1, 4, 6, 4, 1$ berentri ganjil hanya di kedua ujungnya. Baris $5 = (101)_2$: ada $2^2 = 4$ — memang $1, 5, 10, 10, 5, 1$.

**19.** Semua entri bagian dalamnya genap $\iff$ barisnya mempunyai tepat $2$ entri ganjil (karena kedua ujungnya selalu ganjil) $\iff 2^{s_2(n)} =
2 \iff s_2(n) = 1 \iff n$ merupakan pangkat $2$.

**20.** Pada jumlah pertanyaan 11, suku ke-$k$ lenyap begitu $p^k > m + n$ (karena ketiga lantainya lalu sama; memang yang pertama $0$ bila $p^k > m+n$; lebih sederhananya setiap sukunya $0$). Jadi paling banyak $\lfloor \log_p(m+n)\rfloor$ suku yang tak nol, masing-masing bernilai $1$: sehingga $a = v_p\binom{m+n}m \leq \log_p(m+n)$, yakni $p^a \leq
m + n$.

**21.** Untuk setiap [prima](#def-b1-arith-prime) $p$ berlaku $v_p\bigl(\operatorname{lcm}(1,
\dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (karena pangkat terbesar $p$ yang tak melampaui $2n$ muncul di antara $1, \dots, 2n$). Pertanyaan 20 dengan $m = n$ memberikan $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ untuk setiap $p$: jadi menurut [Proposisi 6.16](#prop-b1-arith-valuation), $\binom{2n}n
\mid \operatorname{lcm}(1, \dots, 2n)$. Untuk ukurannya: rasio $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ tepat untuk $k < n$, jadi entri pusatnya adalah yang terbesar di antara $2n + 1$ entri baris $2n$, sehingga $4^n = \sum_k \binom{2n}k \leq
(2n+1)\binom{2n}n$. Dengan menggabungkannya:

$$
\operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq
\frac{4^n}{2n + 1} .
$$

Seandainya [bilangan prima](#def-b1-arith-prime) di bawah $2n$ hanya sedikit, KPK-nya tak akan sebesar itu: jadi pertumbuhan eksponensial KPK-nya adalah jejak kuantitatif dari limpahnya [bilangan prima](#def-b1-arith-prime).

**22.** $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac
n4$, jadi bidiklah di dekat $n = 4 \times 2026 = 8104$: $Z(8104) = 1620 +
324 + 64 + 12 + 2 = 2022$. Naikkan dengan kelipatan $5$: $Z(8110)
= 2024$, $Z(8115) = 2025$, dan

$$
Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 .
$$

Karena $Z$ tetap di antara kelipatan $5$ dan $Z(8119) =
Z(8115) = 2025$, maka $n$ terkecil yang berisi sekurang-kurangnya $2026$ nol penutup adalah $n = 8120$.

**23.** Basis $7$: $50 = 49 + 1$, dengan angka (dari rendah ke tinggi) $(1, 0,
1)$. Menjumlahkan $50 + 50$: posisi $0$: $1 + 1 = 2 < 7$, tanpa simpanan; posisi $1$: $0 + 0 = 0$; posisi $2$: $1 + 1 = 2 < 7$, tanpa simpanan. Bebas simpanan, jadi menurut Kummer $v_7\binom{100}{50} = 0$: sehingga $7 \nmid
\binom{100}{50}$. Legendre sependapat: $v_7(100!) = \lfloor 100/7
\rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ dan $v_7(50!) = 7
+ 1 = 8$, jadi $v_7\binom{100}{50} = 16 - 2\times8 = 0$.

**24.** (i) Ketunggalan pemfaktoran melandasi definisi $v_p$ itu sendiri beserta keaditifannya, sehingga juga rumus Legendre dan setiap kesimpulan [keterbagiannya](#def-b1-arith-divides) ([Proposisi 6.16](#prop-b1-arith-valuation)). (ii) Pembagian Euclid menghasilkan kesamaan pemenggalan pada pertanyaan 2 dan pemilahan $m = p^km_1 +
m_0$ yang mengisolasi simpanannya (pertanyaan 12). (iii) Pencacahan: cacah kelipatan $m$ (pertanyaan 4), hasil kali pilihan angkanya (pertanyaan 18), dan batas jumlah barisnya $4^n \leq
(2n+1)\binom{2n}n$ (pertanyaan 21) semuanya argumen bergaya [Bab 2](https://one-course.com/books/math/3/id/chapter/2-pencacahan#ch-b1-counting).

**25.** Legendre mengubah “pangkat $p$ yang mana yang [membagi](#def-b1-arith-divides) $n!$” menjadi aritmetika angka basis $p$; Kummer memampatkan jawabannya untuk [koefisien binomial](https://one-course.com/books/math/3/id/chapter/2-pencacahan#def-b1-counting-objects) menjadi simpanan pada satu penjumlahan — [keterbagian](#def-b1-arith-divides), yang tampaknya sifat global bilangan raksasa, ternyata terbaca secara lokal, angka demi angka. Pertanyaan 16 adalah paradigmanya: empat simpanan, yang dihitung dengan tangan, menentukan pangkat $3$ yang persis pada bilangan beratus angka. Dan pertanyaan 21 memperlihatkan lingkaran gagasan yang sama menyenggol perairan dalam: batas bawah eksponensial bagi $\operatorname{lcm}(1, \dots, 2n)$ adalah langkah pertama yang sepenuhnya dasar menuju teorema [bilangan prima](#def-b1-arith-prime), yang buktinya jauh di luar jilid ini. Seluruh kotak perkakasnya — pembagian, FPB, valuasi — diputar ulang untuk polinomial pada [Bab 8](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly), yang di sana analog ekspansi angkanya adalah ekspansi dalam pangkat $(X - a)$.