---
title: "Aritmetika"
book: "Matematika Sekolah Menengah Atas"
subject: math
language: id
chapter: 29
exercises: 10
source: https://one-course.com/books/math/2/id/chapter/29-aritmetika
---

# Bab 29 — Aritmetika

Aritmetika mengkaji [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets): [keterbagian](#def-g12-arith-divides), [bilangan prima](#def-g12-arith-prime), sisa. Lama dianggap yang paling murni di antara matematika murni, kini ia melindungi setiap pembayaran daring: sistem sandi RSA bersandar pada teorema Bézout, Gauss dan Fermat yang dibuktikan di bab ini.

## 29.1 Keterbagian dan pembagian Euklides

**Definisi 29.1 (Keterbagian).**

Misalkan $a, b \in \Z$. Kita katakan $b$ *membagi* $a$, ditulis $b \mid a$, jika ada $k \in \Z$ dengan $a = kb$. Kita katakan pula bahwa $a$ adalah *kelipatan* dari $b$.

**Proposisi 29.2.**

Jika $c \mid a$ dan $c \mid b$, maka $c$ [membagi](#def-g12-arith-divides) setiap gabungan bulat $au + bv$ ($u, v \in \Z$). Jika $a \mid b$ dan $b \mid a$ dengan $a,b \in \N$, maka $a = b$. Jika $a \mid b$ dan $b \neq 0$, maka $\abs a \leq \abs b$.

**Bukti.** Tulislah $a = kc$, $b = lc$: maka $au + bv = (ku + lv)c$. Butir lainnya menyusul dari $\abs{a} = \abs{k}\,\abs{b}$ dengan $\abs k \geq 1$ ketika $b = ka \neq 0$. ∎

**Teorema 29.3 (Pembagian Euklides).**

Misalkan $a \in \Z$ dan $b \in \N^*$. Ada tepat satu pasangan $(q, r) \in \Z \times \N$ sedemikian sehingga

$$
a = bq + r \qquad\text{dan}\qquad 0 \leq r < b .
$$

Di sini $q$ disebut *hasil bagi* dan $r$ disebut *sisanya*.

**Bukti.** *Keberadaannya.* Himpunan kelipatan $b$ yang tidak melampaui $a$ punya anggota terbesar $bq$ (himpunan itu tak kosong dan [terbatas di atas](https://one-course.com/books/math/2/id/chapter/20-barisan#def-g12-seq-bounded)); ambil $r = a - bq$. Menurut kemaksimalannya, $b(q+1) > a$, sehingga $0 \leq r < b$. *Ketunggalannya.* Jika $bq + r = bq' + r'$ dengan $0 \leq r, r' < b$, maka $b(q - q') = r' - r$ dan $\abs{r' - r} < b$: kelipatan $b$ yang [nilai mutlaknya](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-abs) kurang dari $b$ haruslah $0$, sehingga $r = r'$ dan $q = q'$. ∎

## 29.2 Kekongruenan

**Definisi 29.4 (Kekongruenan).**

Misalkan $n \in \N^*$. Dua [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $a, b$ disebut *kongruen modulo $n$*, ditulis $a \equiv b \pmod n$, jika $n \mid (a - b)$ — setara dengan mengatakan bahwa $a$ dan $b$ bersisa sama pada [pembagian Euklides](#thm-g12-arith-euclid) oleh $n$.

**Proposisi 29.5 (Keselarasan dengan operasinya).**

Jika $a \equiv b \pmod n$ dan $c \equiv d \pmod n$, maka

$$
a + c \equiv b + d, \qquad
ac \equiv bd, \qquad
a^k \equiv b^k \ (k \in \N) \pmod n .
$$

**Bukti.** Bilangan $n$ [membagi](#def-g12-arith-divides) $(a-b) + (c-d) = (a+c) - (b+d)$, dan $ac - bd = a(c - d) + d(a - b)$ juga kelipatan $n$. Kaidah pemangkatannya menyusul lewat induksi dari kaidah hasil kalinya. ∎

**Metode 29.6 (Menghitung pangkat modulo nnn).**

Untuk menghitung $a^k \bmod n$, susutkan bilangan pokoknya modulo $n$, lalu carilah pangkat kecil dari $a$ yang kongruen dengan $\pm1$, dan pakailah itu untuk meruntuhkan eksponennya. Misalnya $2^{100} \bmod 7$: karena $2^3 = 8 \equiv 1 \pmod 7$ dan $100 = 3\times33 + 1$,

$$
2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .
$$

## 29.3 FPB, Bézout dan Gauss

**Definisi 29.7 (Pembagi persekutuan terbesar).**

Misalkan $a, b$ [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) yang tidak keduanya nol. *Pembagi persekutuan terbesar* $\gcd(a, b)$ adalah [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) terbesar yang [membagi](#def-g12-arith-divides) $a$ sekaligus $b$. Ketika $\gcd(a,b) = 1$, maka $a$ dan $b$ disebut *saling prima*.

**Proposisi 29.8 (Algoritme Euklides).**

Jika $a = bq + r$ ($b \neq 0$), maka $\gcd(a, b) = \gcd(b, r)$. Karena itu melelarkan pembagian Euklidesnya menghitung $\gcd(a,b)$: yaitu sisa tak nol yang terakhir.

**Bukti.** Setiap pembagi persekutuan $a$ dan $b$ [membagi](#def-g12-arith-divides) $r = a - bq$ ([Proposisi 29.2](#prop-g12-arith-divprops)), sehingga menjadi pembagi persekutuan $b$ dan $r$; begitu pula sebaliknya, sebab $a = bq + r$. Kedua pasangan itu punya pembagi persekutuan yang sama, jadi punya FPB yang sama. Algoritmenya berhenti sebab sisanya membentuk [barisan](https://one-course.com/books/math/2/id/chapter/20-barisan#def-g12-seq-sequence) [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) tak negatif yang turun tegas. ∎

**Contoh 29.9.**

$\gcd(252, 198)$: $252 = 198 + 54$; $198 = 3\times54 + 36$; $54 = 36 + 18$; $36 = 2 \times 18 + 0$. Jadi $\gcd(252,198) = 18$.

**Teorema 29.10 (Identitas Bézout).**

Misalkan $a, b$ [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) yang tidak keduanya nol, dan $d = \gcd(a,b)$. Ada $u, v \in \Z$ sedemikian sehingga

$$
au + bv = d .
$$

Khususnya, $a$ dan $b$ [saling prima](#def-g12-arith-gcd) jika dan hanya jika $au + bv = 1$ untuk suatu [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $u, v$.

**Bukti.** Jalankan [algoritme Euklides](#prop-g12-arith-euclidalgo) secara mundur: setiap sisanya adalah gabungan bulat dari dua sisa sebelumnya, dan data awalnya $a, b$ adalah gabungan dari dirinya sendiri; lewat substitusi menurun, sisa tak nol yang terakhir $d$ adalah gabungan bulat dari $a$ dan $b$. (Pada [Contoh 29.9](#ex-g12-arith-euclidalgo): $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 =
4(252 - 198) - 198 = 4\times252 - 5\times198$.)

Untuk kesetaraannya: jika $\gcd(a,b) = 1$, maka Bézout menyediakan $u, v$; sebaliknya, setiap pembagi persekutuan $a$ dan $b$ [membagi](#def-g12-arith-divides) $au + bv = 1$, sehingga memaksa $\gcd(a,b) = 1$. ∎

**Teorema 29.11 (Lema Gauss).**

Misalkan $a, b, c \in \Z$. Jika $a \mid bc$ dan $\gcd(a, b) = 1$, maka $a \mid c$.

**Bukti.** Bézout memberi $au + bv = 1$; kalikanlah dengan $c$: $acu + bcv = c$. Kedua suku pada ruas kirinya kelipatan $a$ (yang kedua sebab $a \mid bc$), sehingga begitu pula $c$. ∎

**Akibat 29.12.**

Jika $a \mid c$, $b \mid c$ dan $\gcd(a,b) = 1$, maka $ab \mid c$.

**Bukti.** Tulislah $c = ak$. Dari $b \mid ak$ dan $\gcd(a,b)=1$, Gauss memberi $b \mid k$, sebutlah $k = bl$; maka $c = abl$. ∎

## 29.4 Bilangan prima

**Definisi 29.13 (Prima).**

[Bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $p \geq 2$ disebut *prima* jika pembagi positifnya hanyalah $1$ dan $p$.

**Proposisi 29.14.**

Setiap [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $n \geq 2$ punya pembagi [prima](#def-g12-arith-prime); jika $n$ bukan [prima](#def-g12-arith-prime), ia punya pembagi [prima](#def-g12-arith-prime) $\leq \sqrt n$. Jika suatu [prima](#def-g12-arith-prime) $p$ [membagi](#def-g12-arith-divides) hasil kali $ab$, maka $p \mid a$ atau $p \mid b$ (*lema Euklides*).

**Bukti.** Pembagi terkecil $d \geq 2$ dari $n$ adalah [prima](#def-g12-arith-prime) (setiap pembagi sejati $d$ akan menjadi pembagi $n$ yang lebih kecil). Jika $n = de$ tersusun dengan $2 \leq d \leq e$, maka $d^2 \leq de = n$, sehingga $d \leq \sqrt n$. Untuk lema Euklidesnya: jika $p \nmid a$, maka $\gcd(p, a) = 1$ (sebab pembagi $p$ hanyalah $1$ dan $p$), dan lema Gauss memberi $p \mid b$. ∎

**Teorema 29.15 (Euklides).**

Ada tak berhingga banyak [bilangan prima](#def-g12-arith-prime).

**Bukti.** Diberikan sebarang daftar berhingga $p_1, \dots, p_k$ berisi [bilangan prima](#def-g12-arith-prime), tinjaulah $N = p_1 p_2 \cdots p_k + 1$. Ada [prima](#def-g12-arith-prime) $p$ yang [membagi](#def-g12-arith-divides) $N$; tetapi tak satu pun $p_i$ [membagi](#def-g12-arith-divides) $N$ (sebab sisanya $1$), sehingga $p$ [prima](#def-g12-arith-prime) yang tak ada di daftarnya. Jadi tak ada daftar berhingga yang menghabiskan [bilangan primanya](#def-g12-arith-prime). ∎

**Teorema 29.16 (Teorema dasar aritmetika).**

Setiap [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $n \geq 2$ adalah hasil kali [bilangan prima](#def-g12-arith-prime), dan pemfaktoran itu tunggal sampai pada urutan faktornya:

$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r},
\qquad p_1 < p_2 < \dots < p_r \text{ prima},\ \alpha_i \geq 1 .
$$

**Bukti.** *Keberadaannya*, lewat induksi kuat: $n$ yang [prima](#def-g12-arith-prime) adalah pemfaktorannya sendiri; jika tidak, $n = de$ dengan $2 \leq d, e < n$, dan keduanya terfaktorkan menurut hipotesis induksinya. *Ketunggalannya*: andaikan $p_1\cdots p_s = q_1 \cdots q_t$ ([bilangan prima](#def-g12-arith-prime), pengulangan diperbolehkan). Menurut lema Euklides, $p_1$ [membagi](#def-g12-arith-divides) suatu $q_j$, dan karena [prima](#def-g12-arith-prime), $p_1 = q_j$; coretlah lalu ulangi. Kedua pemfaktorannya cocok suku demi suku. ∎

**Teorema 29.17 (Teorema kecil Fermat).**

Misalkan $p$ [prima](#def-g12-arith-prime) dan $a \in \Z$ dengan $p \nmid a$. Maka

$$
a^{p-1} \equiv 1 \pmod p .
$$

Untuk setiap $a \in \Z$ (tanpa anggapan [saling prima](#def-g12-arith-gcd)), $a^p \equiv a \pmod p$.

**Bukti.** Tinjaulah $p - 1$ [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $a, 2a, 3a, \dots, (p-1)a$ modulo $p$. Tak satu pun $\equiv 0$ (sebab jika $p \mid ka$ dengan $1 \leq k \leq p-1$, lema Euklides memaksa $p \mid k$, dan itu mustahil), dan semuanya berbeda sepasang demi sepasang modulo $p$ (sebab jika $ka \equiv la$, maka $p \mid (k - l)a$, sehingga $p \mid k - l$ dan $k = l$). Karena itu, modulo $p$, semuanya adalah bilangan $1, 2, \dots, p-1$ dalam suatu urutan. Dengan mengalikan semua [kekongruenannya](#def-g12-arith-congruence):

$$
a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .
$$

Karena $p$ tidak [membagi](#def-g12-arith-divides) satu pun dari $1, \dots, p-1$, pemakaian berulang lema Euklides membolehkan pencoretan $(p-1)!$, sehingga tersisa $a^{p-1} \equiv 1$. Bentuk keduanya menyusul dengan mengalikannya dengan $a$ (dan sepele ketika $p \mid a$). ∎

**Contoh 29.18 (Penerapan pada persandian).**

Teorema Fermat membuat pemangkatan modulo $n$ dapat dibalik ketika eksponennya dipilih dengan tepat — dan itulah jantung sistem sandi *RSA*. Dengan $p, q$ [bilangan prima](#def-g12-arith-prime) besar dan $n = pq$, orang menerbitkan $n$ dan sebuah eksponen $e$; penyandiannya $x \mapsto x^e \bmod n$. Pembacaan sandinya menuntut eksponen $d$ dengan $ed \equiv 1 \pmod{(p-1)(q-1)}$, yang hanya dapat dihitung oleh orang yang tahu $p$ dan $q$ — lagi pula memperoleh kembali $p, q$ dari $n$ berarti [memfaktorkan](https://one-course.com/books/math/2/id/chapter/2-aljabar-persamaan-dan-pertidaksamaan#def-g10-algebra-expand) bilangan yang panjangnya ratusan angka, dan tak ada algoritme yang diketahui melakukannya dalam waktu yang masuk akal.

## 29.5 Latihan

**Latihan 29.1 ★.**

Hitunglah hasil bagi dan sisa [pembagian Euklides](#thm-g12-arith-euclid) $2026$ oleh $17$, lalu $-2026$ oleh $17$.

**Solusi Latihan 29.1.**

$17 \times 119 = 2023$, jadi $2026 = 17 \times 119 + 3$: hasil baginya $119$, sisanya $3$. Untuk $-2026$: $-2026 = 17\times(-120) + 14$ (memang $17 \times 120 = 2040$ dan $2040 - 2026 = 14$): hasil baginya $-120$, sisanya $14$ (sisanya harus terletak di $\intco{0}{17}$, jadi *bukan* $-3$).

**Latihan 29.2 ★.**

Berapakah sisa $7^{100}$ modulo $10$? (Berapakah angka terakhir $7^{100}$?)

**Solusi Latihan 29.2.**

Modulo $10$: $7^2 = 49 \equiv 9 \equiv -1$. Karena itu $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$: jadi angka terakhir $7^{100}$ adalah $1$.

**Latihan 29.3 ★.**

Dengan [algoritme Euklides](#prop-g12-arith-euclidalgo), hitunglah $\gcd(1071, 462)$, lalu carilah [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $u, v$ dengan $1071u + 462v = \gcd(1071, 462)$.

**Solusi Latihan 29.3.**

Euklides: $1071 = 2\times462 + 147$; $462 = 3\times147 + 21$; $147 = 7\times21 + 0$. Jadi $\gcd = 21$.

Substitusi mundurnya: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462)
= 7\times462 - 3\times1071$. Jadi $u = -3$, $v = 7$: $1071\times(-3) + 462\times7 = 21$.

**Latihan 29.4 ★.**

Tunjukkan bahwa untuk setiap $n \in \Z$, $n^2$ kongruen dengan $0$ atau $1$ modulo $4$. Simpulkan bahwa [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) yang $\equiv 3 \pmod 4$ tak pernah menjadi jumlah dua kuadrat.

**Solusi Latihan 29.4.**

Setiap [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $\equiv 0, 1, 2$ atau $3 \pmod 4$, dan setelah dikuadratkan: $0^2 \equiv 0$, $1^2 \equiv 1$, $2^2 = 4 \equiv 0$, $3^2 = 9 \equiv 1$. Jadi $n^2 \equiv 0$ atau $1 \pmod 4$. Jumlah dua kuadrat lalu kongruen dengan $0 + 0$, $0 + 1$ atau $1 + 1$, *yaitu* dengan $0$, $1$ atau $2 \pmod 4$ — tak pernah dengan $3$.

**Latihan 29.5 ★★.**

Tunjukkan bahwa untuk semua $n \in \N$, $n(n+1)(2n+1)$ terbagi oleh $6$.

**Solusi Latihan 29.5.**

[Keterbagian](#def-g12-arith-divides) oleh $2$: di antara $n$ dan $n + 1$, salah satunya genap. [Keterbagian](#def-g12-arith-divides) oleh $3$: jika $n \equiv 0$, maka $3 \mid n$; jika $n \equiv 1 \pmod 3$, maka $2n + 1 \equiv 3 \equiv 0$; jika $n \equiv 2$, maka $n + 1 \equiv 0$. Pada semua kasusnya $3$ [membagi](#def-g12-arith-divides) hasil kalinya. Karena $\gcd(2,3) = 1$, [Akibat 29.12](#cor-g12-arith-coprimeprod) memberi $6 \mid n(n+1)(2n+1)$. (Ini sekaligus membuktikan kembali bahwa $\frac{n(n+1)(2n+1)}{6}$, jumlah kuadrat pada [Latihan 20.1](https://one-course.com/books/math/2/id/chapter/20-barisan#exo-g12-seq-1), adalah [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets).)

**Latihan 29.6 ★★.**

Selesaikan di $\Z$ [kekongruenan](#def-g12-arith-congruence) $5x \equiv 3 \pmod{11}$. (Petunjuk: carilah balikan $5$ modulo $11$.)

**Solusi Latihan 29.6.**

Kita mencari balikan $5$ modulo $11$: lewat pengujian (atau Bézout), $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$. Dengan mengalikan [kekongruenannya](#def-g12-arith-congruence) dengan $9$:

$$
x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.
$$

Penyelesaiannya adalah [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $x = 5 + 11k$, $k \in \Z$. (Periksalah: $5\times5 = 25 \equiv 3 \pmod{11}$.)

**Latihan 29.7 ★★.**

Selesaikan di $\Z \times \Z$ [persamaan](https://one-course.com/books/math/2/id/chapter/2-aljabar-persamaan-dan-pertidaksamaan#def-g10-algebra-equation) Diofantin

$$
17x - 40y = 1,
$$

lalu lukiskan semua penyelesaian $17x - 40y = 6$.

**Solusi Latihan 29.7.**

$\gcd(17, 40) = 1$, jadi penyelesaiannya ada. Euklides: $40 = 2\times17 + 6$; $17 = 2\times6 + 5$; $6 = 5 + 1$. Dengan substitusi mundur: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17
= 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$. Jadi $17\times(-7) - 40\times(-3) = 1$: itulah penyelesaian khususnya, $(x_0, y_0) = (-7, -3)$.

Penyelesaian umum $17x - 40y = 1$: dengan mengurangkan hubungan khususnya, $17(x + 7) = 40(y + 3)$; karena $\gcd(17, 40) = 1$, Gauss memberi $40 \mid x + 7$, sehingga $x = -7 + 40k$ lalu $y = -3 + 17k$, $k \in \Z$ (dan semuanya lolos pemeriksaan).

Untuk $17x - 40y = 6$, kalikan penyelesaian khususnya dengan $6$: $(x_1, y_1) = (-42, -18)$, lalu penalaran yang sama memberi

$$
x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .
$$

(Misalnya $k = 2$: $x = 38$, $y = 16$; memang $17\times38 - 40\times16
= 646 - 640 = 6$.)

**Latihan 29.8 ★★.**

Tunjukkan bahwa $\sqrt2$ [irasional](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#ex-g10-numbers-classify), dengan memakai ketunggalan pemfaktoran [primanya](#def-g12-arith-prime) (bandingkan eksponen $2$ pada kedua ruas $a^2 = 2b^2$).

**Solusi Latihan 29.8.**

Andaikan $\sqrt2 = \frac ab$ dengan $a, b \in \N^*$; maka $a^2 = 2b^2$. Pada pemfaktoran [prima](#def-g12-arith-prime) suatu kuadrat, setiap eksponennya genap; jadi eksponen $2$ pada $a^2$ genap, sedangkan pada $2b^2$ ganjil (satu lebih daripada bilangan genap). Dua pemfaktoran [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) yang sama dengan eksponen $2$ yang berbeda bertentangan dengan ketunggalan pada [Teorema 29.16](#thm-g12-arith-fta). Jadi pecahan semacam itu tak ada: $\sqrt2 \notin \Q$.

**Latihan 29.9 ★★★.**

Misalkan $p$ suatu [bilangan prima](#def-g12-arith-prime).

1. Tunjukkan bahwa untuk $1 \leq k \leq p - 1$ , $p$ [membagi](#def-g12-arith-divides) $\dbinom{p}{k}$ . (Petunjuk: pakailah $k\binom pk = p\binom{p-1}{k-1}$ , [Latihan 27.7](https://one-course.com/books/math/2/id/chapter/27-kombinatorika-dan-pencacahan#exo-g12-comb-7) , dan lema Gauss.)
2. Simpulkan, lewat induksi pada $a \geq 0$ , suatu bukti lain bagi teorema kecil Fermat dalam bentuk $a^p \equiv a \pmod p$ .

**Solusi Latihan 29.9.**

*1.* Dari $k\binom pk = p \binom{p-1}{k-1}$, jelas $p$ [membagi](#def-g12-arith-divides) $k\binom pk$. Untuk $1 \leq k \leq p-1$, $p \nmid k$ dan $p$ yang [prima](#def-g12-arith-prime) memberi $\gcd(p, k) = 1$, sehingga lema Gauss menghasilkan $p \mid \binom pk$.

*2.* Induksi pada $a$. Untuk $a = 0$: $0^p \equiv 0$. Andaikan $a^p \equiv a \pmod p$. Menurut teorema binomial,

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

sebab semua suku tengahnya lenyap modulo $p$ menurut butir 1. Menurut hipotesis induksinya, $(a+1)^p \equiv a + 1 \pmod p$. Ini membuktikan $a^p \equiv a$ untuk semua $a \in \N$, dan kasus $a < 0$ menyusul dengan menulis $a \equiv a + kp$ untuk suatu wakil positif yang sesuai.

**Latihan 29.10 ★★★.**

*(Soal sisa Tiongkok.)* Carilah semua [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $n$ sedemikian sehingga

$$
n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .
$$

(Petunjuk: selesaikan dua syarat pertamanya, lalu masukkan yang ketiga; koefisien Bézout akan membantu.)

**Solusi Latihan 29.10.**

$n \equiv 2 \pmod 3$ dan $n \equiv 3 \pmod 5$: tulislah $n = 2 + 3s$; maka $2 + 3s \equiv 3 \pmod 5$, *yaitu* $3s \equiv 1 \pmod 5$. Balikan $3$ modulo $5$ adalah $2$ (sebab $3\times2 = 6 \equiv 1$), jadi $s \equiv 2 \pmod 5$, sebutlah $s = 2 + 5t$, dan $n = 8 + 15t$: jadi kedua syarat pertamanya berarti $n \equiv 8 \pmod{15}$.

Dengan menambahkan $n \equiv 2 \pmod 7$: $8 + 15t \equiv 2 \pmod 7$, dan $15 \equiv 1 \pmod 7$, jadi $t \equiv -6 \equiv 1 \pmod 7$, sebutlah $t = 1 + 7u$. Karena itu $n = 23 + 105u$:

$$
n \equiv 23 \pmod{105}.
$$

(Periksalah: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$.)

## 29.6 Soal: Sandi rahasia dan angka pemeriksa

**Soal 29.1.**

Soal akhir pekan — kekongruenan menjaga setiap kode batang dan kartu kredit, dan teorema kecil Fermat menjalankan kunci bagi rahasia dunia

G. H. Hardy membanggakan diri pada tahun 1940 bahwa teori bilangan “tak ternoda” oleh penerapan. Delapan puluh tahun kemudian, setiap bunyi pemindai kode batang, setiap pembayaran kartu kredit dan setiap pesan bersandi membantahnya — justru dengan perkakas bab ini: [kekongruenan](#def-g12-arith-congruence) ([Proposisi 29.5](#prop-g12-arith-congops)), balikan Bézout ([Teorema 29.10](#thm-g12-arith-bezout)) dan teorema kecil Fermat ([Latihan 29.9](#exo-g12-arith-9)). Soal ini memeriksa kodenya, membobol kunci versi mainannya, lalu belajar mengapa kunci yang sungguhan bertahan.

**Bagian I — Kelancaran [kekongruenan](#def-g12-arith-congruence).**

1. Hitunglah $2026 \bmod 7$ ; lalu angka terakhir $7^{100}$ (carilah kitaran pangkat $7$ modulo $10$ ).
2. Pemangkatan cepat ( [Metode 29.6](#met-g12-arith-powers) ): hitunglah $5^{117} \bmod 13$ (mulailah dari $5^2 \equiv -1$ ).
3. Selesaikan $3x \equiv 5 \pmod 7$ .
4. Jalankan [algoritme Euklides](#prop-g12-arith-euclidalgo) pada $(97, 35)$ , substitusikan mundur untuk mencari [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) $u, v$ dengan $97u + 35v = 1$ , lalu simpulkan balikan $35$ modulo $97$ .
5. Nyatakan dengan tepat kapan $a$ punya balikan modulo $n$ , dan teorema mana yang menyerahkan balikannya.

**Bagian II — Angka pemeriksa.**

6. ISBN-10: kesepuluh angka $d_1 \dots d_{10}$ pada kode sebuah buku harus memenuhi $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0  \pmod{11}$ . Periksalah ISBN yang sungguhan, $0\,306\,40615\,2$ .
7. Buktikan bahwa rancangan ISBN itu mendeteksi *setiap* galat satu angka: jika satu angkanya berubah sebesar $d \not\equiv 0$ , maka jumlah berbobotnya berubah sebesar $w d$ dengan $1 \leq w \leq 10$ — mengapa itu tak pernah bisa $\equiv 0 \pmod{11}$ ( [Teorema 29.11](#thm-g12-arith-gauss) )?
8. Buktikan bahwa rancangan itu juga mendeteksi setiap pertukaran dua angka bertetangga (yang berbeda). Lalu jelaskan rahasia rancangannya: sifat $11$ yang mana yang membuat kedua buktinya jalan, dan apa yang bisa keliru dengan [modulus](https://one-course.com/books/math/2/id/chapter/28-bilangan-kompleks#def-g12-complex-modulus) $10$ ?
9. Kode batang EAN-13 memberi bobot $1, 3, 1, 3, \dots$ pada angkanya, modulo $10$ . Hitunglah angka pemeriksa yang melengkapi $978\,2940199\,05$ . Pertukaran bertetangga mana yang *gagal* dideteksi EAN? (Kapan $2(a - b) \equiv 0 \pmod{10}$ ?)
10. Kartu kredit memakai rancangan Luhn: dari kanan, lipatduakan tiap angka kedua (dengan mengurangi $9$ ketika lipatduanya melampaui $9$ ), jumlahkan semuanya, lalu tuntutlah kelipatan $10$ . Periksalah nomor ujinya, $4539\,1488\,0343\,6467$ .
11. Dalam satu kalimat: apa yang dibeli [modulus](https://one-course.com/books/math/2/id/chapter/28-bilangan-kompleks#def-g12-complex-modulus) [prima](#def-g12-arith-prime) bagi ISBN, yang tak dapat dimiliki EAN dan Luhn karena terantai pada $10$ ?

**Bagian III — Kunci Fermat.**

12. Sebuah jebakan sebelum hartanya: hitunglah $2^{10} \bmod 341$ , simpulkan $2^{340} \bmod 341$ — lalu faktorkanlah $341$ . Apa yang dikatakan contoh ini (sebuah *[prima](#def-g12-arith-prime) semu Fermat* ) tentang pemakaian teorema kecil Fermat sebagai uji keprimaan?
13. RSA dalam ukuran mini: ambil $p = 3$ , $q = 11$ , jadi $n = 33$ dan $(p-1)(q-1) = 20$ ; eksponen umumnya $e = 3$ . Carilah eksponen rahasianya $d$ dengan $3d \equiv 1 \pmod{20}$ (cara pertanyaan 4).
14. Sandikanlah pesan $m = 4$ : hitunglah $c = m^3 \bmod 33$ .
15. Bacalah sandinya: hitunglah $c^d \bmod 33$ (pakailah $c \equiv -2 \pmod{33}$ ) lalu perolehlah kembali pesannya.
16. Mengapa pembacaan sandinya selalu berhasil: tunjukkan bahwa $m^{21} \equiv m$ baik modulo $3$ maupun modulo $11$ (teorema kecil Fermat di masing-masing dunianya), lalu simpulkan modulo $33$ ( [Teorema 29.11](#thm-g12-arith-gauss) merekatkan kedua [kekongruenannya](#def-g12-arith-congruence) ). Di manakah bentuk khusus $21 = ed$ , yaitu $1 + 20k$ , masuk?
17. Keamanan kuncinya: semua orang tahu $n$ dan $e$ ; memperoleh kembali $d$ menuntut $(p-1)(q-1)$ , sehingga menuntut faktor $n$ . Bilangan $33$ kita terfaktorkan sekali lihat — lalu mengapa rancangan yang sama, dengan $n$ sepanjang enam ratus angka, melindungi bank sedunia? (Satu kalimat tentang ketaksetangkupan antara mengalikan dan [memfaktorkan](https://one-course.com/books/math/2/id/chapter/2-aljabar-persamaan-dan-pertidaksamaan#def-g10-algebra-expand) .)

**Bagian IV — Yang klasik.**

18. Pencacahan prajurit Tiongkok kuno (bandingkan [Latihan 29.10](#exo-g12-arith-10) ): sejumlah prajurit menyisakan $2$ ketika dibariskan dalam kelompok $3$ dan menyisakan $3$ ketika dibariskan dalam kelompok $5$ . Carilah semua cacah yang mungkin, lalu jelaskan mengapa jawabannya tunggal modulo $15$ .
19. Bukti satu baris, akhirnya: dari $10 \equiv 1 \pmod 9$ , buktikan bahwa setiap bilangan kongruen dengan jumlah angkanya modulo $9$ ; dari $10 \equiv -1 \pmod{11}$ , turunkan kaidah jumlah berselang-seling untuk $11$ . (Jilid sekolah menengah pertama membuktikan ini dengan aljabar yang gamblang — kagumilah pemampatannya.)
20. Penutup — Hardy melawan kode batang: rangkumlah perkakas bab ini (aritmetika [kekongruenan](#def-g12-arith-congruence) , balikan Bézout, teorema kecil Fermat, perekatan [modulus](https://one-course.com/books/math/2/id/chapter/28-bilangan-kompleks#def-g12-complex-modulus) yang [saling prima](#def-g12-arith-gcd) ) dan di mana masing-masingnya mengunci pada tempatnya dalam soal ini; lalu berikan vonis zaman kini atas kata “tak ternoda” itu.

**Solusi Soal 29.1.**

**1.** $2026 = 289 \times 7 + 3$, jadi $2026 \equiv 3
\pmod 7$. Pangkat $7$ modulo $10$: $7, 9, 3, 1$, sebuah kitaran sepanjang $4$; dan $100 \equiv 0 \pmod 4$, jadi angka terakhir $7^{100}$ adalah $1$.

**2.** $5^2 = 25 \equiv -1 \pmod{13}$, sehingga $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ dan $5^{117} \equiv 5 \pmod{13}$.

**3.** Balikan $3$ modulo $7$ adalah $5$ (sebab $15 \equiv 1$): jadi $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$.

**4.** $97 = 2 \times 35 + 27$; $35 = 27 + 8$; $27 = 3 \times 8 + 3$; $8 = 2 \times 3 + 2$; $3 = 2 + 1$. Dengan substitusi mundur: $1 = 97 \times 13 + 35 \times (-36)$. Jadi $35 \times (-36) \equiv 1 \pmod{97}$: balikan $35$ adalah $-36 \equiv 61 \pmod{97}$.

**5.** Bilangan $a$ punya balikan modulo $n$ tepat ketika $\gcd(a, n) = 1$: Bézout menyediakan $au + nv = 1$, yaitu $au \equiv 1$; sebaliknya adanya balikan memaksa FPB-nya [membagi](#def-g12-arith-divides) $1$.

**6.** $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 +
4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 +
2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$: jadi sah.

**7.** Jumlahnya berubah sebesar $wd$ dengan $1 \leq w \leq 10$ dan $1 \leq \abs d \leq 9$: karena $11$ [prima](#def-g12-arith-prime) dan tidak [membagi](#def-g12-arith-divides) satu pun faktornya, ia tak dapat [membagi](#def-g12-arith-divides) hasil kalinya ([Teorema 29.11](#thm-g12-arith-gauss) / [Proposisi 29.14](#prop-g12-arith-primedivides)), sehingga jumlah yang berubah itu tak pernah lagi $\equiv 0$: jadi setiap galat satu angka membunyikan alarmnya.

**8.** Menukar angka bertetangga $a, b$ (yang berbobot $w + 1, w$) mengubah jumlahnya sebesar $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ bagi $a \neq b$: jadi terdeteksi. Rahasianya adalah *keprimaan* $11$: modulo $10$, hasil kali seperti $5 \times 2$ lenyap padahal tak satu faktornya nol, sehingga galat berbobot $5$ sebesar $\pm 2$ (atau pertukaran yang bernasib sial) bisa lolos.

**9.** Jumlah berbobot kedua belas angkanya: $119$; angka pemeriksanya harus melengkapinya menjadi kelipatan $10$, jadi $1$ (kode lengkapnya $978\,2940199\,051$). EAN meleset pada pertukaran bertetangga dengan $2(a - b) \equiv 0 \pmod{10}$, yaitu $\abs{a - b} = 5$: menukar $2$ dengan $7$, misalnya, lolos tanpa terlihat — itulah harga [modulus](https://one-course.com/books/math/2/id/chapter/28-bilangan-kompleks#def-g12-complex-modulus) $10$ yang bersahabat itu.

**10.** Dengan melipatduakan tiap angka kedua dari kanan lalu melipatnya ($16 \to 7$, dan seterusnya), jumlahnya menjadi $80 \equiv 0
\pmod{10}$: jadi kartu ujinya sah.

**11.** Dengan [modulus](https://one-course.com/books/math/2/id/chapter/28-bilangan-kompleks#def-g12-complex-modulus) [prima](#def-g12-arith-prime) setiap bobotnya punya balikan, sehingga *semua* galat tunggal dan *semua* pertukaran bertetangga tertangkap — itulah kemewahan ISBN; sedangkan rancangan modulo $10$ mempertahankan angka yang ramah bagi manusia dan menerima satu titik buta.

**12.** $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1
\pmod{341}$, sehingga $2^{340} = \left(2^{10}\right)^{34} \equiv
1$. Padahal $341 = 11 \times 31$ tersusun: bilangan itu lolos uji Fermat pada bilangan pokok $2$ padahal bukan [prima](#def-g12-arith-prime). Pelajarannya: [kekongruenan](#def-g12-arith-congruence) Fermat itu perlu, tetapi tidak cukup — pengujian keprimaan menuntut perkakas yang lebih tajam (dan memperolehnya, di jilid universitas).

**13.** $3d \equiv 1 \pmod{20}$: jadi $d = 7$ (sebab $21 = 20 + 1$).

**14.** $c = 4^3 = 64 \equiv 31 \pmod{33}$.

**15.** $31 \equiv -2$: maka $(-2)^7 = -128$, dan $-128 + 4 \times 33 = 4$: jadi teks sandinya terbaca kembali menjadi $m = 4$. Kuncinya berputar.

**16.** Modulo $3$: jika $3 \nmid m$, maka $m^2 \equiv 1$ (Fermat), sehingga $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$; sedangkan jika $3 \mid m$, kedua ruasnya $\equiv 0$. Modulo $11$: $m^{10} \equiv 1$ atau $11 \mid m$, dan $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$. Jadi $3$ dan $11$ keduanya [membagi](#def-g12-arith-divides) $m^{21} - m$, dan karena [saling prima](#def-g12-arith-gcd) hasil kalinya $33$ juga [membaginya](#def-g12-arith-divides) (Gauss): $m^{21} \equiv m \pmod{33}$. Eksponen $ed = 21 = 1 + 20k$ dibangun justru agar kedua eksponen Fermat ($2$ dan $10$, yang [membagi](#def-g12-arith-divides) $20$) lenyap.

**17.** Mengalikan dua [bilangan prima](#def-g12-arith-prime) sepanjang $300$ angka memakan waktu sepersejuta detik; memperolehnya kembali dari hasil kalinya mengalahkan setiap algoritme yang diketahui dan seluruh komputer di dunia — kuncinya jalan satu arah. (Bilangan $n = 33$ kita adalah jalan itu dalam ukuran mainan, yang dapat ditempuh ke dua arah.)

**18.** Dengan menguji sisanya (atau membangun lewat Bézout): $n \equiv 8 \pmod{15}$, jadi cacahnya $8, 23, 38, 53, \dots$ Ketunggalannya modulo $15$: dua penyelesaian berselisih kelipatan $3$ sekaligus $5$, sehingga kelipatan $15$ (sebab $3$ dan $5$ [saling prima](#def-g12-arith-gcd), Gauss). Sang jenderal dengan $1000$ prajurit mengumumkan “$8$” lewat tiga kali baris cepat — muslihat pencacahan kepala dari zaman dahulu.

**19.** Dari $10 \equiv 1 \pmod 9$ diperoleh $10^k \equiv 1$, sehingga $\sum d_k 10^k \equiv \sum d_k$: jadi sebuah bilangan dan jumlah angkanya kongruen modulo $9$ (dan modulo $3$). Lalu $10 \equiv -1 \pmod{11}$ memberi $\sum d_k 10^k \equiv \sum (-1)^k d_k$: itulah kaidah berselang-selingnya. Dua kaidah masa kanak-kanak, masing-masing satu baris.

**20.** [Kekongruenan](#def-g12-arith-congruence) mengubah sisa menjadi sebuah aritmetika (Bagian I); Bézout mencetak balikan yang menyelesaikan [kekongruenan](#def-g12-arith-congruence) linear dan $d$ milik RSA (pertanyaan 4, 13); teorema kecil Fermat membuka dan menutup kuncinya (pertanyaan 15–16); perekatan [modulus](https://one-course.com/books/math/2/id/chapter/28-bilangan-kompleks#def-g12-complex-modulus) yang [saling prima](#def-g12-arith-gcd) mencacah prajurit dan menuntaskan buktinya (pertanyaan 16, 18). Vonis atas Hardy: teorema paling murni yang dikenalnya kini menjaga setiap pembelian — kemurnian, jika diberi waktu, adalah hal yang paling dapat diterapkan.