Một định lý về số (không) nguyên tố và chứng minh đẹp của Euclid

Posted on October 3, 2014 by

1


Op-Economica, 3-10-2014 — Quá trình ‘biến đổi’ tư duy học sinh phổ thông từ các phép tính toán đại số sang tư duy trừu tượng thường liên quan tới thay đổi nhận thức rất đáng kể: từ tính toán tới chứng minh các mệnh đề.

Bài ngắn này nói lại về một định lý – có thể không quá quan trọng, và không phải ai cũng để ý – về số (không) nguyên tố. Mặc dù chứng minh không có gì là hóc búa, nhưng lại đại diện cho vẻ đẹp của lập luận toán học. Cha mẹ có thể giúp cho con cái nhìn thấy vẻ đẹp và sự lý thú ấy. Học toán mà chỉ có roi vọt và nỗi sợ hãi điểm thấp, thì khó mà hiệu quả, vì đây là hành trình tư duy lâu dài, kỷ luật và sự say mê.

Euclid (330-275 TCN)

Euclid (330-275 TCN)

Xin bắt đầu luôn.

* Mệnh đề phỏng ước: Giả sử n là một số nguyên lớn hơn 1, và n không phải là số nguyên tố. Vậy thì, 2^n - 1 cũng không phải là số nguyên tố.

* Chứng minh:

Do n không phải là số nguyên tố, do đó, tồn tại các số nguyên dương ký hiệu ab sao cho: a<n, b<n, và n=a\cdot b.

Cho số x=2^b - 1y = 1+2^b + 2^{2b}+\ldots+ 2^{(a-1)b}. Vậy thì:

xy = (2^b-1)\cdot (1+2^b +2^{2b}+\ldots+2^{(a-1)b})

xy = 2^b \cdot (1+2^b +2^{2b}+\ldots+2^{(a-1)b}) - (1+2^b +2^{2b}+\ldots+2^{(a-1)b})

xy = (2^b +2^{2b}+\ldots+2^{a\cdot b}) - (1+2^b +2^{2b}+\ldots+2^{(a-1)b})

xy = 2^{ab}-1=2^n -1

b<n nên ta suy ra x=2^b - < 2^n -1. Đồng thời, vì ab = n>a, nên b>1. Do đó, x=2^b -1 > 2^1 -1 = 1. Suy ra, y <xy = 2^n -1. Rõ ràng, 2^n -1 được chứng minh là tích của 2 số nguyên dương x,y và cả hai số đều nhỏ hơn 2^n -1, do đó nó không thể là số nguyên tố.

“Phỏng ước” này đã được chứng minh, và có thể gọi là một định lý.

Chứng minh này của nhà toán học cổ Hy Lạp (330-275 TCN), trình bày trong Cuốn IX của bộ sách Elements lừng danh của ông vào khoảng năm 350 TCN. Đây là một trong những chứng minh định lý nổi tiếng và đẹp nhất của toán học.


Velleman D.J. (2006), trang 2-4.