Keterbagian dan Bilangan Prima

Keterbagian, faktor persekutuan terbesar, dan bilangan prima membentuk dasar teori bilangan: setiap bilangan bulat dibangun secara multiplikatif dari bilangan prima, dan cara pembangunannya mengatur hampir setiap hasil selanjutnya.

Definition

Bilangan bulat a membagi b jika b sama dengan a dikalikan dengan suatu bilangan bulat; bilangan prima adalah bilangan bulat yang lebih besar dari satu yang pembagi positifnya hanya satu dan dirinya sendiri. Keterbagian dan bilangan prima berkaitan dengan dekomposisi multiplikatif bilangan bulat dan blok bangunan yang tidak dapat direduksi dari dekomposisi tersebut.

Scope

Topik ini membahas relasi keterbagian pada bilangan bulat, algoritma pembagian, faktor persekutuan terbesar dan kelipatan persekutuan terkecil yang dihitung melalui algoritma Euclidean, identitas Bezout, lemma Euclid, teorema dasar aritmetika, dan teori dasar bilangan prima — ketakterhinggaannya, heuristik distribusinya, dan keprimaan.

Core questions

• Bagaimana algoritma Euclidean menghitung faktor persekutuan terbesar dan menghasilkan identitas Bezout?
• Mengapa lemma Euclid memaksa faktorisasi menjadi bilangan prima menjadi unik?
• Bagaimana seseorang dapat membuktikan ada tak terhingga banyaknya bilangan prima, dan apa yang diungkapkan oleh bukti-bukti tersebut?
• Bagaimana bilangan prima didistribusikan di antara bilangan bulat, dan bagaimana keprimaan ditentukan dalam praktik?

Key theories

Algoritma pembagian dan algoritma Euclidean

Setiap bilangan bulat yang dibagi dengan bilangan bulat positif akan menyisakan hasil bagi dan sisa yang unik; mengulanginya akan memberikan faktor persekutuan terbesar dan, melalui substitusi balik, bilangan bulat yang menyatakannya sebagai kombinasi linear (identitas Bezout).

Teorema dasar aritmetika

Setiap bilangan bulat di atas satu adalah hasil kali bilangan prima yang unik hingga urutannya; lemma Euclid (bilangan prima yang membagi suatu hasil kali akan membagi salah satu faktornya) adalah langkah kunci.

Ketakterhinggaan bilangan prima

Argumen klasik Euclid menunjukkan bahwa tidak ada daftar bilangan prima yang terbatas yang lengkap; rumus hasil kali Euler untuk fungsi zeta memberikan bukti analitik dan mengukur kepadatan prima melalui divergensi jumlah kebalikan bilangan prima.

Clinical relevance

Faktorisasi cepat dan pengujian keprimaan adalah dasar bagi kriptografi: keamanan RSA bertumpu pada kesulitan memfaktorkan hasil kali besar dari dua bilangan prima, sementara uji keprimaan yang efisien (seperti Miller-Rabin) membuat pembuatan kunci menjadi praktis.

History

Elemen Euclid (sekitar 300 SM) sudah memuat algoritma Euclidean, lemma Euclid, dan bukti bahwa bilangan prima tidak terbatas. Saringan Eratosthenes menyediakan metode sistematis pertama untuk mendaftar bilangan prima, dan karya abad kedelapan belas dan kesembilan belas oleh Euler, Legendre, dan Gauss merumuskan kembali distribusi prima sebagai masalah kuantitatif.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

Apakah satu adalah bilangan prima?

Tidak. Satu dikecualikan berdasarkan definisi agar faktorisasi prima menjadi unik; jika satu dianggap prima, setiap bilangan akan memiliki faktorisasi yang tak terhingga banyaknya.

Untuk apa identitas Bezout digunakan?

Identitas ini menyatakan bahwa faktor persekutuan terbesar dari dua bilangan bulat adalah kombinasi linear bilangan bulat dari keduanya, yang merupakan dasar untuk menghitung invers modular dan menyelesaikan persamaan Diophantine linear.