Phân tích các số dạng 10n +1 ra thừa số nguyên tố

PHÂN TÍCH CÁC SỐ DẠNG 10ⁿ + 1 RA THỪA SỐ NGUYÊN TỐ

Bài viết này nói về việc sử dụng phần mềm Geogebra trong việc phân tích số dạng 10ⁿ + 1 ra thừa số nguyên tố.

Nội dung chính

Lời mở đầu

Trong tạp chí Toán học và Tuổi trẻ số 29 (tháng 2-1967, trang 15), Giáo sư Lại Đức Thịnh đã viết như sau: “Bài toán: Các số nguyên tố có dạng 1000 . . . 0001 gồm bao nhiêu chữ số 0 là một bài toán chưa giải được”. Theo tìm hiểu của chúng tôi, hơn 50 năm qua chưa có phản hồi nào về bài toán này, có lẽ cũng vì không ai đủ sức (bằng tay) để phân tích các số dạng 100..001 với n số 0 ra thừa số nguyên tố.

Bài báo này trình bày cách sử dụng Geogebra như một công cụ thí nghiệm trong phân tích số 10ⁿ + 1 ra thừa số nguyên tố, và trả lời về cơ bản câu hỏi nêu trên.

Giới thiệu về Geogebra

Geogebra là một phần mềm toán học có thể làm mọi tính toán toán học và vẽ hình trong chương trình toán phổ thông và đại học. Hơn nữa, Geogebra được cài đặt phần mềm chuyển đổi tiếng Anh sang tiếng Việt, do đó Geogebra là một công cụ tiện dùng và hữu ích trong dạy và học, đặc biệt trong dạy và học theo chương trình và sách giáo khoa mới. Bạn đọc có thể tìm hiểu cài đặt và sử dụng Geogebra theo và tìm hiểu một số ứng dụng của Geogebra trong

Hội thảo Khoa học, Sầm Sơn 28-28/09/2019

Sử dụng Geogebra trong phân tích số nguyên tố ra thừa số

Một số chỉ chia hết cho 1 và chính nó được gọi là số nguyên tố. Với những số lớn, thuật toán Euclid và các thuật toán hiện đại phân tích một số ra thừa số nguyên tố ở thời điểm hiện tại chưa thể cho kết quả trong thời gian thực. Vì vậy, việc phân tích một số ra thừa số nguyên tố vẫn còn là bài toán rất khó, ngay cả với những hệ thống máy tính song song cỡ lớn và các phần mềm chuyên dụng. Mặt khác, với phần mềm thương mại Maple hoặc phần mềm free (miễn phí trên mạng) Geogebra, có thể phân tích được số tự nhiên với dưới 35 chữ số tương đối nhanh (chỉ trong vài giây). Điều này giúp các thày cô giáo có thể hướng dẫn học sinh Trung học Phổ thông, thậm chí học sinh Trung học Cơ sở, tập dượt nghiên cứu với đề tài Phân tích một số ra thừa số nguyên tố.

Sau khi cài đặt, để phân tích một số ra thừa số nguyên tố nhờ Geogebra, ta mở Geogebra, chọnCAS (Computer Algebra System-hệ tính toán đại số). Sau đó chỉ cần khai báo duy nhất một lệnh ifactor () với số cần phân tích được khai báo trong ngoặc, thí dụ, số dạng 10ⁿ + 1, máy sẽ lập tức cho ra ngay kết quả như trong Bảng 1.

Bảng 1 Phân tích các số dạng 100 . . . 001 với n = 2, . . . , 50 chữ số 0 ra thừa số nguyên tố.

Quan sát Bảng 1, ta rút ra quy luật sau:

Khẳng định 1 Các số dạng N_n := 100 . . . 001 với n = 2k chữ số 0 chia hết cho 11.

Nhận xét 0.1. Với k = 0 thì 11 là số nguyên tố.

Chứng minh 1 Làm phép nhân trực tiếp ta được

Chứng minh 2 Ta có

Như vậy, câu hỏi của Giáo sư Lại Đức Thịnh đã được trả lời một nửa.

Có thể thấy rõ hơn trong Phụ lục 1 dưới đây.

Phụ lục 1

Áp dụng Mặc dù với n đủ lớn, thí dụ, với n = 36, 40, 42, 46, 50, Geogebra không thể phân tích được các số đó ra thừa số (Geogebra cho dấu ?, xem Bảng 1). Nhưng ta vẫn khẳng định được nó chia hết cho 11. Ta có thể kiểm tra điều này nhờ Geogebra bằng phép chia (sử dụng lệnh chia: /) như sau.

Vậy chỉ còn chưa biết các số dạng N_2k+1 có là số nguyên tố hay không.

Quan sát Bảng 1 ta đi đến

