Số nguyên tố là gì?
Các số nguyên tố có thể là những ''nguyên tử'' của số học: đi từ chúng, người ta có thể đạt được tất cả các số khác. Một định lý cơ bản của số học là mọi số nguyên dương có thể thu được từ phép nhân nhiều số nguyên tố. Định nghĩa cổ điển nêu rằng một số là nguyên tố nếu nó chỉ chia được cho nó và cho 1. Vì vậy danh mục các số nguyên tố bắt đầu như sau: 2, 3, 5, 7, 11, 13, 17, 19, 23, v.v... Người ta có thể chứng minh hơi thô thiển về sự tồn tại “việc phân tích thành thừa số nguyên tố” khi nhận xét rằng một số n đã cho, hoặc là nguyên tố, thì khi ấy việc phân tích là xong trước khi bắt đầu, hoặc không phải là nguyên tố, là điều cho phép chia nó thành tích của hai số nhỏ hơn, từ đó đặt lại vấn đề là tìm các số chia, cứ như thế cho đến khi tiến trình dừng lại (là điều nhất định xảy ra vào lúc này hay lúc khác): rốt cuộc, người ta thu được đúng số cần tìm. Vấn đề hơi ít trực giác hơn nhưng cũng cơ bản là, đối với một số nào đó, chỉ có một cách phân tích khả dĩ thành tích của các thừa số nguyên tố, ít ra theo thứ tự gần các thừa số nghĩa là 2 x 3 và 3 x 2 được xem như là cùng cách phân tích số 6 thành các thừa số nguyên tố.
