Matematika Universitas — Tahun 1 · Bachelor Year 1

6Aritmetika Bilangan Bulat

Aritmetika — yaitu telaah keterbagian di $\Z$ — sudah dimulai pada jilid sekolah menengah. Bab ini membangunnya kembali sepenuhnya dari pembagian Euclid, dengan bukti lengkap: faktor persekutuan terbesar dan algoritma Euclid, kesamaan Bézout dan lema Gauss, pemfaktoran prima, serta kalkulus kekongruenan sampai teorema kecil Fermat. Di luar pesonanya sendiri, bahan ini adalah model yang ditiru Bab 8 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 $A = \{a - bk : k \in \Z\} \cap \N$ adalah himpunan 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$ ; keberadaan FPB)

Setiap subgrup $(\Z, +)$ berbentuk $n\Z = \{nk : k \in \Z\}$ untuk suatu $n \in \N$ yang tunggal.
Untuk $a, b \in \Z$ yang tak keduanya nol, himpunan $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 $a$ dan $b$ , dan setiap pembagi persekutuan $a$ dan $b$ membagi $d$ .

Bukti. (1) Misalkan $H \subseteq \Z$ sebuah subgrup (tak kosong dan tertutup terhadap pengurangan; definisi formalnya ada pada Bab 7, 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); 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 $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 keduanya. Dan jika $c$ membagi $a$ dan $b$ , maka $c$ membagi 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 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 $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$ .

(Lema Gauss) Jika $a \mid bc$ dan $\gcd(a, b) = 1$ , maka $a \mid c$ .
Jika $a \mid c$ , $b \mid c$ dan $\gcd(a,b) = 1$ , maka $ab \mid c$ .
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, $\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 $4$ , jadi penyelesaiannya ada (seandainya FPB-nya tidak membagi 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, 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 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), 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 $\leq \sqrt n$ . Jadi untuk menguji apakah $n$ prima cukup dicoba bilangan prima 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, 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.

Teorema 6.14 (Euclid)

Bilangan prima ada tak hingga banyaknya.

Bukti. Setiap bilangan bulat $n \geq 2$ mempunyai pembagi prima: pembagi terkecilnya yang $\geq 2$ bersifat prima (karena pemfaktoran sejatinya akan menghasilkan pembagi $n$ yang lebih kecil). Sekarang andaikan $p_1, \dots, p_k$ semua bilangan primanya, lalu tulis $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Suatu prima $p_i$ membagi $N$ ; tetapi $p_i$ juga membagi $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, 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): $n = 2$ prima; untuk $n > 2$ , entah $n$ prima, 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 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 melebihi $1$ ). Untuk $r \geq 1$ : prima $p_1$ membagi $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 suatu $q_j$ . Tetapi $q_j$ prima 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 yang sama. ∎

Proposisi 6.16 (Valuasi)

Untuk $p$ prima 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 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 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 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). 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 dalam wujud mini: pemeriksaan kekongruenan membantah, tetapi tidak mengesahkan.

Proposisi 6.20 (Keterbalikan mod $n$ )

$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 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). Ketunggalannya: jika $ab \equiv ab' \equiv 1$ , maka $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Contoh 6.21 (Membalikkan $7$ modulo $26$ )

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 $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, 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 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. 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 $\binom pk = \frac{p!}{k!(p-k)!}$ habis dibagi $p$ : memang $k!\,(p-k)!\, \binom pk = p!$ dan $p$ membagi $p!$ tetapi saling prima 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). ∎

Contoh 6.24 (Konvers Fermat gugur: $341$ )

Teorema kecil Fermat memberikan uji kekompositan yang murah: jika $a^{n-1} \not\equiv 1 \pmod n$ untuk suatu $a$ yang saling prima dengan $n$ , maka $n$ tidak prima. 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 besar pada Catatan 6.27. Moralnya: sebuah implikasi dan konversnya hidup secara terpisah (Catatan 1.10), 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)

Membagi sebuah kekongruenan. 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 modulusnya juga: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
Menyalahgunakan lema Euclid. Bahwa $a \mid bc$ mengakibatkan $a \mid b$ atau $a \mid c$ hanya berlaku untuk $a$ yang prima (atau yang saling prima dengan salah satu faktornya): $6 \mid 4 \times 9$ padahal $6$ tak membagi satu pun faktornya.
Saling prima itu relasi, bukan sifat. “ $8$ dan $9$ saling prima” itu benar meskipun tak satu pun prima; “saling prima dua-dua” lebih kuat daripada “saling prima secara menyeluruh” ( $\gcd(6, 10, 15) = 1$ tetapi tak ada pasangan yang saling prima).
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.

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, yang di sana “derajat” memainkan peran nilai mutlak; membandingkan kedua bab itu berdampingan adalah cara terbaik memahami keduanya. Kalkulus kekongruenannya menjelma menjadi ring $\Z/n\Z$ pada Bab 7, yang unsur terbalikkannya (Proposisi 6.20) 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. 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 besar yang dipakai di sana.

