Định Lý Nhỏ Fermat: Nền Tảng Toán Học Cho Mật Mã Học Và Kiểm Tra Tính Nguyên Tố

by Thầy Đông · January 8, 2026

Rate this post

Trong thế giới của toán học, một số định lý tuy có vẻ “nhỏ” nhưng lại mang trong mình sức ảnh hưởng to lớn, đặt nền móng cho nhiều lĩnh vực phức tạp. Định lý nhỏ Fermat là một trong số đó. Phát biểu bởi nhà toán học lỗi lạc Pierre de Fermat, định lý này không chỉ làm phong phú thêm lý thuyết số mà còn trở thành công cụ thiết yếu trong kiểm tra tính nguyên tố và là một phần quan trọng trong cơ sở toán học của ngành mật mã học hiện đại.

Đề Bài

Trong bài này ta sẽ xem quan hệ của định lý nhỏ Fermat, định lý Euler và hàm phi Euler và vai trò của chúng trong cơ sở toán học ngành mật mã.

Phân Tích Yêu Cầu

Bài viết yêu cầu làm rõ mối liên hệ giữa ba khái niệm quan trọng trong lý thuyết số: Định lý nhỏ Fermat, Định lý Euler và Hàm phi Euler. Mục tiêu là trình bày vai trò và ứng dụng của chúng, đặc biệt là trong lĩnh vực mật mã học và kiểm tra tính nguyên tố. Chúng ta cần cung cấp định nghĩa, phát biểu chính xác, chứng minh (hoặc phương pháp chứng minh), các ví dụ minh họa cụ thể và bài tập áp dụng để người đọc có thể hiểu sâu sắc.

Kiến Thức/Nền Tảng Cần Dùng

Để hiểu rõ Định lý nhỏ Fermat, chúng ta cần nắm vững các khái niệm cơ bản về số nguyên tố, đồng dư thức và tính chất của chúng.

Số Nguyên Tố

Một số tự nhiên lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có hai ước số dương phân biệt là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Ví dụ, 2, 3, 5, 7, 11 là các số nguyên tố.

Đồng Dư Thức

Trong lý thuyết số, đồng dư thức là một khái niệm cho biết hai số có cùng số dư khi chia cho một số nguyên khác. Ký hiệu là a ≡ b (mod m), đọc là “a đồng dư với b theo modulo m”. Điều này có nghĩa là m chia hết hiệu a - b, hay a - b = km với k là một số nguyên.

Ví dụ, 7 ≡ 2 (mod 5) vì 7 - 2 = 5, và 5 chia hết cho 5.

Định Lý Nhỏ Fermat

Định lý nhỏ Fermat là một kết quả nền tảng trong lý thuyết số, phát biểu mối quan hệ giữa số nguyên tố và phép lũy thừa. Định lý này có hai cách phát biểu tương đương, đều rất quan trọng.

Cách phát biểu 1: Nếu $p$ là một số nguyên tố, thì với mọi số nguyên $a$ bất kỳ, biểu thức $a^p - a$ sẽ chia hết cho $p$. Chúng ta có thể viết điều này dưới dạng đồng dư thức là:
$a^p equiv a pmod{p}$

Ví dụ: Xét $a=3$ và $p=5$ . Ta có $3^5 - 3 = 243 - 3 = 240$ . Số 240 chia hết cho 5, do đó $3^5 equiv 3 pmod{5}$ .

Cách phát biểu 2: Nếu $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$ (tức là ước chung lớn nhất của $a$ và $p$ là 1, ký hiệu $GCD(a, p) = 1$ ), thì $a^{p-1} - 1$ sẽ chia hết cho $p$. Dưới dạng đồng dư thức là:
$a^{p-1} equiv 1 pmod{p}$

Ví dụ: Xét $a=4$ và $p=5$ . Ta thấy $GCD(4, 5) = 1$ . Theo định lý, $4^{5-1} equiv 1 pmod{5}$ . Tính toán cho thấy $4^4 = 256$ . Khi chia 256 cho 5, ta được số dư là 1. Như vậy, $256 equiv 1 pmod{5}$ .

