Định lý Wilson và áp dụng
- 18/11/2022
- 611 lượt xem
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}}$.
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à
$\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$.)