Kuliah · Kuliah · Bilangan

Teori Bilangan

Teori Bilangan mempelajari sifat bilangan bulat. Mata kuliah ini bergerak dari keterbagian dan algoritma Euclid, ke aritmetika kongruensi, lalu ke teorema Fermat dan Euler yang menjadi dasar kriptografi RSA, dan ditutup dengan persamaan Diophantine linear. Hampir semua perhitungan di sini bertumpu pada satu alat: identitas Bézout gcd⁡(a,b)=ax+by\gcd(a, b) = ax + by.

Daftar isi
  1. Konsep
  2. Rumus
  3. Contoh soal
  4. Kesalahan umum
  5. Coba sendiri
  6. Kuis 5 soal
  7. Tanya jawab
  8. Topik terkait
  9. Untuk guru

Konsep Teori Bilangan

Bab 1 — Keterbagian

aa membagi bb (ditulis a∣ba \mid b) jika ada bilangan bulat kk dengan b=akb = ak. Sifat dasar: jika a∣ba \mid b dan a∣ca \mid c, maka a∣(bx+cy)a \mid (bx + cy) untuk semua bulat x,yx, y.

Algoritma pembagian: untuk bulat aa dan b>0b > 0 ada tepat satu pasangan q,rq, r dengan a=bq+ra = bq + r dan 0≤r<b0 \le r < b. Buktinya memakai prinsip urutan baik pada himpunan {a−bk≥0}\{a - bk \ge 0\}.

Teorema dasar aritmetika: setiap bilangan bulat n>1n > 1 dapat ditulis sebagai hasil kali bilangan prima secara tunggal (tidak memandang urutan). Jika n=p1e1⋯pkekn = p_1^{e_1} \cdots p_k^{e_k}, banyak pembagi positifnya (e1+1)⋯(ek+1)(e_1 + 1) \cdots (e_k + 1). Euclid membuktikan bilangan prima tak berhingga: jika p1,…,pkp_1, \dots, p_k semua prima, maka p1⋯pk+1p_1 \cdots p_k + 1 tidak habis dibagi satu pun di antaranya.

Bab 2 — FPB dan algoritma Euclid

Karena gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r) bila a=bq+ra = bq + r, FPB dapat dihitung dengan pembagian berulang sampai sisanya nol; sisa tak nol terakhir adalah FPB. Algoritma ini sangat cepat: banyak langkahnya sebanding dengan banyak digit bilangan.

Identitas Bézout: ada bulat x,yx, y dengan ax+by=gcd⁡(a,b)ax + by = \gcd(a, b). Nilai x,yx, y diperoleh dengan algoritma Euclid yang diperluas, yaitu menyusun mundur persamaan-persamaan pembagian. Akibatnya: aa dan bb relatif prima jika dan hanya jika ax+by=1ax + by = 1 punya solusi, dan lemma Euclid: jika pp prima dan p∣abp \mid ab, maka p∣ap \mid a atau p∣bp \mid b. Hubungan dengan KPK: gcd⁡(a,b)×KPK⁡(a,b)=ab\gcd(a, b) \times \operatorname{KPK}(a, b) = ab.

Bab 3 — Kongruensi

a≡b(modn)a \equiv b \pmod{n} berarti n∣(a−b)n \mid (a - b). Kongruensi adalah relasi ekuivalensi yang menghormati penjumlahan dan perkalian, sehingga kita boleh "menghitung dengan sisa".

Kongruensi linear ax≡b(modn)ax \equiv b \pmod{n} punya solusi jika dan hanya jika d=gcd⁡(a,n)d = \gcd(a, n) membagi bb, dan ada tepat dd solusi modulo nn. Jika gcd⁡(a,n)=1\gcd(a, n) = 1, aa memiliki invers modulo nn yang dicari dengan Bézout.