Hai cách phát biểu này có mối liên hệ chặt chẽ. Nếu $p$ không chia hết $a$, thì $a^p equiv a pmod{p}$ tương đương với $a^p - a equiv 0 pmod{p}$ . Chia cả hai vế cho $a$ (điều này hợp lệ vì $GCD(a,p)=1$ ), ta được $a^{p-1} equiv 1 pmod{p}$ . Nếu $p$ chia hết $a$, thì $a equiv 0 pmod{p}$ , do đó $a^p equiv 0^p equiv 0 pmod{p}$ (với $p \ge 1$ ), và $a equiv 0 pmod{p}$ . Suy ra $a^p equiv a pmod{p}$ vẫn đúng.

Kiểm Tra Tính Nguyên Tố Theo Xác Suất (Kiểm Tra Fermat)

Một trong những ứng dụng quan trọng nhất của Định lý nhỏ Fermat là trong việc phát triển các thuật toán kiểm tra tính nguyên tố hiệu quả, đặc biệt là kiểm tra Fermat. Thay vì phải thử chia một số lớn $n$ cho tất cả các số nhỏ hơn nó, thuật toán này dựa trên việc kiểm tra tính đúng đắn của hệ thức đồng dư.

Khái niệm: Nếu $n$ là một số nguyên tố, thì với mọi số nguyên $a$ sao cho $1 \le a < n[/katex], ta luôn có [katex]a^{n-1} equiv 1 pmod{n}[/katex]. <strong>Định lý nhỏ Fermat</strong> phát biểu điều này. Tuy nhiên, điều ngược lại không phải lúc nào cũng đúng: một hợp số $n$ có thể thỏa mãn [katex]a^{n-1} equiv 1 pmod{n}$ với một số giá trị $a$.

Khi muốn kiểm tra xem một số tự nhiên $n$ có phải là số nguyên tố hay không, ta chọn ngẫu nhiên một số $a$ trong khoảng từ 1 đến $n-1$ . Sau đó, ta tính giá trị của $a^{n-1} pmod{n}$ .

Nếu $a^{n-1} notequiv 1 pmod{n}$ , thì chắc chắn $n$ là một hợp số. Số $a$ này được gọi là "bằng chứng Fermat" cho thấy $n$ là hợp số.
Nếu $a^{n-1} equiv 1 pmod{n}$ , thì $n$ có thể là số nguyên tố, hoặc $n$ là một hợp số "giả nguyên tố" (pseudoprime) đối với cơ số $a$.

Để tăng độ tin cậy, thuật toán kiểm tra Fermat lặp lại quá trình này với nhiều giá trị $a$ ngẫu nhiên khác nhau. Nếu hệ thức đồng dư đúng với tất cả các giá trị $a$ đã chọn, ta kết luận $n$ là số nguyên tố với một xác suất cao. Nếu chỉ cần một giá trị $a$ duy nhất mà hệ thức sai, ta khẳng định ngay $n$ là hợp số.

Thuật toán kiểm tra Fermat:

<strong>Đầu vào</strong>: n: số cần kiểm tra tính nguyên tố; k: số lần lặp kiểm tra
<strong>Đầu ra</strong>: 'Hợp số' nếu n là hợp số, 'Nguyên tố xác suất' nếu không chắc chắn

repeat k times:
  Chọn ngẫu nhiên một số a sao cho 1 ≤ a < n
  Tính giá trị b = a^(n-1) mod n
  if b ≠ 1 then
    return 'Hợp số'
return 'Nguyên tố xác suất'

Khi sử dụng thuật toán tính nhanh luỹ thừa theo mô-đun (như thuật toán luỹ thừa theo mô-đun nhị phân), thời gian thực thi của thuật toán này là khoảng $O(k \times (log n)^3)$ , trong đó $k$ là số lần kiểm tra với mỗi số $a$ ngẫu nhiên, và $n$ là giá trị ta muốn kiểm tra.

Lưu ý: Một số hợp số, được gọi là số Carmichael, thỏa mãn $a^{n-1} equiv 1 pmod{n}$ với mọi $a$ nguyên tố cùng nhau với $n$. Các số này có thể đánh lừa kiểm tra Fermat cơ bản. Tuy nhiên, các thuật toán kiểm tra nguyên tố hiện đại hơn, như kiểm tra Miller-Rabin, khắc phục được nhược điểm này bằng cách sử dụng các điều kiện bổ sung dựa trên tính chất của căn bậc hai của 1 theo modulo $n$.

