Bilangan Asli Selain 1 Memiliki Faktor Prima

Pada pembahasan sebelumnya mengenai pembuktian teorema bilangan komposit (yaitu “jika n memiliki faktor prima p dimana $p \le \sqrt{n}$ maka n adalah bilangan komposit”) yang dibahas dalam tulisan lain dengan judul Cara Membuktikan Bilangan Prima, di dalamnya kita menggunakan lemma “setiap bilangan bulat positif (bilangan asli) yang lebih besar dari 1 memiliki faktor prima” yang memerlukan pembuktian untuk mendukung pembuktian dalam tulisan sebelumnya, sehingga pada tulisan ini, kita akan membuktikan lemma (teorema kecil) yang dimaksud tersebut berikut ini.

“Setiap bilangan asli n lebih besar dari  1 memiliki faktor prima.”

Kita tahu bahwa setiap bilangan asli $n>1$ kalau bukan bilangan prima maka bilangan komposit. Kita buktikan untuk n yang komposit saja dengan bukti kontradiksi (karena jelas jika n bilangan prima sudah pasti n memiliki faktor prima, yaitu n itu sendiri). Andaikan bahwa terdapat bilangan asli n komposit lebih besar dari 1 yang tidak memiliki faktor prima. Ini artinya bahwa himpunan bilangan asli lebih besar dari 1 yang tidak memiliki faktor prima tersebut merupakan suatu himpunan tak-kosong. Karena itu, menurut Well Ordering Principle (Prinsip Terurut Rapi), terdapat bilangan asli terkecil m yang lebih besar dari 1 yang tidak memiliki faktor prima (dalam himpunan tersebut). Karena m komposit maka $m=ab$ dimana $1 < a < m$ dan $1 < b < m$. Jelas a dan b komposit sesuai pengandaian (karena jika a atau b prima maka pembuktian selesai). Perhatikan bahwa $a < m$ bertentangan dengan m bilangan asli terkecil dalam himpunan bilangan asli $n > 1$ yang tidak memiliki faktor prima. Jadi, pengandaian salah dan yang benar adalah n memiliki sebuah faktor prima.

Cukup menarik bahwa setiap bilangan asli lebih besar dari 1 memiliki faktor prima  yang dengan ini, secara intuisi kita peroleh kenyataan bahwa  setiap bilangan asli yang lebih besar dari 1 dapat dituliskan dalam bentuk perkalian bilangan-bilangan prima. Hal ini telah dinyatakan dalam teorema yang sangat terkenal dalam teori bilangan, yaitu The Fundamental Theorem of Arithmetic (Teorema Fundamental Aritmetik) yang berbunyi “Every positive integer different from 1 can be written uniquely as a product of primes”. Selengkapnya baca di Teorema Fundamental Aritmetik.