Teorema sisa Tiongkok: jika n1,…,nkn_1, \dots, n_k relatif prima sepasang-sepasang, sistem x≡ai(modni)x \equiv a_i \pmod{n_i} punya solusi tunggal modulo N=n1⋯nkN = n_1 \cdots n_k, yaitu x=∑aiNiyix = \sum a_i N_i y_i dengan Ni=NniN_i = \frac{N}{n_i} dan yi≡Ni−1(modni)y_i \equiv N_i^{-1} \pmod{n_i}.

Bab 4 — Teorema Fermat dan Euler

Teorema kecil Fermat: jika pp prima dan p∤ap \nmid a, maka ap−1≡1(modp)a^{p - 1} \equiv 1 \pmod{p}. Bukti singkat: perkalian dengan aa hanya mengacak urutan 1,2,…,p−11, 2, \dots, p - 1 modulo pp, sehingga ap−1(p−1)!≡(p−1)!a^{p - 1}(p - 1)! \equiv (p - 1)!, lalu coret (p−1)!(p - 1)!.

Fungsi phi Euler φ(n)\varphi(n) menghitung bilangan di 1,…,n1, \dots, n yang relatif prima dengan nn, dengan rumus φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right). Teorema Euler: jika gcd⁡(a,n)=1\gcd(a, n) = 1, maka aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n}. Teorema ini memangkas perhitungan pangkat besar: kurangi eksponen modulo φ(n)\varphi(n). Teorema Wilson melengkapinya: pp prima jika dan hanya jika (p−1)!≡−1(modp)(p - 1)! \equiv -1 \pmod{p}.

Bab 5 — Persamaan Diophantine linear

Persamaan ax+by=cax + by = c dengan x,yx, y bulat punya solusi jika dan hanya jika d=gcd⁡(a,b)d = \gcd(a, b) membagi cc. Jika (x0,y0)(x_0, y_0) satu solusi, semua solusinya

x=x0+bdt,y=y0−adt,t∈Z.x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t, \qquad t \in \mathbb{Z}.

Dalam soal cerita biasanya ada syarat x,y≥0x, y \ge 0 atau ≥1\ge 1; syarat itu membatasi tt pada suatu interval sehingga banyak solusinya dapat dihitung. Persamaan Diophantine nonlinear (misalnya tripel Pythagoras x2+y2=z2x^{2} + y^{2} = z^{2}) dibahas sebagai pengayaan.

Rumus

Algoritma pembagian
a=bq+r,0≤r<ba = bq + r, \quad 0 \le r < b
Identitas Bézout
gcd⁡(a,b)=ax+by\gcd(a, b) = ax + by
Teorema Euler
aφ(n)≡1(modn),φ(n)=n∏p∣n(1−1p)a^{\varphi(n)} \equiv 1 \pmod{n}, \quad \varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)
Solusi umum Diophantine linear
x=x0+bdt,y=y0−adtx = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t

Contoh soal teori bilangan dan pembahasan

Contoh 1 · Mudah

Algoritma pembagian

Tentukan hasil bagi qq dan sisa rr ketika 2026 dibagi 17.

Lihat langkah penyelesaian
  1. 17×100=1.70017 \times 100 = 1.700, sisa 326326; 17×19=32317 \times 19 = 323, sisa 3.
  2. Jadi 2026=17×119+32026 = 17 \times 119 + 3 dengan 0≤3<170 \le 3 < 17.

q=119q = 119 dan r=3r = 3.

Contoh 2 · Sedang

FPB dengan algoritma Euclid dan Bézout

Tentukan gcd⁡(252,198)\gcd(252, 198) dan bilangan bulat x,yx, y dengan 252x+198y=gcd⁡(252,198)252x + 198y = \gcd(252, 198).

Lihat langkah penyelesaian
  1. 252=1×198+54252 = 1 \times 198 + 54, 198=3×54+36198 = 3 \times 54 + 36, 54=1×36+1854 = 1 \times 36 + 18, 36=2×18+036 = 2 \times 18 + 0. Sisa tak nol terakhir 18.
  2. Mundur: 18=54−36=54−(198−3×54)=4×54−19818 = 54 - 36 = 54 - (198 - 3 \times 54) = 4 \times 54 - 198.
  3. Substitusi 54=252−19854 = 252 - 198: 18=4×252−5×19818 = 4 \times 252 - 5 \times 198.