Catatan 6.28 (Selingan: $\Z$ 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 (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, 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, yang di sana pertanyaan keterbalikan (yaitu Proposisi 6.20 bab ini) menjadi pernyataan 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. — 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, beserta sepasang bilangan Bézout untuknya.

Solusi

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

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

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

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 dan $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Solusi

Solusi Latihan 6.5.

Untuk setiap prima $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 adalah sama (Proposisi 6.16), 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

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); 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 $p$ , dengan memakai valuasi: bandingkan $v_p$ kedua ruas $p q^2 = r^2$ .

Solusi

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, sepasang kekongruenan $x \equiv a \ (m)$ , $x \equiv b\ (n)$ selalu mempunyai penyelesaian yang tunggal modulo $mn$ .

Solusi

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 $x - x'$ , sehingga $mn \mid x - x'$ (Teorema 6.8 (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).

Solusi

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), $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.

Solusi

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 $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 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. 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, maka $(n-1)! \not\equiv -1 \pmod n$ .

Solusi

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

Buktikan bahwa $F_0 F_1 \cdots F_{n-1} = F_n - 2$ untuk $n \geq 1$ (dengan induksi).
Simpulkan bahwa bilangan Fermat saling prima dua-dua.
Simpulkan bukti kedua, yang tak bergantung pada Teorema 6.14, bahwa bilangan prima ada tak hingga banyaknya.

Solusi

Solusi Latihan 6.12.

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 .$
Misalkan $m < n$ dan $d = \gcd(F_m, F_n)$ . Menurut (1), $F_m$ membagi $F_n - 2$ , jadi $d$ membagi $F_n$ maupun $F_n - 2$ , sehingga ia membagi $2$ . Tetapi setiap bilangan Fermat ganjil, jadi $d = 1$ .
Setiap $F_n \geq 3$ mempunyai pembagi prima $p_n$ (menurut langkah pertama Teorema 6.14). Jika $m \neq n$ , maka $p_m \neq p_n$ , karena prima persekutuannya akan membagi $\gcd(F_m, F_n) = 1$ . Jadi pemetaan $n \mapsto p_n$ bersifat injektif dari $\N$ ke dalam bilangan prima: sehingga bilangan prima 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 $p$ yang membagi $n!$ , atau membagi koefisien binomial? 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. Di sepanjang soal ini, $p$ sebuah prima, $\floor{x}$ bagian bulatnya, dan $s_p(n)$ menyatakan jumlah angka $n$ yang ditulis dalam basis $p$ .

Bagian I — Lantai, valuasi, dan rumus Legendre.

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$ .
Buktikan bahwa untuk $x \in \R$ dan $n \in \N^*$ berlaku $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
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)$ .
Tunjukkan bahwa banyaknya kelipatan $m$ di $\intint1n$ adalah $\lfloor n/m \rfloor$ .
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.

Hitung $v_5(1000!)$ dan $v_2(1000!)$ , lalu simpulkan: berapa banyak nol yang mengakhiri $1000!$ ?
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} .$
Dua akibat untuk $p = 2$ : tunjukkan bahwa $2^n$ tak pernah membagi $n!$ , dan bahwa $2^{n-1}$ membagi $n!$ tepat ketika $n$ merupakan pangkat $2$ .
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.
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.

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$ .
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$ .)
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, yang dipulihkan.)
Buktikan bahwa $v_2\binom{2n}n = s_2(n)$ . Simpulkan bahwa koefisien binomial pusatnya selalu genap, dan bahwa $\binom{2n}n \equiv 2 \pmod 4$ tepat ketika $n$ merupakan pangkat $2$ .
Tunjukkan, dengan memakai kesamaan Vandermonde (Latihan 2.7) dan pertanyaan 13, bahwa $\binom{2p}p \equiv 2 \pmod p$ untuk setiap prima $p$ .
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.

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$ .
Simpulkan bahwa baris $n$ segitiga Pascal memuat tepat $2^{s_2(n)}$ entri ganjil; lalu periksa pada baris $4$ dan $5$ .
Simpulkan bahwa semua entri bagian dalamnya $\binom nk$ ( $0 < k < n$ ) genap jika dan hanya jika $n$ merupakan pangkat $2$ .
Buktikan bahwa setiap pangkat prima yang membagi $\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?)
Simpulkan bahwa $\binom{2n}n$ membagi $\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.

Bagian V — Sintesis.

Carilah $n$ terkecil yang membuat $n!$ berakhir dengan sekurang-kurangnya $2026$ nol. (Taksir $Z(n) \approx n/4$ , lalu sesuaikan memakai rumus eksaknya.)
Satu pemeriksaan silang terakhir: tunjukkan bahwa $7$ tidak membagi $\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.
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? Satu kalimat untuk masing-masing.
Sintesis, dalam satu paragraf pendek: rumus Legendre mengubah pertanyaan keterbagian 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 (pernyataan lengkapnya, yaitu teorema bilangan prima, jauh di luar jilid ini; adapun analog polinomial bagi kotak perkakas bab ini adalah Bab 8).

Solusi

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 yang dipakai pada Teorema 6.23.

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 $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, $\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 di bawah $2n$ hanya sedikit, KPK-nya tak akan sebesar itu: jadi pertumbuhan eksponensial KPK-nya adalah jejak kuantitatif dari limpahnya bilangan prima.

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 (Proposisi 6.16). (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.

25. Legendre mengubah “pangkat $p$ yang mana yang membagi $n!$ ” menjadi aritmetika angka basis $p$ ; Kummer memampatkan jawabannya untuk koefisien binomial menjadi simpanan pada satu penjumlahan — keterbagian, 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, yang buktinya jauh di luar jilid ini. Seluruh kotak perkakasnya — pembagian, FPB, valuasi — diputar ulang untuk polinomial pada Bab 8, yang di sana analog ekspansi angkanya adalah ekspansi dalam pangkat $(X - a)$ .

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium