Matematika Sekolah Menengah Atas · Grades 10–12

29Aritmetika

Aritmetika mengkaji bilangan bulat: keterbagian, bilangan prima, 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 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); 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 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 $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 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 $(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 $n$ )

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 yang tidak keduanya nol. Pembagi persekutuan terbesar $\gcd(a, b)$ adalah bilangan bulat terbesar yang membagi $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 $r = a - bq$ (Proposisi 29.2), 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 bilangan bulat 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 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 jika dan hanya jika $au + bv = 1$ untuk suatu bilangan bulat $u, v$ .

Bukti. Jalankan algoritme Euklides 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: $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 $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 $p \geq 2$ disebut prima jika pembagi positifnya hanyalah $1$ dan $p$ .

Proposisi 29.14

Setiap bilangan bulat $n \geq 2$ punya pembagi prima; jika $n$ bukan prima, ia punya pembagi prima $\leq \sqrt n$ . Jika suatu prima $p$ membagi hasil kali $ab$ , maka $p \mid a$ atau $p \mid b$ (lema Euklides).

Bukti. Pembagi terkecil $d \geq 2$ dari $n$ adalah prima (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.

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

Teorema 29.16 (Teorema dasar aritmetika)

Setiap bilangan bulat $n \geq 2$ adalah hasil kali bilangan prima, 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 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, pengulangan diperbolehkan). Menurut lema Euklides, $p_1$ membagi suatu $q_j$ , dan karena prima, $p_1 = q_j$ ; coretlah lalu ulangi. Kedua pemfaktorannya cocok suku demi suku. ∎

Teorema 29.17 (Teorema kecil Fermat)

Misalkan $p$ prima 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), $a^p \equiv a \pmod p$ .

Bukti. Tinjaulah $p - 1$ bilangan bulat $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:

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

Karena $p$ tidak membagi 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 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 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 $2026$ oleh $17$ , lalu $-2026$ oleh $17$ .

Solusi

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

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, hitunglah $\gcd(1071, 462)$ , lalu carilah bilangan bulat $u, v$ dengan $1071u + 462v = \gcd(1071, 462)$ .

Solusi

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 yang $\equiv 3 \pmod 4$ tak pernah menjadi jumlah dua kuadrat.

Solusi

Solusi Latihan 29.4.

Setiap bilangan bulat $\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

Solusi Latihan 29.5.

Keterbagian oleh $2$ : di antara $n$ dan $n + 1$ , salah satunya genap. Keterbagian 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 hasil kalinya. Karena $\gcd(2,3) = 1$ , Akibat 29.12 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, adalah bilangan bulat.)

Latihan 29.6 ★★

Selesaikan di $\Z$ kekongruenan $5x \equiv 3 \pmod{11}$ . (Petunjuk: carilah balikan $5$ modulo $11$ .)

Solusi

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 dengan $9$ :

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

