Bài toán về số nguyên tố

Một số bài toán và thuật toán liên quan tới số nguyên tố

Nguyễn Văn Trường

Trong các đề thi Olimpic tin học và trong nhiều bài toán tin chúng ta thường gặp dạng bài

tập có liên quan trực tiếp hay gián tiếp đến số nguyên tố. Các dạng bài tập này có thể là tìm

số nguyên tố thoả mãn một điều kiện nào đó hay kiểm tra tính nguyên tố của một số cho

trước. Bên cạnh đó, vấn đề tìm các số nguyên tố rất lớn đang được rất nhiều người quan

tâm vì sự ứng dụng thực tế của nó; đặc biệt là trong lĩnh vực mã hoá và an toàn thông tin,

việc tìm ra và sử dụng các số nguyên tố lớn đảm bảo tính an toàn rất cao cho hệ thống mã

hoá công khai nổi tiếng RSA. Bài viết này xin được giới thiệu với bạn đọc một số bài tập

và một số thuật toán hiệu quả có liên quan tới số nguyên tố. Trước hết chúng ta cùng

nghiên cứu một vài kiến thức làm cơ sở toán học cho các thuật toán sẽ trình bàỵ

Định nghĩa: Một số nguyên dương khác 1 được gọi là số nguyên tố nếu nó chỉ có hai ước

số dương là 1 và chính nó. Một số nguyên dương khác 1 không là số nguyên tố thì được

gọi là hợp số.

Định lý 1. Ước số dương bé nhất d khác 1 của một số nguyên dương a lớn hơn 1 là một số

nguyên tố.

Chứng minh Ta chứng minh bằng phản chứng như sau:

Giả sử d là hợp số => d = qd' , với 1 < q, d' < d. Mặt khác do a = dp theo giả thiết nên a =

qd'p => a có một ước số dương là d' với 1< d'< d. điều này là vô lý vì vậy d là số nguyên

tố.

Bài 1. Hãy phân tích một số nguyên n, n > 1 thành tích của các thừa số nguyên tố. Ví dụ

với n = 15 ta có dạng phân tích là n = 3.5

Theo định lý 1, ta có thể dễ dàng đưa ra thuật giải như sau:

B1.Tìm ước số dương d nhỏ nhất của n, (d >1) và gán n = n div d;

B2. Lặp lại B1 nếu n >1, ngược lại thì tập hợp các ước số đã tìm được chính là các thừa số

nguyên tố của n.

Định lý 2. Ước số dương bé nhất khác 1 của một hợp số a > 1 là một số nguyên tố không

vượt quá căn bậc hai của ạ

Định lý này cho phép ta kết luận: Một số nguyên dương n lớn hơn 1 là số nguyên tố nếu nó

không có ước số dương lớn hơn 1 và nhỏ hơn hoặc bằng

Chứng minh Giả sử p là ước số dương bé nhất khác 1 nhất của a =>p là số nguyên tố (Theo

định lý 1) và a = pd, với d≥ P => pd≥ p2

=>p2 ≤a =>p ≤

Định lý 3. (Định lý cơ bản của số học) Mọi số tự nhiên lớn hơn 1 đều phân tích được

thành tích của các thừa số nguyên tố và sự phân tích này là duy nhất nếu không kể đến thứ

tự của các thừa số.

Chứng minh Giả sử 1 < a N. Vì a > 1 nên a có ước nguyên tố là p1. Do đó a = p1a1, 1 ≤ a1

< a.

Nếu a1 = 1 => a= p1.

Nếu a1 > 1 => a1 có ước nguyên tố là p2. Do đó a1 = p2a2, 1≤ a2 < a 1.

Nếu a2 = 1 => a1 = p2 => a = p1p2.

Nếu a2 > 1 => a2 có ước nguyên tố là p3. Do đó a2 = p3a3, 1≤ a3 < a2. Cứ tiếp tục như vậy thì