Bilangan bulat positif disebut prima jika dan hanya jika

Setiap bilangan bulat n >= 2 adalah prima atau hasil kali bilangan prima.

Pembahasan

Setiap bilangan bulat positif n(n>=2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Kita akan membuktikannya dengan prinsip induksi kuat.

Basis Induksi: Untuk n=2, 2 adalah bilangan prima, jadi pernyataan tersebut benar.

Langkah Induksi: Asumsikan bahwa pernyataan tersebut benar untuk semua bilangan bulat positif k, dimana 2 <= k < n. Kita perlu menunjukkan bahwa pernyataan tersebut juga benar untuk n.

Kasus 1: Jika n adalah bilangan prima, maka n dapat dinyatakan sebagai perkalian dari satu bilangan prima (dirinya sendiri), sehingga pernyataan tersebut benar.

Kasus 2: Jika n bukan bilangan prima, maka n dapat dinyatakan sebagai perkalian dari dua bilangan bulat positif a dan b, dimana 2 <= a < n dan 2 <= b < n. Berdasarkan asumsi induksi, a dan b dapat dinyatakan sebagai perkalian dari bilangan prima. Karena n = a * b, maka n juga dapat dinyatakan sebagai perkalian dari bilangan prima.

Dengan demikian, berdasarkan prinsip induksi kuat, setiap bilangan bulat positif n(n>=2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.