gcd⁡(252,198)=18\gcd(252, 198) = 18 dengan x=4x = 4 dan y=−5y = -5.

Contoh 3 · Sedang

Invers modulo dengan Euclid yang diperluas

Tentukan invers 7 modulo 26, yaitu xx dengan 7x≡1(mod26)7x \equiv 1 \pmod{26} dan 0≤x<260 \le x < 26.

Lihat langkah penyelesaian
  1. gcd⁡(7,26)=1\gcd(7, 26) = 1, jadi invers ada: 26=3×7+526 = 3 \times 7 + 5, 7=1×5+27 = 1 \times 5 + 2, 5=2×2+15 = 2 \times 2 + 1.
  2. Mundur: 1=5−2×2=5−2(7−5)=3×5−2×7=3(26−3×7)−2×7=3×26−11×71 = 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.
  3. Jadi 7−1≡−11≡15(mod26)7^{-1} \equiv -11 \equiv 15 \pmod{26}. Cek: 7×15=105=4×26+17 \times 15 = 105 = 4 \times 26 + 1.

Invers 7 modulo 26 adalah 15.

Contoh 4 · Sedang

Pangkat besar dengan teorema Fermat

Tentukan sisa pembagian 31003^{100} oleh 7.

Lihat langkah penyelesaian
  1. 7 prima dan 7∤37 \nmid 3, jadi 36≡1(mod7)3^{6} \equiv 1 \pmod{7}.
  2. 100=6×16+4100 = 6 \times 16 + 4, sehingga 3100=(36)16×34≡34(mod7)3^{100} = (3^{6})^{16} \times 3^{4} \equiv 3^{4} \pmod{7}.
  3. 34=81=11×7+43^{4} = 81 = 11 \times 7 + 4.

Sisanya 4.

Contoh 5 · Penalaran

Persamaan Diophantine dalam soal belanja

Bu Sari membeli kue lapis seharga Rp4.000 per potong dan bolu seharga Rp7.000 per potong dengan total tepat Rp111.000. Masing-masing dibeli paling sedikit satu potong. Ada berapa kemungkinan banyak kue lapis dan bolu yang dibeli?

Lihat langkah penyelesaian
  1. Model: 4x+7y=1114x + 7y = 111 dengan x,y≥1x, y \ge 1. Karena gcd⁡(4,7)=1\gcd(4, 7) = 1 membagi 111, solusi bulat ada.
  2. Satu solusi: y=1y = 1 memberi 4x=1044x = 104, x=26x = 26. Solusi umum: x=26−7tx = 26 - 7t, y=1+4ty = 1 + 4t.
  3. Syarat y≥1y \ge 1 memberi t≥0t \ge 0; syarat x≥1x \ge 1 memberi 7t≤257t \le 25, yaitu t≤3t \le 3.
  4. Jadi t=0,1,2,3t = 0, 1, 2, 3, yaitu (26,1),(19,5),(12,9),(5,13)(26, 1), (19, 5), (12, 9), (5, 13).

Ada 4 kemungkinan.

Kesalahan yang sering terjadi

Membagi kedua ruas kongruensi dengan sembarang bilangan, misalnya dari 6x≡6(mod9)6x \equiv 6 \pmod{9} menyimpulkan x≡1(mod9)x \equiv 1 \pmod{9}.
Pembagian dengan aa hanya sah jika gcd⁡(a,n)=1\gcd(a, n) = 1. Di sini gcd⁡(6,9)=3\gcd(6, 9) = 3, sehingga x≡1(mod3)x \equiv 1 \pmod{3}, yaitu x≡1,4,7(mod9)x \equiv 1, 4, 7 \pmod{9}.
Memakai teorema Fermat untuk modulus yang bukan prima, misalnya menganggap a9≡1(mod10)a^{9} \equiv 1 \pmod{10}.
Untuk modulus komposit gunakan teorema Euler dengan φ(n)\varphi(n). Untuk n=10n = 10, φ(10)=4\varphi(10) = 4, sehingga a4≡1(mod10)a^{4} \equiv 1 \pmod{10} bila gcd⁡(a,10)=1\gcd(a, 10) = 1.
Berhenti pada satu solusi persamaan Diophantine dan melupakan solusi umum.
Persamaan ax+by=cax + by = c yang punya solusi selalu punya tak berhingga solusi bulat. Tulis solusi umum dengan parameter tt, lalu terapkan syarat soal.

