Định lý Wilson


Hôm nay xin giới thiệu với các bạn một định lý liên quan đến số nguyên tố, đó là Định lý Wilson. Định lý này nói rằng nếu $p$ là một số nguyên tố thì số $(p-1)! + 1$ sẽ chia hết cho $p$.

Ở đây, ký hiệu $n!$ có nghĩa là $$n! = 1 \times 2 \times 3 \times \dots \times n.$$

Ví dụ,
  • $1! + 1 = 2$ chia hết cho $2$
  • $2! + 1 = 3$ chia hết cho $3$
  • $4! + 1 = 25$ chia hết cho $5$
  • $6! + 1 = 721$ chia hết cho $7$


Có nhiều cách chứng minh Định lý Wilson. Cách chứng minh mà chúng ta sắp trình bày ở đây là cách chứng minh sử dụng định lý nhỏ Fermat. 

Định lý nhỏ Fermat. Nếu $p$ là số nguyên tố và số $a$ không chia hết cho $p$ thì $$a^{p-1} = 1 \pmod{p}.$$

Các bạn có thể đọc cách chứng minh định lý nhỏ Fermat ở đây.

Để chứng minh định lý Wilson, chúng ta sẽ sử dụng một vài tính chất của đa thức. Các tính chất này mặc dù rất đơn giản nhưng nếu chúng ta biết cách sử dụng thì nó sẽ trở nên rất hữu ích trong việc giải toán.


Trước tiên chúng ta nói một chút về đa thức. Đa thức có dạng như sau $$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0.$$ Đa thức $P(x)$ này có bậc là $n$ và các số $a_0, a_1, \dots, a_n$ gọi là các hệ số. Số $a_0$ gọi là hệ số tự do, số $a_1$ là hệ số bậc $1$, $a_2$ là hệ số bậc $2$,..., $a_n$ là hệ số bậc $n$. Số $a_0$ còn được gọi là hệ số cuối cùng và $a_n$ gọi là hệ số đầu tiên của đa thức.



Bây giờ chúng ta phát biểu một vài tính chất của đa thức.


Tính chất 1. Đối với đa thức $$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$$ thì hệ số cuối cùng có thể được tính như sau: $a_0 = P(0)$.

Rõ ràng khi thay $x=0$ thì $P(0) = a_0$. Do đó, tính chất 1 là hiển nhiên. 



Tính chất 2. Nếu $P(x)$ là đa thức có bậc là $n \geq 1$, thì $$\Delta P(x) = P(x+1)-P(x)$$ sẽ là một đa thức có bậc $n-1$.

Chúng ta chứng minh tính chất 2 này cho một trường hợp đặc biệt là đa thức $x^n$, trường hợp tổng quát sẽ từ đó mà suy ra.

Đối với đa thức $x^n$, chúng ta có $$\Delta x^n = (x+1)^n - x^n = n x^{n-1} + {n \choose 2} x^{n-2} + {n \choose 3} x^{n-3} + \dots + n x + 1$$ Vậy $\Delta x^n$ là một đa thức bậc $n-1$.

Đối với trường hợp tổng quát thì $$\Delta P(x) = a_n \Delta x^n + a_{n-1} \Delta x^{n-1} + \dots + a_1 \Delta x$$ Vì $\Delta x^n$ là đa thức bậc $n-1$, $\Delta x^{n-1}$ là đa thức bậc $n-2$, ..., do đó $\Delta P(x)$ là một đa thức bậc $n-1$.



Tính chất 3. Hệ số đầu tiên của đa thức $\Delta P(x)$ sẽ bằng $n a_n$.

Như ở trên chúng ta đã chứng minh rằng $\Delta x^n$ là đa thức bậc $n-1$ với hệ số đầu tiên bằng $n$, do đó đa thức $\Delta P(x) = a_n \Delta x^n + \dots$ sẽ có hệ số đầu tiên là $n a_n$.



Bây giờ chúng ta sử dụng ba tính chất trên của đa thức để chứng minh định lý Wilson.

Định lý Wilson. Với mọi số nguyên tố $p$ thì $$ (p-1)! = -1 \pmod{p} $$

Chứng minh. Chúng ta sẽ dùng đa thức $$f_1(x) = x^{p-1} - 1$$

