Bài 6: Định Lý Fermat Nhỏ Và Hàm Phi Euler - Blog Nam Phạm
Có thể bạn quan tâm
Trong bài này ta sẽ xem quan hệ của định lý nhỏ Fermat, định lý Euler,à hàm phi Euler và vai trò của chúng trong cơ sở toán học ngành mật mã.
- Định lý nhỏ Fermat
- Phát biểu định lý Fermat nhỏ
- Kiểm tra Fermat
- Khái niệm
- Thuật toán kiểm tra Fermat
- Chứng minh
- Ví dụ
- Bài tập
- Định lý Euler và Hàm phi Euler
- Định nghĩa
- Tính chất
- Ví dụ
- Bài tập
Định lý nhỏ Fermat
Nhà toán học người Pháp, Pierre de Fermat đã phát triển nhiều định lý mang tên mình trong đó có Định lý nhỏ Fermat về tính chất của số nguyên tố.
Phát biểu định lý Fermat nhỏ
Định lý nhỏ của Fermat (hay định lý Fermat nhỏ) khẳng định rằng nếu ${\displaystyle p}$ là một số nguyên tố, thì với số nguyên ${\displaystyle a}$ bất kỳ, ${\displaystyle a^{p}-a}$ sẽ chia hết cho ${\displaystyle p}$. Bằng kí hiệu đồng dư ta có: $${\displaystyle a^{p}\equiv a{\pmod {p}}\,\!}$$
Ví dụ: với ${\displaystyle a=3,\;p=5\implies 3^{5}-3=240\equiv 0{\pmod {5}}}$.
Một cách phát biểu khác của định lý như sau: nếu ${\displaystyle p}$ là số nguyên tố và ${\displaystyle a}$ là số nguyên không chia hết cho ${\displaystyle p}$, thì ${\displaystyle a^{p-1}-1}$ sẽ chia hết cho ${\displaystyle p}$. Nghĩa là: $${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\,!}$$
Ví dụ: với ${\displaystyle a=4,p=5\implies 4^{5-1}-1=255\equiv 0{\pmod {5}}}$
Cũng có một cách phát biểu khác là: Nếu ${\displaystyle p}$ là một số nguyên tố và ${\displaystyle a}$ là số nguyên không chia hết cho ${\displaystyle p}$, thì ${\displaystyle a^{p-1}-1}$ chia hết cho ${\displaystyle p}$.
Định lý Fermat nhỏ là cơ sở để kiểm tra tính nguyên tố theo xác suất trong kiểm tra Fermat và là một trong những kết quả nền tảng của lý thuyết số.
Kiểm tra Fermat
Kiểm tra Fermat là một thuật toán xác suất kiểm tra một số tự nhiên là hợp số hay là số nguyên tố.
Khái niệm
Định lý nhỏ Fermat phát biểu rằng nếu p là số nguyên tố và ${\displaystyle 1\leq a<p}$, thì ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.
Nếu ta muốn kiểm tra số n có là nguyên tố không, ta lấy ngẫu nhiên các số a’ và kiểm tra xem đẳng thức trên có đúng không. Nếu nó không đúng với một giá trị a nào đó thì n là hợp số. Nếu đẳng thức đúng với nhiều giá trị của a, ta có thể nói rằng n là số nguyên tố với xác suất nào đó, hay là một số giả nguyên tố (pseudoprime).
Có thể phép thử sẽ cho ta một kết quả sai.
- Số a mà ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ trong khi n là hợp số được gọi là một giả Fermat.
- Còn nếu có số a mà ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ thì a được xem như một bằng chứng Fermat chứng tỏ n là hợp số.
Thuật toán kiểm tra Fermat
Thuật toán Fermat kiểm tra số n có phải số nguyên tố hay kjong có thể viết như sau:
Inputs: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình kiểm tra Output: hợp số nếu n là hợp số, nếu không nguyên tố xác suất repeat k times: lấy a ngẫu nhiên trong [1, n − 1] if an − 1 mod n ≠ 1 then return composite return probably primeKhi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của thuật toán là O(k × log3n), ở đó 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.
Chứng minh
Fermat phát biểu định lý mà không chứng minh. Đã có nhiều chứng minh của định lý. Tuy nhiên định lý thường được chứng minh bằng cách dùng hệ quả của định lý Euler.
Bài chi tiết: https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem
Ví dụ
Xét ${\displaystyle 2^{7-1} {\pmod {7}}}$, ta thấy 7 là số nguyên tố và ${\displaystyle GCD(2, 7)=1}$, theo định lý nhỏ Fermat thì ${\displaystyle 2^{7-1} \equiv 1 {\pmod {7}}}$ . Kiểm tra lại ta có ${\displaystyle 2^{7-1} \equiv 2^{6} \equiv 64 \equiv 1 {\pmod {7}}}$
Bài tập
Tính nhanh
- 616 mod 17
- 1516 mod 17
- 95100 mod 101
Định lý Euler và Hàm phi Euler
Định nghĩa
Trong lý thuyết số, hàm số Euler của một số nguyên dương n được định nghĩa là số các số nguyên dương nhỏ hơn hoặc bằng n nguyên tố cùng nhau với n. Hàm Euler được ký hiệu bởi ${\displaystyle \phi (n)}$ hoặc ${\displaystyle \varphi (n)}$, do đó hàm được gọi làm hàm phi Euler.
Chẳng hạn, ${\displaystyle \phi (9)=6}$ vì có sáu số 1, 2, 4, 5, 7 và 8 là nguyên tố cùng nhau với 9.
Định lý Euler phát biểu rằng, nếu n là số nguyên dương bất kỳ và a nguyên tố cùng nhau với n, tức GCD(a,n) = 1, thì ${\displaystyle a^{\phi (n)}\equiv 1\mod n}$. Điều này suy ra từ Định lý Lagrange và từ việc a thuộc nhóm nhân modulo ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ nếu và chỉ nếu a nguyên tố cùng nhau với n.
Tính chất
Định lý Euler: Với mọi số nguyên dương n nguyên tố cùng nhau với a, ta có: ${\displaystyle a^{\phi (n)}\equiv 1\mod n}$ (*)
Định lý nhỏ Fermat chỉ ra rằng nếu p là một số nguyên tố thì: ${\displaystyle a^{p}\equiv a{\pmod {p}} \Leftrightarrow (a^p – a)\ \vdots\ p}$. Nếu ${\displaystyle GCD(a,p)=1}$ thì ${\displaystyle (a^{p-1} – 1)\ \vdots\ p \Leftrightarrow a^{p-1} \equiv 1\pmod{p}}$ (**)
Ta thấy định lý Fermat nhỏ là một trường hợp nhỏ của định lý Euler với n = p. Từ (*) và (**) có thể thấy rằng: Nếu n là số nguyên tố thì ${\displaystyle \phi (n)=n-1}$ [TC1]
Từ định nghĩa hàm phi Euler chúng ta có ${\displaystyle \phi (1)=1}$, và ${\displaystyle \phi (n)=(p-1)p^{k-1}}$ với n là lũy thừa bậc k của số nguyên tố p (${\displaystyle n=p^{k}}$) . Ngoài ra, ${\displaystyle \phi }$ là một hàm nhân tính; nếu m và n là nguyên tố cùng nhau thì ${\displaystyle \phi (m*n)=\phi (m)*\phi (n)}$ [TC2].
Từ tính chất 1 ta thấy ${\displaystyle n=p^k}$ thì ${\displaystyle \phi(p^k)=p^k-p^{k-1}}$ [TC3] với p là số nguyên tố
Xem thêm cách chứng minh các tính chất trên: https://www.tvhoang.com/articles/2017/11/fermat-euler
Ví dụ
1. Tính ${\displaystyle \phi(26)}$
Ta có ${\displaystyle \phi(26)=\phi(2*13)}$ mà ${\displaystyle GCD(2, 13)=1}$ nên theo TC2 có ${\displaystyle \phi(2*13) = \phi(2)*\phi(13)}$ Lại thấy 2 và 13 đều là số nguyên tố nên theo TC1 ${\displaystyle \phi(2)*\phi(13)=(2-1)*(3-1)=1*12=12}$
Vậy ${\displaystyle \phi(26)=12}$
2. Tính ${\displaystyle \phi(2^3)}$
Ta thấy 2 là số nguyên tố nên theo TC3 có ${\displaystyle \phi(2^3)=2^3-2^{3-1}=8-4=4}$
Vậy ${\displaystyle \phi(2^3)=4}$
3. Tính ${\displaystyle 7^{4} mod 10 }$
Ta có${\displaystyle \phi(10)=\phi(2*5)= \phi (2)*\phi (5) (TC2) = (2-1)*(5-1) (TC1) = 4}$ với 2 và 5 là các số nguyên tố.
${\displaystyle 7^4 mod 10 = 7^{\phi(10)} mod 10 = 1 mod 10 }$ (Theo định lý Euler)
Vậy ${\displaystyle 7^4 \equiv 1{\pmod{10}}}$
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:
- 95 mod 10
- 1012 mod 21
- 9190 mod 100
Tài liệu tham khảo:
- [1] https://vi.wikipedia.org/wiki/Định_lý_nhỏ_Fermat
- [2] https://vi.wikipedia.org/wiki/Kiểm_tra_Fermat
- [3] https://vi.wikipedia.org/wiki/Định_lý_Euler
- [4] https://vi.wikipedia.org/wiki/Hàm_phi_Euler
- [5] https://www.tvhoang.com/articles/2017/11/fermat-euler
Nam.Name.VN
Từ khóa » định Lý Ole
-
Định Lý Ơle Là Gì? - VietnamFinance
-
Định Lý Euler – Wikipedia Tiếng Việt
-
Định Lý Euler (hình Học) – Wikipedia Tiếng Việt
-
Định Lý Nhỏ Fermat Và Phi Hàm Euler - Thien Hoang
-
Định Lý Euler - Wiki Tiếng Việt - Du Học Trung Quốc
-
Định Lí Euler - Tìm Số Dư Phép Chia ( Ôn Thi Hsg Toán Máy Tính )
-
4 Hàm Euler, định Lý Euler Và định Lý Fermat - Tài Liệu Text - 123doc
-
[Toán 8] Định Lý Ơ-le | Cộng đồng Học Sinh Việt Nam - HOCMAI Forum
-
Tài Liệu định Lý Euler - Xemtailieu
-
Định Lý Euler - Wiki Là Gì
-
Định Lý Fermat Nhỏ-Định Lý Euler - Các Bài Toán Và Vấn đề Về Số Học
-
Định Lý Fermat Về Tổng Của Hai Số Chính Phương - Wikiwand