Định lý Wilson và áp dụng

 

Khi làm toán về chia hết và đồng dư nếu ta bắt gặp đề bài có giả thiết về $(p-1)!$ với $p$ là số nguyên tố ta sẽ nghĩ đến định lý Wilson. Ở đây chúng tôi chỉ đề cập đến ứng dụng, không đề cập đến chứng minh.

 

 

 

Định lý Wilson: Nếu $p$ là một số nguyên tố thì $(p-1)!\equiv -1$ (mod $p$).

 

 

 

Áp dụng:

 

 

 

1. Chứng minh rằng $10!+1$ chia hết cho $11$.

 

Giải:

$11$ là số nguyên tố nên $10!\equiv -1$ (mod $11$). Suy ra $10!+1\equiv 0$ (mod $11$), nghĩa là $10!+1$ chia hết cho 11.

 

 

2. Tìm dư của phép chia $5!\times 25!$ cho $31$.

 

 

Giải:

 

$31$ là số nguyên tố nên $30!\equiv -1$ (mod $31$). Suy ra

 

$30\times 29\times 28\times 27\times 26\times 25! \equiv -1$ (mod $31$).

 

Vì $30, 29, 28, 27, 26$ lần lượt đồng dư với $-1, -2, -3, -4, -5$ theo mô-đu-lô 31 nên

 

$(-1)(-2)(-3)(-4)(-5)\times 25! \equiv -1$ (mod $31$).

 

$(-1)^5\times 5!\times 25! \equiv -1$ (mod $31$), nghĩa là $5!\times 25!\equiv 1$ (mod $31$)

 

 

3. Chứng minh rằng nếu $p$ là số nguyên tố lẻ thì $\quad 2(p-3)! \equiv -1 $ (mod $p$).

 

 

Giải:

 

Ta có: $(p-1)! \equiv -1$ (mod $p$).

 

Vì $p \geqslant 3$ nên ta có thể viết: $(p-1)!=(p-1)(p-2)(p-3)! \equiv -1$ (mod $p$)

 

$(p-1)(p-2)=p^2-3p+2 \equiv 2$ (mod $p$).

 

Vậy $2(p-3)! \equiv -1$ (mod $p$.)

 

 

Sau đây là một áp dụng không liên quan đến giai thừa.

 

 

4. Tìm dư của phép chia $5^{100}$ cho $7$.

 

 

Giải:

 

Ta có : Vì $7$ là số nguyên tố nên theo định lý Wilson ta có:

 

$5^6\equiv -1$ (mod $7$)

 

Suy ra $5^{100}=(5^6)^{16}\times 5^4 \equiv 5^4$ (mod $7$).

 

$5^4 \equiv 2$ (mod $7$).

 

Vậy dư của phép chia $5^{100}$ cho $7$ bằng $2$.

 

 

Nhận xét. Những bài toán trên được ra đời vào thời kỳ chưa có máy tính cầm tay (khoảng năm 1970) . Do đó ta phải xây dựng các định lý mạnh. Ngày nay với máy tính cầm tay khá phổ biến, ta có thể giải trực tiếp các bài tập đó, ví dụ bài 4 như sau:

 

 

$100=4+32+64 \Rightarrow 5^{100}=5^4\times \underbrace{5^{32}\times 5^{64}}_{\text{số sau là bình phương của số trước}}$.

 

abc1a 1

 

Vì $5^4\equiv 2$ (mod $7$) nên bình phương nhiều lần dư của phép chia trước, ta có $5^{32} \equiv 4$ (mod $7$) và

 

abc1b $\quad 5^{64}\equiv 2 $ (mod 7). Suy ra $5^{100} \equiv 2.4.2=16 $ (mod $7$). Do đó $5^{100} \equiv 2$ (mod $7$.)

Chia sẻ

About TS. Nguyễn Thái Sơn

TS. Nguyễn Thái Sơn
Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). /n Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). /n Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013). /n Giảng viên thỉnh giảng ĐHSP TP HCM.

Bài Viết Tương Tự

SỬ DỤNG MÁY TÍNH FX-880BTG GIẢI BÀI TOÁN DÃY SỐ TRUY HỒI TRONG ĐỀ THI HSG MTCT

Đề bài: Cho dãy số $(u_n)$ biết $u_1=1,u_2=2,u_3=3$ và $u_n=2u_{n-1}+3u_{n-2}-u_{n-3}+n^2 (n\geq 4)$. Tính (ghi kết …