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 .
Daftar isi
Konsep Teori Bilangan
Bab 1 — Keterbagian
membagi (ditulis ) jika ada bilangan bulat dengan . Sifat dasar: jika dan , maka untuk semua bulat .
Algoritma pembagian: untuk bulat dan ada tepat satu pasangan dengan dan . Buktinya memakai prinsip urutan baik pada himpunan .
Teorema dasar aritmetika: setiap bilangan bulat dapat ditulis sebagai hasil kali bilangan prima secara tunggal (tidak memandang urutan). Jika , banyak pembagi positifnya . Euclid membuktikan bilangan prima tak berhingga: jika semua prima, maka tidak habis dibagi satu pun di antaranya.
Bab 2 — FPB dan algoritma Euclid
Karena bila , 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 dengan . Nilai diperoleh dengan algoritma Euclid yang diperluas, yaitu menyusun mundur persamaan-persamaan pembagian. Akibatnya: dan relatif prima jika dan hanya jika punya solusi, dan lemma Euclid: jika prima dan , maka atau . Hubungan dengan KPK: .
Bab 3 — Kongruensi
berarti . Kongruensi adalah relasi ekuivalensi yang menghormati penjumlahan dan perkalian, sehingga kita boleh "menghitung dengan sisa".
Kongruensi linear punya solusi jika dan hanya jika membagi , dan ada tepat solusi modulo . Jika , memiliki invers modulo yang dicari dengan Bézout.
Teorema sisa Tiongkok: jika relatif prima sepasang-sepasang, sistem punya solusi tunggal modulo , yaitu dengan dan .
Bab 4 — Teorema Fermat dan Euler
Teorema kecil Fermat: jika prima dan , maka . Bukti singkat: perkalian dengan hanya mengacak urutan modulo , sehingga , lalu coret .
Fungsi phi Euler menghitung bilangan di yang relatif prima dengan , dengan rumus . Teorema Euler: jika , maka . Teorema ini memangkas perhitungan pangkat besar: kurangi eksponen modulo . Teorema Wilson melengkapinya: prima jika dan hanya jika .
Bab 5 — Persamaan Diophantine linear
Persamaan dengan bulat punya solusi jika dan hanya jika membagi . Jika satu solusi, semua solusinya
Dalam soal cerita biasanya ada syarat atau ; syarat itu membatasi pada suatu interval sehingga banyak solusinya dapat dihitung. Persamaan Diophantine nonlinear (misalnya tripel Pythagoras ) dibahas sebagai pengayaan.
Rumus
Contoh soal teori bilangan dan pembahasan
Algoritma pembagian
Tentukan hasil bagi dan sisa ketika 2026 dibagi 17.
Lihat langkah penyelesaian
- , sisa ; , sisa 3.
- Jadi dengan .
dan .
FPB dengan algoritma Euclid dan Bézout
Tentukan dan bilangan bulat dengan .
Lihat langkah penyelesaian
- , , , . Sisa tak nol terakhir 18.
- Mundur: .
- Substitusi : .
dengan dan .
Invers modulo dengan Euclid yang diperluas
Tentukan invers 7 modulo 26, yaitu dengan dan .
Lihat langkah penyelesaian
- , jadi invers ada: , , .
- Mundur: .
- Jadi . Cek: .
Invers 7 modulo 26 adalah 15.
Pangkat besar dengan teorema Fermat
Tentukan sisa pembagian oleh 7.
Lihat langkah penyelesaian
- 7 prima dan , jadi .
- , sehingga .
- .
Sisanya 4.
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
- Model: dengan . Karena membagi 111, solusi bulat ada.
- Satu solusi: memberi , . Solusi umum: , .
- Syarat memberi ; syarat memberi , yaitu .
- Jadi , yaitu .
Ada 4 kemungkinan.
Kesalahan yang sering terjadi
Coba sendiri
Tulis jawabanmu, tekan Periksa. Jika belum tepat, buka petunjuk satu per satu.
Pembahasan
, jadi FPB-nya 23. Bentuk Bézout: .
Pembahasan
. Angka satuannya 9.
Pembahasan
, jadi . Cek: .
Kuis 5 soal
Kerjakan semua soal, lalu periksa sekaligus.
Pembahasan
.
Pembahasan
Benar. , yang habis dibagi .
Pembahasan
.
Pembahasan
membagi 21 tetapi tidak 20; membagi 7; tidak membagi 7; membagi 1.
Pembahasan
pembagi.
Latihan tanpa batas
Soal kembar dengan angka baru, petunjuk bertingkat, dan catatan penguasaanmu.
Tanya jawab
Apa hubungan Teori Bilangan dengan keamanan internet?
Kriptografi RSA memilih dua prima besar , memakai dan , lalu mencari kunci privat sebagai invers modulo . Keamanannya bertumpu pada sulitnya memfaktorkan .
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 , cukup coba pembagi prima sampai .
Topik terkait
Pelajari dulu (prasyarat)
- Tidak ada prasyarat khusus.
Topik lanjutan
- Belum ada.
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.