Hôm nay chúng ta sẽ cùng nhau học về Định lý Fermat "nhỏ". Chúng ta sẽ thấy rằng định lý nhỏ Fermat rất là tiện dụng trong khi làm các phép tính toán modulo. Định lý này phát biểu như sau. Với mọi số nguyên tố $p$ và với mọi số nguyên $a$ không chia hết cho $p$ thì
$$ a^{p-1} = 1 \pmod{p} . $$
- Với $p=7$ và $a=3$, $$3^6 = 1 \pmod{7}$$
- Với $p=13$ và $a=2014$, $$2014^{12} = 1 \pmod{13}$$
- Với $p=29$ và $a=15$, $$15^{28} = 1 \pmod{29}$$
Giả sử như chúng ta cần tìm $3^{n} = ~?~ \pmod{7}$, trong đó $n$ là một con số lớn nào đó. Làm sao chúng ta có thể làm được?
The Định lý nhỏ Fermat, chúng ta biết rằng
$$3^6 = 1 \pmod{7} .$$
Để tính $3^n \pmod{7}$ cho một con số lớn $n$, chúng ta lấy $n$ rồi chia nó cho 6. Giả sử như chúng ta được kết quả $n = 6k+r$, trong đó số dư $r=0,1,2,3,4,5$, như vậy thì
$$3^{n} = 3^{6k+r} = (3^6)^k \times 3^r = 1^k \times 3^r = 3^r \pmod{7}$$
Vậy bằng cách sử dụng định lý nhỏ Fermat, chúng ta đã giản ước một con số lớn $3^{n}$ thành một con số nhỏ $3^r \pmod{7}$.
Ví dụ: Tìm $3^{2012}$ modulo $7$. Chúng ta lấy $2012$ rồi chia nó cho $6$, chúng ta có $2012 = 6 \times 335 + 2$, vậy thì
$$ 3^{2012} = 3^{6 \times 335 + 2} = (3^6)^{335} \times 3^2 = 1^{335} \times 3^2 \pmod{7}$$
Vì vậy, $3^{2012} = 3^2 = 9 = 2 \pmod{7}$.
Bây giờ chúng ta cùng nhau chứng minh Định lý nhỏ Fermat. Trước tiên để cho dễ hiểu chúng ta chứng minh cho trường hợp đặc biệt là $3^6 = 1 \pmod{7}$ và sau đó chúng ta sẽ chứng minh cho trường hợp tổng quát là $a^{p-1} = 1 \pmod{p}$.
Chúng ta thấy rằng
$$3 \times 1 = 3 \pmod{7}$$
$$3 \times 2 = 6 \pmod{7}$$
$$3 \times 3 = 2 \pmod{7}$$
$$3 \times 4 = 5 \pmod{7}$$
$$3 \times 5 = 1 \pmod{7}$$
$$3 \times 6 = 4 \pmod{7}$$
Nhân các đẳng thức này lại với nhau, chúng ta có
$$3^6 \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \pmod{7}$$
Vì vậy nên
$$(3^6 -1) \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 0 \pmod{7}$$
Đẳng thức này có nghĩa là gì? Có nghĩa là số $(3^6 -1) \times 1 \times 2 \times 3 \times 4 \times 5 \times 6$ cho hết cho 7. Chúng ta suy ra số $3^6 -1$ cũng chia hết cho 7. Tức là $3^6 = 1 \pmod{7}$. Vậy chúng ta đã chứng minh xong Định lý nhỏ Fermat cho trường hợp $p=7$ và $a=3$. Chứng minh cho trường hợp tổng quát cũng giống hệt như thế này.
Chứng minh Định lý nhỏ Fermat.
Giả sử rằng $p$ là số nguyên tố và $a$ không chia hết cho $p$. Xem xét các con số sau: $a$, $2a$, $3a$, $\dots$, $(p-1)a$. Chúng ta đặt
Giả sử rằng $p$ là số nguyên tố và $a$ không chia hết cho $p$. Xem xét các con số sau: $a$, $2a$, $3a$, $\dots$, $(p-1)a$. Chúng ta đặt
$$a = r_1 \pmod{p}$$
$$2a = r_2 \pmod{p}$$
$$3a = r_3 \pmod{p}$$
$$\dots$$
$$(p-1)a = r_{p-1} \pmod{p}$$
trong đó $r_1, r_2, r_3, \dots, r_{p-1}$ là các số nằm trong khoảng $[0,p-1]$.
Chúng ta nhận xét hai điều.
Điều thứ nhất, đó là $r_i \neq 0$. Tại sao vậy? Đó là vì nếu $r_i=0$ thì $ia = r_i = 0 \pmod{p}$. Cái này không thể nào xảy ra vì $a$ và $i$ không chia hết cho số nguyên tố $p$.
Điều thứ nhất, đó là $r_i \neq 0$. Tại sao vậy? Đó là vì nếu $r_i=0$ thì $ia = r_i = 0 \pmod{p}$. Cái này không thể nào xảy ra vì $a$ và $i$ không chia hết cho số nguyên tố $p$.
Điều nhận xét thứ hai là các số $r_1, r_2, r_3, \dots, r_{p-1}$ phải hoàn toàn khác nhau. Vì sao vậy? Nếu $r_i = r_j$ thì điều gì sẽ xảy ra? Nếu $r_i = r_j$ thì $ia = r_i = r_j = ja \pmod{p}$, và vì vậy $(i-j)a = 0 \pmod{p}$. Cái này cũng không thể xảy ra vì $a$ và $i-j$ đều không chia hết cho số nguyên tố $p$.
Như vậy chúng ta có $p-1$ con số $r_1, r_2, r_3, \dots, r_{p-1}$, tất cả chúng đều khác nhau và nằm trong khoảng $[1,p-1]$. Vậy thì $p-1$ con số này $r_1, r_2, r_3, \dots, r_{p-1}$ phải là một hoán vị của $p-1$ con số $1,2,3, \dots, p-1$. Do đó
$$r_1 \times r_2 \times r_3 \times \dots \times r_{p-1} = 1 \times 2 \times 3 \times \dots \times (p-1) .$$
Nhân các đẳng thức dưới đây lại với nhau
$$a = r_1 \pmod{p}$$
$$2a = r_2 \pmod{p}$$
$$3a = r_3 \pmod{p}$$
$$\dots$$
$$(p-1)a = r_{p-1} \pmod{p}$$
chúng ta có
$$a^{p-1} \times 1 \times 2 \times \dots \times (p-1) = r_1 \times r_2 \times \dots \times r_{p-1} = 1 \times 2 \times \dots \times (p-1) \pmod{p}$$
Vì vậy,
$$(a^{p-1} - 1) \times 1 \times 2 \times \dots \times (p-1) = 0 \pmod{p},$$
và do đó
$$a^{p-1} - 1 = 0 \pmod{p} .$$
Vậy, chúng ta đã chứng minh xong Định lý nhỏ Fermat rằng $a^{p-1} = 1 \pmod{p}. \blacksquare$
Một hệ quả của Định lý nhỏ Fermat là như sau. Bởi vì $a^{p-1} = 1 \pmod{p}$, cho nên nếu $x$ là số dương nhỏ nhất sao cho $a^x = 1 \pmod{p}$ thì $x$ bắt buộc phải là một ước số của $p-1$. Chẳng hạn như trong trường hợp $p=7$, theo Định lý nhỏ Fermat thì
$$1^6=2^6=3^6=4^6=5^6=6^6 = 1 \pmod{7},$$
số dương nhỏ nhất $x$ để cho $a^x = 1 \pmod{7}$ được liệt kê dưới đây
- Với $a=1$ thì $x=1$ $$1^1 = 1 \pmod{7}$$
- Với $a=2$ thì $x=3$ $$2^1 = 2, ~2^2 = 4, ~2^3 = 8 = 1 \pmod{7}$$
- Với $a=3$ thì $x=6$ $$3^1 = 3, ~3^2 = 9 = 2, ~3^3 = 6, ~3^4 = 18 = 4, ~3^5 = 12 = 5, ~3^6 = 15 = 1 \pmod{7}$$
- Với $a=4$ thì $x=3$ $$4^1 = 4, ~4^2 = 16 = 2, ~4^3 = 8 = 1 \pmod{7}$$
- Với $a=5$ thì $x=6$ $$5^1 = 5, ~5^2 = 25 = 4, ~5^3 = 20 = 6, ~5^4 = 30 = 2, ~5^5 = 10 = 3, ~5^6 = 15 = 1 \pmod{7}$$
- Với $a=6$ thì $x=2$ $$6^1 = 6, ~6^2 = 36 = 1 \pmod{7}$$
Chúng ta thấy rằng ở mỗi trường hợp, $1^1 = 2^3 = 3^6 = 4^3 = 5^6 = 6^2 = 1 \pmod{7}$, số mũ $x = 1, 3, 6, 3, 6, 2$ đều là ước số của $p-1=6$. Hình dưới đây miêu tả sự tuần hoàn của $a^n$ modulo 7.
 |
| sự tuần hoàn của $a^n$ modulo 7 |
Xin hẹn gặp lại các bạn ở kỳ cuối tại "modulo - Phần 6".
Bài tập về nhà.
1. Chứng minh rằng $2011^{2011^{2011}} + 2012^{2012^{2012}} + 2013^{2013^{2013}} + 2014^{2014^{2014}}$ chia hết cho 11.
2. Cho $p$ là một số nguyên tố và $a$ là số không chia hết cho $p$. Gọi $x$ là số nguyên dương nhỏ nhất sao cho $a^x = 1 \pmod{p}$. Chứng minh rằng $x$ là một ước số của $p-1$.
3. Lần lượt tính $2^n \pmod{11}$ cho $n=0,1,2,3,\dots$ rồi phát biểu tính tuần hoàn của $2^n$ modulo $11$.
Làm tương tự cho $3^n$, $4^n, \dots, 10^n$ modulo $11$.
Làm tương tự cho $3^n$, $4^n, \dots, 10^n$ modulo $11$.