Coba sendiri

Tulis jawabanmu, tekan Periksa. Jika belum tepat, buka petunjuk satu per satu.

Soal 1Aplikasi
Dengan algoritma Euclid, tentukan gcd⁡(391,299)\gcd(391, 299).
Soal 2Aplikasi
Tentukan angka satuan dari 72227^{222}, yaitu sisa 72227^{222} dibagi 10.
Soal 3Penalaran
Tentukan invers 5 modulo 17 (bilangan 0≤x<170 \le x < 17 dengan 5x≡1(mod17)5x \equiv 1 \pmod{17}).

Kuis 5 soal

Kerjakan semua soal, lalu periksa sekaligus.

Soal 1Aplikasi
Nilai φ(36)\varphi(36) adalah …
Soal 2Pemahaman
Pernyataan: "Jika a≡b(modn)a \equiv b \pmod{n} dan c≡d(modn)c \equiv d \pmod{n}, maka ac≡bd(modn)ac \equiv bd \pmod{n}." Benar atau salah?
Soal 3Aplikasi
Sisa pembagian 2502^{50} oleh 13 adalah …
Soal 4Penalaran
Pilih semua persamaan yang memiliki solusi bilangan bulat x,yx, y.
Pilih semua jawaban yang benar.
Soal 5Aplikasi
Berapa banyak pembagi positif dari 360?

Latihan tanpa batas

Soal kembar dengan angka baru, petunjuk bertingkat, dan catatan penguasaanmu.

Mulai latihan

Tanya jawab

Apa hubungan Teori Bilangan dengan keamanan internet?

Kriptografi RSA memilih dua prima besar p,qp, q, memakai n=pqn = pq dan φ(n)=(p−1)(q−1)\varphi(n) = (p - 1)(q - 1), lalu mencari kunci privat sebagai invers modulo φ(n)\varphi(n). Keamanannya bertumpu pada sulitnya memfaktorkan nn.

Apakah perlu menghafal tabel prima?

Tidak. Yang penting adalah menguasai algoritma Euclid yang diperluas dan cara mereduksi eksponen dengan teorema Fermat atau Euler. Untuk menguji keprimaan nn, cukup coba pembagi prima sampai n\sqrt{n}.

Topik terkait

Ringkasan untuk guru

Tujuan pembelajaran

  • Mahasiswa membuktikan sifat keterbagian dan memakai teorema dasar aritmetika.
  • Mahasiswa menghitung FPB, koefisien Bézout, dan invers modulo dengan algoritma Euclid yang diperluas.
  • Mahasiswa menyelesaikan kongruensi linear dan sistem dengan teorema sisa Tiongkok.
  • Mahasiswa menerapkan teorema Fermat dan Euler serta menyelesaikan persamaan Diophantine linear berkendala.

Ide aktivitas kelas

  • Simulasi RSA mini: kelompok memilih prima kecil, membangkitkan kunci, lalu saling mengirim pesan angka yang dienkripsi.
  • Pemrograman algoritma Euclid: mahasiswa menulis fungsi FPB dan Bézout, lalu membandingkan banyak langkah dengan banyak digit masukan.
  • Soal cerita Diophantine: mahasiswa membuat soal belanja dengan harga lokal, lalu teman menghitung banyak kemungkinan solusinya.

Acuan: Silabus umum mata kuliah Teori Bilangan program sarjana matematika (disusun tim redaksi), elemen Bilangan.

Bagikan latihan ke kelas dengan kode tugas