Khẳng định 2 Các số dạng N_n := 100 . . . 001 với n = 4k + 1 chữ số 0 chia hết cho 101.

Nhận xét 2 Với k = 0 thì 101 là số nguyên tố.

Chứng minh 1 Phép nhân trực tiếp cho

Chứng minh 2 Ta có

Các số lẻ n = 2k + 1 chỉ có thể là n = 4k₁ + 1 hoặc n = 4k₂ + 3. Ta đã thấy rằng, nếu

= 4k₁ + 1 thì N_n chia hết cho 101. Vậy câu hỏi của Giáo sư Lại Đức Thịnh đã được trả lời thêm một phần tư (tổng cộng đã bằng 1/2 + 1/4 = 3/4). Chỉ còn các số dạng n = 4k + 3.

Có thể thấy rõ hơn trong Phụ lục 2 dưới đây.

Phụ lục 2

Áp dụng Mặc dù Geogebra không phân tích được N₃₇, N₄₅ ra thừa số (xem Bảng 1), nhưng n = 37 = 4 9 + 1 và n = 45 = 4 11 + 1 nên ta khẳng định N₃₇, N₄₅ chia hết cho 101. Ta có

Quan sát tiếp Bảng 1, ta thấy nếu n = 8k + 3 thì N_n chia hết cho 10001 = 73 137. Ta

có

Khẳng định 3 Các số dạng N_n := 100 . . . 001 với n = 8k + 3 chữ số 0 chia hết cho 10001.

Nhận xét 3 Với k = 0 thì 10001 = 73 137 là hợp số.

Chứng minh 1 Phép nhân trực tiếp cho

Chứng minh 2 Ta có

Các số lẻ n = 4k + 3 chỉ có thể là n = 8k₁ + 3, (khi n = 2k₁ ) hoặc n = 8k₁ + 7 (khi

= 2k₁ + 1)

Vậy chỉ còn trường hợp n = 8k₁ + 7 là chưa có câu trả lời, hay câu hỏi của Giáo sư Lại Đức Thịnh đã được trả lời thêm một phần tám (tổng cộng bằng 1/2 + 1/4 + 1/8 = 7/8).

Có thể thấy rõ hơn trong Phụ lục 3 dưới đây.

Phụ lục 3

Quan sát tiếp Bảng 1, ta thấy nếu n = 16k + 7 thì N_n chia hết cho 100000001 = 17 5882353.

Ta có

Khẳng định 4 Các số dạng N_n := 100 . . . 001 với n = 16k + 7 chữ số 0 chia hết cho 100000001.

Nhận xét 4 Với k = 0 thì 100000001 = 17 5882353 là hợp số.

Chứng minh 1 Phép nhân trực tiếp cho

Chứng minh 2 Ta có

Có thể thấy rõ hơn trong Phụ lục 4 dưới đây.

Phụ lục 4

Vì n = 8k + 7 chỉ có thể là n = 16k + 7 (khi k = 2k₁) hoặc n = 16k₁ + 15 (khi k = 2k₁ + 1

nên chỉ còn các số với n = 16k₁ + 15 là chưa biết có phải là số nguyên tố hay không. Tổng quát hóa từ bốn khẳng định trên, ta đi đến

Hội thảo Khoa học, Sầm Sơn 28-28/09/2019

Tuy nhiên, với m = 13, Geogebra trả lời:

Tính toán quá lâu nên bỏ, nghĩa là Geogebra không tính toán và trả lời được đây là số nguyên tố hay không.

Kết luận

Kết luận 1

Bài toán phân tích số dạng 100 . . . 001 ra thừa số nguyên tố liên quan đến bài toán sau đây: Tìm số nguyên tố p có tổng các chữ số của nó là một số nguyên tố q mà tổng các chữ số của q là 2.

Lời giải. Vì q là số nguyên tố q mà tổng các chữ số của q là 2 nên q = 2, tức là p chỉ có thể có dạng 100 . . . 001. Thí dụ: 11, 101.

Dẫn đến bài toán: Có bao nhiêu số nguyên tố dạng 10^{^n} + 1? – hiện nay có lẽ chưa có câu trả lời

Kết luận 2

Để tìm câu trả lời cho câu hỏi của Giáo sư Lại Đức Thịnh, thực ra chỉ cần chứng minh Mệnh đề 2. Tuy nhiên, chúng tôi muốn trình bày con đường đi đến lời giải của chúng tôi, cũng khá vất vả và công phu, và phải dùng đến công cụ thí nghiệm là Geogebra. Một câu hỏi tuy nhỏ, phát biểu đơn giản, nhưng tồn tại 50 năm (và bây giờ cũng vẫn chưa giải quyết trọn vẹn). Tất nhiên, không loại trừ khả năng đã có chứng minh hoặc phản ví dụ (mà chúng tôi chưa biết) là có số dạng là số nguyên tố.