Chúng ta có những nhận xét về đa thức này như sau 
  • $f_1(x)$ là một đa thức bậc $p-1$
  • hệ số đầu tiên của đa thức $f_1(x)$ là $1$
  • hệ số cuối cùng của đa thức $f_1(x)$ là $-1$
  • theo định lý nhỏ Fermat, $f_1(1) = f_1(2) = f_1(3) = \dots = f_1(p-1) = 0 \pmod{p}$. 

Bây giờ chúng ta tạo đa thức mới như sau $$f_2(x) = \Delta f_1(x) = f_1(x+1)-f_1(x)$$ 
  • Theo tính chất 2 về đa thức mà chúng ta đã nói ở trên thì $f_2(x)$ là đa thức bậc $p-2$. 
  • Theo tính chất 3 thì hệ số đầu tiên của đa thức $f_2(x)$ là $p-1$. 
  • Và vì $f_2(x) = f_1(x+1) - f_1(x)$ cho nên $f_2(1) = f_2(2) = \dots = f_2(p-2) = 0 \pmod{p}$.

Tương tự với đa thức $$f_3(x) = \Delta f_2(x) = f_2(x+1)-f_2(x)$$
chúng ta có
  • $f_3(x)$ là một đa thức bậc $p-3$
  • hệ số đầu tiên của đa thức $f_3(x)$ là $(p-1)(p-2)$
  • $f_3(1) = f_3(2) = \dots = f_3(p-3) = 0 \pmod{p}$ 


Cuối cùng với đa thức $$f_{p-1}(x) = \Delta f_{p-2}(x) = f_{p-2}(x+1)-f_{p-2}(x)$$ thì
  • $f_{p-1}(x)$ là một đa thức bậc $1$
  • hệ số đầu tiên của đa thức $f_{p-1}(x)$ là $(p-1)(p-2)\dots 2 = (p-1)!$
  • $f_{p-1}(1) = 0 \pmod{p}$ 

Bây giờ chúng ta xem xét hệ số cuối cùng của các đa thức này.
  • Hệ số cuối cùng của đa thức $f_1(x)$ là $f_1(0) = -1$.
  • Hệ số cuối cùng của đa thức $f_2(x)$ là $$f_2(0) = f_1(1) - f_1(0) = - f_1(0) \pmod{p}$$
  • Hệ số cuối cùng của đa thức $f_3(x)$ là $$f_3(0) = f_2(1) - f_2(0) = - f_2(0) \pmod{p}$$
  • Hệ số cuối cùng của đa thức $f_{p-1}(x)$ là $$f_{p-1}(0) = f_{p-2}(1) - f_{p-2}(0) = - f_{p-2}(0) \pmod{p}$$

Từ đó suy ra $f_{p-1}(0) = (-1)^{p-2} f_1(0) = 1 \pmod{p}$.

Tóm lại, $f_{p-1}(x)$ là một đa thức bậc $1$, có hệ số đầu tiên là $(p-1)!$, hệ số cuối cùng là $f_{p-1}(0) = 1 \pmod{p}$, cho nên $$f_{p-1}(x) = (p-1)! x + c,$$ ở đây, $c = 1 \pmod{p}$.

Ở trên chúng ta đã chỉ ra rằng $f_{p-1}(1) = 0 \pmod{p}$, tức là $$(p-1)!  + c = 0 \pmod{p}$$ Kết hợp với $c = 1 \pmod{p}$, chúng ra suy ra định lý Wilson là $$(p-1)! + 1 = 0 \pmod{p}. \blacksquare$$



Như vậy chúng ta đã chứng minh xong định lý Wilson. Chúng ta thấy rằng ba tính chất của đa thức ở trên mặc dù rất đơn giản nhưng đã giúp cho chúng ta chứng minh được định lý Wilson. Đặc biệt, chúng ta đã sử dụng công thức $\Delta P(x) = P(x+1) - P(x)$. Công thức này tương tự như là phép lấy đạo hàm trong giải tích vậy.


Chúng ta tạm dừng ở đây, hẹn gặp lại các bạn ở kỳ sau.



Bài tập về nhà.

1. Viết lại chi tiết cách chứng minh định lý Wilson cho trường hợp $p=5$.

2. Chứng minh rằng nếu $n > 1$ và $(n-1)! = -1 \pmod{n}$ thì $n$ là một số nguyên tố.

3. Thay vì đặt $\Delta P(x) = P(x+1)-P(x)$, chúng ta có thể đặt $\Delta P(x) = P(x)-P(x-1)$. Phát biểu tính chất 2 và tính chất 3 cho trường hợp này.



Không có nhận xét nào:

Đăng nhận xét