Chứng Minh Định Lý Nhỏ Fermat

Fermat đã phát biểu định lý này mà không đưa ra một chứng minh đầy đủ. Tuy nhiên, nhiều nhà toán học sau đó đã chứng minh nó, trong đó có Gottfried Wilhelm Leibniz và Leonhard Euler. Một trong những cách chứng minh phổ biến và dễ hiểu nhất là sử dụng khái niệm nhóm và các tính chất của nó, hoặc thông qua hệ quả trực tiếp từ Định lý Euler.

Chứng minh dựa trên Định lý Euler:
Định lý Euler là một mở rộng của Định lý nhỏ Fermat. Nếu chúng ta hiểu Định lý Euler, Định lý nhỏ Fermat sẽ trở nên hiển nhiên.

Định Lý Euler Và Hàm Phi Euler

Định Nghĩa Hàm Phi Euler

Trong lý thuyết số, hàm số Euler, thường được ký hiệu là $phi(n)$ hoặc $varphi(n)$, là một hàm số định nghĩa trên tập các số nguyên dương. Với mỗi số nguyên dương $n$, $phi(n)$ đếm số lượng các số nguyên dương $k$ sao cho $1 \le k \le n$ và ước chung lớn nhất của $k$ và $n$ bằng 1 ( $GCD(k, n) = 1$ ). Các số $k$ thỏa mãn điều kiện này được gọi là nguyên tố cùng nhau với $n$.

Ví dụ: Tính $phi(9)$. Các số nguyên dương nhỏ hơn hoặc bằng 9 là 1, 2, 3, 4, 5, 6, 7, 8, 9. Chúng ta cần tìm các số $k$ trong danh sách này sao cho $GCD(k, 9) = 1$ .

$GCD(1, 9) = 1$
$GCD(2, 9) = 1$
$GCD(3, 9) = 3$ (không phải 1)
$GCD(4, 9) = 1$
$GCD(5, 9) = 1$
$GCD(6, 9) = 3$ (không phải 1)
$GCD(7, 9) = 1$
$GCD(8, 9) = 1$
$GCD(9, 9) = 9$ (không phải 1)
Có 6 số là 1, 2, 4, 5, 7, 8. Vậy, $phi(9) = 6$ .

Định Lý Euler

Định lý Euler là một tuyên bố tổng quát hơn về đồng dư thức, bao gồm cả Định lý nhỏ Fermat như một trường hợp đặc biệt. Định lý phát biểu rằng: Nếu $n$ là một số nguyên dương bất kỳ và $a$ là một số nguyên nguyên tố cùng nhau với $n$ (tức là $GCD(a, n) = 1$ ), thì $a^{phi(n)} equiv 1 pmod{n}$ .

Điều này có ý nghĩa quan trọng vì nó cho phép chúng ta tính toán các lũy thừa lớn theo mô-đun một cách hiệu quả.

Tính Chất Quan Trọng Của Hàm Phi Euler

Hàm phi Euler có nhiều tính chất hữu ích, giúp chúng ta tính toán nó cho các số khác nhau và chứng minh các định lý liên quan.

