Số học thuật toán–Hà Huy Khoái

Trong những năm gần đây, sự phát triển của Tin học đã làm thay đổi nhiều ngành truyền thống của Lí thuyết số (trong cuốn sách này, chúng ta thường dùng từ “Số học”). Nếu như trước thập kỷ 70, số học vẫn được xem là một trong những ngành lí thuyết xa rời thực tiễn nhất, thì ngày nay, nhiều thành tựu mới nhất của số học có ứng dụng trực tiếp vào các vấn đề của đời sống, như thông tin, mật mã, kĩ thuật máy tính. Một phương hướng mới của số học ra đời và phát triển mạnh mẽ: số học thuật toán. Có thể nói, đó là chiếc cầu nối giữa số học với tin học. Với việc sử dụng rộng rãi máy tính trong nghiên cứu số học, nhiều người cho rằng, số học ngày nay đã thành một khoa học thực nghiệm! Điều đó thể hiện khá rõ trong những “thuật toán xác suất” được đề cập đến trong cuốn sách này.

Mục đích của cuốn sách nhỏ này là cung cấp cho người đọc một số kiến thức sơ bộ về số học thuật toán. Cuốn sách không đòi hỏi ở người đọc một kiến thức chuẩn bị nào về lý thuyết số. Vì thế cũng có thể gọi nó là “Nhập môn thuật toán vào số học”. Điều đó có nghĩa là, trong nhiều con đường khác nhau để đi vào số học, ta chọn con đường thuật toán: các định lí, khái niệm của số học được trình bày cùng với các thuật toán xây dựng chúng. Trong nhiều trường hợp, các thuật toán có kèm theo đánh giá sơ bộ về độ phức tạp. Cuốn sách nhằm một số đối tượng khá rộng rãi: những sinh viên, nghiên cứu sinh về số học và tin học, những người quan tâm đến lí thuyết và ứng dụng của số học hiện đại. Nhiều phần của cuốn sách có thể có ích cho học sinh các lớp chuyên toán và chuyên tin học. Chương đầu tiên của cuốn sách được dành để giới thiệu vài định nghĩa cơ bản nhất của lí thuyết thuật toán. Ba chương tiếp theo trình bày những vấn đề cơ sở của số học. Chương 5, ngoài việc chuẩn bị kiến thức cho những phần tiếp theo, có bình luận ít nhiều về vai trò của sự tương tự giữa số và đa thức trong sự phát triển của số học hiện đại.

Để người đọc có thể hình dung phần nào các ứng dụng của số học thuật toán, cuốn sách dành chương 6 để nói về lí thuyết mật mã. Một vài ứng dụng gần đây của lí thuyết đường cong elliptic vào mật mã được trình bày trong chương 7. Cũng có thể xem Chương 7 là một nhập môn ngắn và sơ cấp vào lí thuyết đường cong elliptic, một trong những lí thuyết phong phú nhất của Hình học đại số số học. Cuối mỗi chương đều có một số bài tập dành cho độc giả muốn đọc cuốn sách “một cách tích cực”. Một số bài tập mang tính chất luyện tập và tính toán thực hành, một số khác là mở rộng lí thuyết. Trừ chương cuối về đường cong elliptic, các chương còn lại đều có kèm theo hướng dẫn thực hành tính toán bằng chương trình MAPLE. Phần hướng dẫn thực hành này do Tạ Thị Hoài An biên soạn. Cuối cuốn sách có phần tự kiểm tra kiến thức dành cho những độc giả học giáo trình này với sự trợ giúp của máy tính.

Do nhiều nguyên nhân khác nhau, cuốn sách chắc chắn còn rất nhiều thiếu sót. Tác giả hy vọng nhận được những lời phê bình của bạn đọc.

Hà nội, 1998

Hà Huy Khoái

Chương 1 và chương 2

Chương 3

Chương 4

Chương 5

Chương 6

Chương 7

Bài tâp

Lê Văn Chuyên – THPT Hiệp Hòa số 1

Vì sao 1 không phải là số nguyên tố?

Toàn bộ số tự nhiên được chia làm ba loại: Loại 1 là các số nguyên tố ( như 2,3,5,7,11,13,...), Loại 2 là các hợp số ( 4,6,8,9,10,...). Số "1" không phải là số nguyên tố, cũng không phải là hợp số nên nó là một loại riêng thứ 3. Số nguyên tố là những số chỉ chia hết cho 1 và chính nó, còn hợp số có thể chia hết cho những số khác. Ví dụ, hợp số 6, ngoài chia hết cho 1 và 6 ra, nó còn chia hết cho 2 và 3. Đây là lý do chính để chia ra thành loại hợp số và số nguyên tố. Nhưng số 1 cũng chia hết cho 1 và chính nó, vì sao không gọi là số nguyên tố ? Nếu 1 là số nguyên tố thì chỉ cần chia số tự nhiên thành 2 loại có tốt hơn không ? Để trả lời vấn đề này, trước tiên ta phải đặt vấn đề vì sao phải bàn đến số nguyên tố. Ví dụ số 3003 có thể chia hết cho số nguyên tố nào? Cũng có nghĩa là số nào là thừa số của 3003 ? Đương nhiên ta có thể xét tất cả các số từ 1 đến 3003, nhưng như vậy thì rất tốn công.
Chúng ta biết rằng, hợp số có thể là tích của nhiều số nguyên tố, tức là nhân nhiều số nguyên tố với nhau, nói cách khác, chính là phân tích thành thừa số nguyên tố.Đương nhiên, mỗi hợp số đều có thể phân tích thành thừa số nguyên tố và chỉ có một kết quả mà thôi ( tất nhiên không kể đến thứ tự các thừa số).
Ví dụ : số 3003 có thể phân tích thành 3.7.11.13
Bây giờ ta quay trở lại vấn đề vì sao 1 không phải là số nguyên tố. Nếu 1 được coi là số nguyên tố thì khi phân tích một hợp số thành thừa số nguyên tố, đáp án sẽ không phải là duy nhất nữa!
Ví dụ : Phân tích số 3003 thành thừa số nguyên tố sẽ xảy ra các trường hợp sau:
3003 = 3.7.11.13
3003 = 1.3.7.11.13
3003 = 1.1.3.7.11.13
............
Như vậy, khi phân tích có thể tuỳ ý thêm các thừa số 1 vào như vậy quả thực là không cần thiết chút nào, và kết quả phân tích lại không duy nhất, chỉ tăng thêm những phiền phức không cần thiết. Vì vậy 1 không được coi là số nguyên tố.(trích http://www.dongnaionline.com/)