Penyelesaiannya adalah bilangan bulat $x = 5 + 11k$ , $k \in \Z$ . (Periksalah: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Latihan 29.7 ★★

Selesaikan di $\Z \times \Z$ persamaan Diofantin

17x - 40y = 1,

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

Solusi

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, dengan memakai ketunggalan pemfaktoran primanya (bandingkan eksponen $2$ pada kedua ruas $a^2 = 2b^2$ ).

Solusi

Solusi Latihan 29.8.

Andaikan $\sqrt2 = \frac ab$ dengan $a, b \in \N^*$ ; maka $a^2 = 2b^2$ . Pada pemfaktoran prima 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 yang sama dengan eksponen $2$ yang berbeda bertentangan dengan ketunggalan pada Teorema 29.16. Jadi pecahan semacam itu tak ada: $\sqrt2 \notin \Q$ .

Latihan 29.9 ★★★

Misalkan $p$ suatu bilangan prima.

Tunjukkan bahwa untuk $1 \leq k \leq p - 1$ , $p$ membagi $\dbinom{p}{k}$ . (Petunjuk: pakailah $k\binom pk = p\binom{p-1}{k-1}$ , Latihan 27.7, dan lema Gauss.)
Simpulkan, lewat induksi pada $a \geq 0$ , suatu bukti lain bagi teorema kecil Fermat dalam bentuk $a^p \equiv a \pmod p$ .

Solusi

Solusi Latihan 29.9.

1. Dari $k\binom pk = p \binom{p-1}{k-1}$ , jelas $p$ membagi $k\binom pk$ . Untuk $1 \leq k \leq p-1$ , $p \nmid k$ dan $p$ yang prima 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 $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

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 (Proposisi 29.5), balikan Bézout (Teorema 29.10) dan teorema kecil Fermat (Latihan 29.9). Soal ini memeriksa kodenya, membobol kunci versi mainannya, lalu belajar mengapa kunci yang sungguhan bertahan.

Bagian I — Kelancaran kekongruenan.

Hitunglah $2026 \bmod 7$ ; lalu angka terakhir $7^{100}$ (carilah kitaran pangkat $7$ modulo $10$ ).
Pemangkatan cepat (Metode 29.6): hitunglah $5^{117} \bmod 13$ (mulailah dari $5^2 \equiv -1$ ).
Selesaikan $3x \equiv 5 \pmod 7$ .
Jalankan algoritme Euklides pada $(97, 35)$ , substitusikan mundur untuk mencari bilangan bulat $u, v$ dengan $97u + 35v = 1$ , lalu simpulkan balikan $35$ modulo $97$ .
Nyatakan dengan tepat kapan $a$ punya balikan modulo $n$ , dan teorema mana yang menyerahkan balikannya.

Bagian II — Angka pemeriksa.

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$ .
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)?
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 $10$ ?
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}$ ?)
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$ .
Dalam satu kalimat: apa yang dibeli modulus prima bagi ISBN, yang tak dapat dimiliki EAN dan Luhn karena terantai pada $10$ ?

Bagian III — Kunci Fermat.

Sebuah jebakan sebelum hartanya: hitunglah $2^{10} \bmod 341$ , simpulkan $2^{340} \bmod 341$ — lalu faktorkanlah $341$ . Apa yang dikatakan contoh ini (sebuah prima semu Fermat) tentang pemakaian teorema kecil Fermat sebagai uji keprimaan?
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).
Sandikanlah pesan $m = 4$ : hitunglah $c = m^3 \bmod 33$ .
Bacalah sandinya: hitunglah $c^d \bmod 33$ (pakailah $c \equiv -2 \pmod{33}$ ) lalu perolehlah kembali pesannya.
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 merekatkan kedua kekongruenannya). Di manakah bentuk khusus $21 = ed$ , yaitu $1 + 20k$ , masuk?
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.)

Bagian IV — Yang klasik.

Pencacahan prajurit Tiongkok kuno (bandingkan Latihan 29.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$ .
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.)
Penutup — Hardy melawan kode batang: rangkumlah perkakas bab ini (aritmetika kekongruenan, balikan Bézout, teorema kecil Fermat, perekatan modulus yang saling prima) dan di mana masing-masingnya mengunci pada tempatnya dalam soal ini; lalu berikan vonis zaman kini atas kata “tak ternoda” itu.

Solusi

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 $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 dan tidak membagi satu pun faktornya, ia tak dapat membagi hasil kalinya (Teorema 29.11 / Proposisi 29.14), 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 $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 prima 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. Pelajarannya: kekongruenan 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 $m^{21} - m$ , dan karena saling prima hasil kalinya $33$ juga membaginya (Gauss): $m^{21} \equiv m \pmod{33}$ . Eksponen $ed = 21 = 1 + 20k$ dibangun justru agar kedua eksponen Fermat ( $2$ dan $10$ , yang membagi $20$ ) lenyap.

17. Mengalikan dua bilangan prima 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, 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 mengubah sisa menjadi sebuah aritmetika (Bagian I); Bézout mencetak balikan yang menyelesaikan kekongruenan linear dan $d$ milik RSA (pertanyaan 4, 13); teorema kecil Fermat membuka dan menutup kuncinya (pertanyaan 15–16); perekatan modulus yang saling prima 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.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium