Teori bilangan mempelajari bilangan bulat dan hubungan keterbagian di antara mereka. Topik ini tampak paling murni dari seluruh matematika, tetapi justru di sinilah lahir sistem yang menjaga pesan-pesan rahasia di internet.
Prima adalah bahan baku bilangan, dan cara membongkarnya selalu memberi hasil yang sama. Dari situ FPB bisa dibaca tanpa mendaftar faktor.
FPB dua bilangan bisa dicari dengan membagi berulang: ganti bilangan yang lebih besar dengan sisanya, lalu ulangi sampai sisanya nol. Untuk 252 dan 105: 252 = 2 · 105 + 42, lalu 105 = 2 · 42 + 21, lalu 42 = 2 · 21 + 0, sehingga FPB-nya 21. Cara ini jauh lebih cepat daripada mendaftar semua faktor.
Setiap bilangan bulat yang lebih besar dari 1 dapat ditulis sebagai hasil kali bilangan prima, dan caranya hanya satu kalau urutannya diabaikan. Sifat tunggal itulah yang menjadikan prima sebagai bahan baku bilangan, dan sekaligus yang membuatnya berguna untuk pengamanan data.
Dua bilangan kongruen modulo m kalau selisihnya habis dibagi m, artinya keduanya memberi sisa yang sama. Ini aritmetika jam: pada modulo 12, pukul 15 sama dengan pukul 3. Operasi biasa tetap berlaku, jadi penjumlahan dan perkalian bisa dikerjakan pada sisanya saja.
Keamanan sistem seperti RSA bersandar pada satu ketidakseimbangan: mengalikan dua bilangan prima besar itu mudah, tetapi memfaktorkan hasilnya kembali sangat sukar. Kunci publik dipakai untuk mengunci pesan, dan hanya pemilik kunci rahasia yang bisa membukanya. Kedua primanya rahasia, sedangkan hasil kalinya boleh diketahui siapa saja.
Kedua bilangan memberi sisa yang sama.
Ulangi sampai sisanya nol.
Boleh mereduksi sisanya lebih dulu.
n adalah hasil kali dua prima yang dirahasiakan.
Tentukan FPB(252, 105) dengan algoritma Euclid.
JawabanFPB(252, 105) = 21
Berapa sisa dari 210 dibagi 7?