Euclid với thuật toán số nguyên tố

Trong toán học, nền tảng mà học sinh được học từ nhỏ là Số học và Hình học. Euclid đã đóng góp cho nhân loại không chỉ hệ thống Hình học đầy đủ mà ông còn xây dựng một số lý thuyết Số học cơ bản. Trong đó có thuật toán về số nguyên tố mang tên ông: Thuật toán Euclid. Đây được coi như kiến thức cơ bản về hệ thống số.

Khi học Số học, ban đầu là học những phép toán như cộng, trừ, nhân, chia. Từ học phép cộng, ta biết đến phép trừ. Đây là những phép toán tự nhiên, cổ xưa nhất mà loài người biết tới. Sau đó, phép nhân là cộng nhiều số bằng nhau. Từ phép nhân, ta có phép chia là phép toán ngược lại. Chẳng hạn 5 x 7 = 35, ta có 35 : 5 = 7.

Vấn đề đặt ra là: Cho trước một số tự nhiên, hãy viết số đó thành tích của những số nhỏ hơn nó và lớn hơn 1. Ví dụ 35 = 5 x 7. Một cách đơn giản là ta phải thử chia số đó cho tất cả những số nhỏ hơn nó xem phép chia nào không dư. Chẳng hạn, với số 70, ta chia cho 2 được 35. Mà 35 = 5 x 7, suy ra 70 = 2 x 5 x 7. Nghĩa là, từ những số tự nhiên lớn, ta tìm cách chia nó cho một số tự nhiên nhỏ hơn nó, rồi lấy thương mới tìm được chia cho số nhỏ hơn nữa.

Những số như 2, 5, 7 được gọi là số nguyên tố. Đó là những số tự nhiên lớn hơn 1 và không thể chia hết cho số tự nhiên nào lớn hơn 1 nhưng nhỏ hơn nó. Số nguyên tố tuy ra đời một cách tự nhiên từ xa xưa nhưng chứa đựng những bí ẩn lớn mà nhân loại chưa khám phá được nhiều. Không có một quy tắc nào cho phép tìm nhanh những ước nguyên tố của một số tự nhiên bất kỳ. Vì vậy, một trong những ứng dụng quan trọng của số nguyên tố là dùng làm mã hóa bảo mật. Ví dụ, nếu biết chìa khóa là 6 thì mật mã là 23 (vì 6 = 2 x 3; 2, 3 là những số nguyên tố và 2 < 3). Vì không có thuật toán nên ta buộc phải thử. Với máy tính hiện đại nhất, có thể thực hiện hàng tỷ phép tính trong một giây thì vẫn có thể phải mất hàng nghìn năm mới có thể tìm ra mật mã.

Bài 1. Viết số 60 thành tích các hai số tự nhiên.
Giải. Ta có 60 = 1 x 60 = 2 x 30 = 3 x 20 = 4 x 15 = 5 x 12 = 6 x 10.

Bài 2. Viết số 100 thành tích các số nguyên tố.
Giải. Ta có 100 = 2 x 2 x 5 x 5.
Nhận xét. Thực hiện thuật toán Euclid, ta có 100 : 2 = 50, 50 : 2 = 25, 25 : 5 = 5.

Bài 3. Viết số 48 thành tích các số nguyên tố.
Giải. Ta có 48 = 2 x 2 x 2 x 2 x 3.
Nhận xét. Thực hiện thuật toán Euclid, ta có 48 : 2 = 24, 24 : 2 = 12, 12 : 2 = 6, 6 : 2 = 3.
Mật mã ở đây là 22223.

Kết quả kỳ trước. Số a có 3 cách điền là 1, 3 và 5. Với mỗi cách điền số a thì bộ (b, c) có 4 cách điền. Sau đó, bộ số (d, e) có 2 cách điền. Ta có 3 x 4 x 2 = 24. Đáp số: 24. Trao giải 50.000 đồng/người cho bạn Trương Minh Sơn (lớp 6A9, THCS Nghĩa Tân).

Kỳ này. Tìm mật mã của số 1.000. Câu trả lời gửi về chuyên mục "Toán học, học mà chơi", tòa soạn Báo Hànộimới, 44 Lê Thái Tổ, Hoàn Kiếm, Hà Nội.