Trường hợp số nguyên tố: Nếu $p$ là một số nguyên tố, thì mọi số nguyên dương từ 1 đến $p-1$ đều nguyên tố cùng nhau với $p$. Do đó, $phi(p) = p-1$ . Đây là lý do tại sao Định lý nhỏ Fermat là trường hợp đặc biệt của Định lý Euler: thay $n=p$ (số nguyên tố) vào Định lý Euler, ta có $a^{phi(p)} equiv 1 pmod{p}$ . Vì $phi(p) = p-1$ , ta thu được $a^{p-1} equiv 1 pmod{p}$ , chính là cách phát biểu thứ hai của Định lý nhỏ Fermat cho trường hợp $GCD(a,p)=1$ .
$phi(p) = p-1 quad \text{(với p là số nguyên tố)}$
Trường hợp lũy thừa của số nguyên tố: Nếu $p$ là số nguyên tố và $k$ là một số nguyên dương, thì $phi(p^k) = p^k - p^{k-1}$ . Số lượng các số không nguyên tố cùng nhau với $p^k$ và nhỏ hơn hoặc bằng $p^k$ là các bội của $p$: $p, 2p, 3p, dots, p^{k-1} \times p = p^k$ . Có tất cả $p^{k-1}$ bội như vậy.
$phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p}) quad \text{(với p là số nguyên tố, k \ge 1)}$
Tính nhân tính: Hàm $phi$ là một hàm nhân tính. Điều này có nghĩa là nếu $m$ và $n$ là hai số nguyên dương nguyên tố cùng nhau ( $GCD(m, n) = 1$ ), thì $phi(mn) = phi(m)phi(n)$ .
$phi(m \times n) = phi(m) \times phi(n) quad \text{(nếu GCD(m, n) = 1)}$
Tính toán tổng quát: Từ các tính chất trên, chúng ta có thể tính $phi(n)$ cho bất kỳ số nguyên dương $n$ nào nếu biết phân tích thừa số nguyên tố của $n$. Nếu $n = p_1^{k_1} p_2^{k_2} cdots p_r^{k_r}$ là phân tích thừa số nguyên tố của $n$, thì:
$phi(n) = phi(p_1^{k_1}) phi(p_2^{k_2}) cdots phi(p_r^{k_r}) = p_1^{k_1}(1 - \frac{1}{p_1}) p_2^{k_2}(1 - \frac{1}{p_2}) cdots p_r^{k_r}(1 - \frac{1}{p<em>r})$
$phi(n) = n prod</em>{i=1}^{r} (1 - \frac{1}{p_i})$

Ví Dụ Minh Họa

1. Tính $phi(26)$:
Phân tích 26 ra thừa số nguyên tố: $26 = 2 \times 13$ .
Vì 2 và 13 là hai số nguyên tố khác nhau, chúng nguyên tố cùng nhau ( $GCD(2, 13) = 1$ ).
Áp dụng tính chất nhân tính: $phi(26) = phi(2) \times phi(13)$ .
Vì 2 và 13 là số nguyên tố, ta có $phi(2) = 2-1 = 1$ và $phi(13) = 13-1 = 12$ .
Vậy, $phi(26) = 1 \times 12 = 12$ .

Có 12 số nguyên dương nhỏ hơn hoặc bằng 26 nguyên tố cùng nhau với 26. Đó là: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.

2. Tính $phi(8)$:
Số 8 có thể viết dưới dạng lũy thừa của số nguyên tố: $8 = 2^3$ .
Áp dụng công thức $phi(p^k) = p^k - p^{k-1}$ :
$phi(8) = phi(2^3) = 2^3 - 2^{3-1} = 8 - 2^2 = 8 - 4 = 4$ .
Các số nguyên tố cùng nhau với 8 là 1, 3, 5, 7. Có 4 số.

3. Tính $7^4 pmod{10}$ :
Trước tiên, ta tính $phi(10)$. Phân tích 10 ra thừa số nguyên tố: $10 = 2 \times 5$ .
Vì 2 và 5 nguyên tố cùng nhau, $phi(10) = phi(2) \times phi(5) = (2-1) \times (5-1) = 1 \times 4 = 4$ .
Bây giờ, áp dụng Định lý Euler: $a^{phi(n)} equiv 1 pmod{n}$ với $GCD(a, n) = 1$ .
Ở đây, $a=7$ và $n=10$ . $GCD(7, 10) = 1$ , và $phi(10) = 4$ .
Vậy, $7^{phi(10)} equiv 7^4 equiv 1 pmod{10}$ .
Kết quả là $7^4 equiv 1 pmod{10}$ .

Vai Trò Trong Mật Mã Học

Định lý nhỏ Fermat và Định lý Euler cùng với hàm phi Euler tạo thành nền tảng toán học cho nhiều thuật toán mật mã hiện đại, nổi bật nhất là hệ mã RSA.

Hệ mã RSA dựa trên hai nguyên lý chính:

