BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Chứng minh số $1.000.000.007$ (một tỉ lẻ $7$ là số nguyên tố).
- 1 ngày trước
- 111 lượt xem
| Đặt vấn đề. Các thầy cô dạy Số học ở bậc THCS thường chỉ làm việc với các số nguyên tố trong phạm vi $1000$. Và rất nhiều thầy cô tỏ ra lúng lúng (thậm chí thành kiến) với các số nguyên tố rất lớn. Trong bài viết cuối tuần, lấy ý của gemini chúng tôi đã trình bày quan điểm: Nói một cách hình tượng, các số nguyên tố hàng trăm triệu chữ số giống như những đỉnh núi Everest của thế giới số học. Người ta chinh phục chúng không chỉ vì đỉnh núi đó tồn tại, mà vì quá trình chế tạo ra công cụ để leo lên đỉnh núi đó sẽ giúp thay đổi toàn bộ công nghệ của loài người dưới mặt đất. Với quan điểm như vậy như vậy hôm nay chúng ta xây dựng công nghệ để chứng minh số $1.000.000.007$ là số nguyên tố. Bài viết sau đây dành cho các GV phụ trách đội tuyển HSG MTCT đọc để trang bị kiến thức cho mình, không chỉ để dạy HSG MTCT mà còn nhằm nâng cao hiểu biết về một môn học mà mình phụ trách ở trường THCS. |
Định lý Pocklington.
| Cho một số tự nhiên $p$, giả sử $p – 1 = F \times R$, trong đó $F$ là số nguyên tố đã biết và $F > \sqrt{p} – 1$. Nếu tồn tại một số nguyên $a$ sao cho: $$\left\lbrace\begin{array}{ll} a^{p-1} \equiv 1 \pmod p &(1)\\ \text{UCLN}\left(a^R – 1, p\right) = 1 &(2)\end{array} \right.$$ thì $p$ là một số nguyên tố. |
Đặt $p=1000000007$, ta có: $p-1=500000003\times 2$. Trong bài này ta tạm chấp nhận $500000003$ là số nguyên tố. Trong bài sau ta sẽ dùng phép thử Miller-Rabin để chứng minh $F=500000003$ là số nguyên tố. Điều kiện $F>\sqrt{p}-1$ hiển nhiên được thoả.
Xét $a=2$ (số thường chọn), điều kiện (2) là hiển nhiên: 
. Bây giờ ta chứng minh $a^{1000000006} \equiv 1 \quad (\text{mod}\ 1000000007)$ (rất tiếc không dùng thuật toán luỹ thừa nhanh được).
Biểu diễn số $1000000006$ qua hệ nhị phân: Mở Cơ hệ 
Bấm FORMAT 2 lần 
, bỏ số $0$ chỉ lấy số $1$, đếm từ bên phải hàng dưới tới, hết hàng dưới đếm tiếp từ bên phải hàng trên đến hết, chú ý vị trí của số $1$ (quy ước vị trí đầu tiên là vị trí $0$, vị trí cuối cùng là vị trí $31$) . Ta có:
$$1000000006=\underbrace{2^1+2^2+2^9+2^{11}+2^{14}+2^{15}}_{\text{hết hàng dưới}}+2^{17}+2^{19}+2^{20}+2^{23}+2^{24}+2^{25}+2^{27}+2^{28}+2^{29}$$
Suy ra $2^{1000000006}=2^{2^1}\times 2^{2^2} \times 2^{2^9}\times 2^{2^{11}}\times 2^{2^{14}}\times 2^{2^{15}}\times 2^{2^{17}}\times 2^{2^{19}}\times 2^{2^{20}}\times 2^{2^{23}}\times 2^{2^{24}}\times 2^{2^{25}}\times 2^{2^{27}}\times 2^{2^{28}}\times 2^{2^{29}}\quad (3)$
Ta lưu $1000000007$ vào A 
, sau đó mở một bảng tính ta tính
$\fbox{$2^{2^n}-A \text{Int}\dfrac{2^{2^n}}{A}, n=1, 2,\dots 29$}$ (liệt kê 29 kết quả, sau đó chọn lọc).
Nhập $2^{2^1}$ vào $A_1$ (không vcần tìm dư của phép chia cho $A=1000000007$)
.
Từ $A_2$ đến $A_{29}$ điền công thức: $A_1^2-A \text{Int} \dfrac{A_1^2}{A} $ 
Tuyển chọn cột A các giá trị của tích (3) vào cột B 
Cuối cùng lấy tích luỹ tiến: Để con trỏ ở $C_2$ nhập phép tính $B_1\times B_2$ hay $4\times 16=64$. Sau đó từ $C_3$ đến $C_{15}$ điền công thức: $\fbox{$B_3\times C_2-A \text{Int}\dfrac{B_3\times C_2}{A}$}$.
Tại $C_{15}$ kết quả $1$, nghĩa là $2^{1000000006} \equiv 1 \quad (\text{mod}\ 1000000007)$ (đpcm).
Vậy theo định lý Pocklington số $1.000.000.007$ là số nguyên tố.
About TS. Nguyễn Thái Sơn
