Lompat ke konten utama
Kelas
Matematika DiskritPelajaran 11 dari 16 · Modul 3, Rekursi, induksi, dan bilangan bulat

Modul 3 · Rekursi, induksi, dan bilangan bulat

Aritmetika modular, kongruensi, dan algoritma Euclid

Setelah pelajaran ini kamu bisa menghitung sisa bagi, memeriksa kongruensi modulo n, dan mencari FPB dua bilangan dengan algoritma Euclid.

  • ±14 menit
  • 3 latihan
  • Diperiksa 27 Sep 2026

Latihan di pelajaran ini butuh akun gratis. Progres, kode, dan catatanmu hanya tersimpan di browser ini. Masuk untuk menyimpannya

Materi

a mod n adalah sisa pembagian a oleh n, selalu salah satu dari 0, 1, …, n − 1. Jam dinding memakai modulo 12: lima jam setelah pukul 10 adalah pukul (10 + 5) mod 12 = 3. Dua bilangan a dan b kongruen modulo n, ditulis a ≡ b (mod n), bila sisa pembagiannya oleh n sama; definisi yang setara: n membagi habis a − b. Contoh: 8 ≡ 23 (mod 5), karena keduanya bersisa 3. Kongruensi bersifat refleksif (a ≡ a), simetris (bila a ≡ b maka b ≡ a), dan transitif (bila a ≡ b dan b ≡ c maka a ≡ c), sehingga kongruensi adalah relasi ekuivalen. Aritmetika modular dipakai untuk menghitung hari dalam seminggu, giliran jadwal, dan angka pemeriksa pada nomor identitas.

FPB (faktor persekutuan terbesar) dua bilangan adalah bilangan bulat positif terbesar yang membagi habis keduanya. Algoritma Euclid mencarinya tanpa memfaktorkan: bila b = 0, FPB-nya a; bila tidak, FPB(a, b) = FPB(b, a mod b). Contoh untuk 84 dan 36: 84 mod 36 = 12, lalu 36 mod 12 = 0, sehingga FPB(84, 36) = 12. Di Python, operator % memberi sisa bagi, pow(a, k, n) memberi aᵏ mod n tanpa menghitung aᵏ utuh, dan math.gcd memberi FPB.

print((10 + 5) % 12)     # 3
print(23 % 5 == 8 % 5)   # True: 23 ≡ 8 (mod 5)
print(-7 % 3)            # 2, bukan -1

Latihan

Jawaban diperiksa di server. Lulus berarti kamu memahami contohnya, bukan penilaian seluruh pekerjaanmu.

Latihan 1 dari 3

Hari diberi nomor Senin = 0, Selasa = 1, sampai Minggu = 6. Hari ini Rabu. Berapa nomor hari 100 hari dari sekarang?

Latihan 2 dari 3

Pakai algoritma Euclid: berapa FPB dari 252 dan 198?

Catatanmu

Memuat catatan…

tersimpan otomatis, ikut tercetak · 0/4.000

Lanjutkan ke

Tampilkan 1 lagi