Độ khó của việc phân tích thừa số nguyên tố: Rất khó để tìm các thừa số nguyên tố của một số nguyên dương rất lớn.
Định lý Euler và tính chất của hàm phi Euler: Cho phép xây dựng các cặp khóa mã hóa và giải mã một cách hiệu quả.

Cụ thể, trong RSA, một khóa công khai và một khóa bí mật được tạo ra. Khóa công khai bao gồm một số $n$ (là tích của hai số nguyên tố lớn $p$ và $q$) và một số mũ $e$. Khóa bí mật bao gồm số $n$ và một số mũ khác là $d$. Mối quan hệ giữa $e$ và $d$ được thiết lập dựa trên Định lý Euler.

Để mã hóa một thông điệp $M$ thành bản mã $C$, ta tính $C = M^e pmod{n}$ .
Để giải mã bản mã $C$ về thông điệp gốc $M$, ta tính $M = C^d pmod{n}$ .

Việc chứng minh tại sao phép giải mã này hoạt động đòi hỏi sử dụng Định lý Euler. Cụ thể, ta cần chứng minh rằng $(M^e)^d equiv M pmod{n}$ . Điều này có thể được chứng minh bằng cách xét hai trường hợp: $GCD(M, n) = 1$ và $GCD(M, n) \ne 1$ . Khi $GCD(M, n) = 1$ , ta dùng Định lý Euler trực tiếp. Khi $GCD(M, n) \ne 1$ , ta cần sử dụng các tính chất bổ sung và Định lý nhỏ Fermat (hoặc Định lý Euler mở rộng).

Quan trọng hơn, số lượng các cặp $(e, d)$ có thể sử dụng là do tính chất của hàm $phi(n)$. Trong thuật toán RSA, ta chọn $e$ sao cho $GCD(e, phi(n)) = 1$ , và $d$ là nghịch đảo của $e$ theo modulo $phi(n)$, tức là $ed equiv 1 pmod{phi(n)}$ . Điều này có nghĩa là $ed = k phi(n) + 1$ cho một số nguyên $k$. Khi đó, $M^{ed} = M^{k phi(n) + 1} = (M^{phi(n)})^k \times M$ . Nếu $GCD(M, n) = 1$ , theo Định lý Euler, $M^{phi(n)} equiv 1 pmod{n}$ . Do đó, $M^{ed} equiv 1^k \times M equiv M pmod{n}$ .

Sự phức tạp của việc tìm phân tích thừa số nguyên tố của $n$ khi $n$ rất lớn chính là điều làm cho RSA trở nên an toàn.

Ví Dụ Bài Tập

Áp dụng Định lý Euler và hàm phi Euler cùng các tính chất để tính:

1. Tính $9^5 pmod{10}$ :
Ta cần tính $phi(10)$. Như đã tính ở trên, $phi(10) = 4$ .
$GCD(9, 10) = 1$ .
Theo Định lý Euler: $9^{phi(10)} equiv 1 pmod{10}$ .
$9^4 equiv 1 pmod{10}$ .
Ta cần tính $9^5 pmod{10}$ .
$9^5 = 9^4 \times 9^1 equiv 1 \times 9 pmod{10} equiv 9 pmod{10}$ .
Vậy, $9^5 equiv 9 pmod{10}$ .

2. Tính $10^{12} pmod{21}$ :
Ta cần tính $phi(21)$. Phân tích 21 ra thừa số nguyên tố: $21 = 3 \times 7$ .
$GCD(3, 7) = 1$ .
$phi(21) = phi(3) \times phi(7) = (3-1) \times (7-1) = 2 \times 6 = 12$ .
Ta có $GCD(10, 21) = 1$ .
Theo Định lý Euler: $10^{phi(21)} equiv 1 pmod{21}$ .
$10^{12} equiv 1 pmod{21}$ .
Vậy, $10^{12} equiv 1 pmod{21}$ .

3. Tính $9^{190} pmod{100}$ :
Ta cần tính $phi(100)$. Phân tích 100 ra thừa số nguyên tố: $100 = 10^2 = (2 \times 5)^2 = 2^2 \times 5^2$ .
$phi(100) = phi(2^2) \times phi(5^2)$ .
$phi(2^2) = 2^2 - 2^{2-1} = 4 - 2^1 = 4 - 2 = 2$ .
$phi(5^2) = 5^2 - 5^{2-1} = 25 - 5^1 = 25 - 5 = 20$ .
Vậy, $phi(100) = 2 \times 20 = 40$ .
Ta có $GCD(9, 100) = 1$ .
Theo Định lý Euler: $9^{phi(100)} equiv 1 pmod{100}$ .
$9^{40} equiv 1 pmod{100}$ .
Ta cần tính $9^{190} pmod{100}$ . Ta chia 190 cho 40: $190 = 4 \times 40 + 30$ .
$9^{190} = 9^{4 \times 40 + 30} = (9^{40})^4 \times 9^{30}$ .
$9^{190} equiv (1)^4 \times 9^{30} pmod{100} equiv 9^{30} pmod{100}$ .
Bây giờ ta cần tính $9^{30} pmod{100}$ .
Ta có thể tính từng bước nhỏ hơn:
$9^1 = 9$
$9^2 = 81$
$9^3 = 729 equiv 29 pmod{100}$
$9^4 equiv 9 \times 29 = 261 equiv 61 pmod{100}$
$9^5 equiv 9 \times 61 = 549 equiv 49 pmod{100}$
$9^{10} equiv 49^2 = 2401 equiv 1 pmod{100}$
Ồ, một kết quả thú vị: $9^{10} equiv 1 pmod{100}$ .
Vậy ta có thể dùng kết quả này:
$9^{30} = (9^{10})^3 equiv 1^3 pmod{100} equiv 1 pmod{100}$ .
Vậy, $9^{190} equiv 1 pmod{100}$ .

Lưu ý về sự khác biệt: Nếu ta tính $a^{n-1} pmod{n}$ trong kiểm tra Fermat, với $n=100$ (hợp số) và $a=9$ , ta có $9^{99} pmod{100}$ .
$9^{99} = 9^{90} \times 9^9 = (9^{10})^9 \times 9^9 equiv 1^9 \times 9^9 equiv 9^9 pmod{100}$ .
$9^9 = 9^{10} / 9 equiv 1 / 9 pmod{100}$ .
Để tìm $1/9 pmod{100}$ , ta tìm $x$ sao cho $9x equiv 1 pmod{100}$ .
$9 \times 11 = 99 equiv -1 pmod{100}$ .
$9 \times (-11) equiv 1 pmod{100}$ .
$-11 equiv 89 pmod{100}$ .
Vậy $9^{99} equiv 89 pmod{100}$ .
Vì $9^{99} notequiv 1 pmod{100}$ , nên 9 là bằng chứng Fermat cho thấy 100 là hợp số.

Tóm Lại:
Định lý nhỏ Fermat cung cấp một công cụ mạnh mẽ để làm việc với số nguyên tố. Định lý Euler mở rộng điều này cho mọi số nguyên, và hàm phi Euler là chìa khóa để tính toán các giới hạn trong các phép toán theo mô-đun. Cả ba khái niệm này là trụ cột không thể thiếu trong toán học hiện đại, đặc biệt là trong lĩnh vực an ninh thông tin và mật mã học. Hiểu sâu sắc về chúng không chỉ giúp giải quyết các bài toán lý thuyết số phức tạp mà còn mở ra cánh cửa ứng dụng vào thế giới thực.

Ngày chỉnh sửa nội dung mới nhất January 8, 2026 by Thầy Đông

Thầy Đông

Thầy Đông – Giảng viên Đại học Công nghiệp Hà Nội, giáo viên luyện thi THPT
Thầy Đông bắt đầu sự nghiệp tại một trường THPT ở quê nhà, sau đó trúng tuyển giảng viên Đại học Công nghiệp Hà Nội nhờ chuyên môn vững và kinh nghiệm giảng dạy thực tế. Với nhiều năm đồng hành cùng học sinh, thầy được biết đến bởi phong cách giảng dạy rõ ràng, dễ hiểu và gần gũi. Hiện thầy giảng dạy tại dehocsinhgioi, tiếp tục truyền cảm hứng học tập cho học sinh cấp 3 thông qua các bài giảng súc tích, thực tiễn và giàu nhiệt huyết.