Bài 6: Định Lý Fermat Nhỏ Và Hàm Phi Euler - Blog Nam Phạ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ã.

1. Định lý nhỏ Fermat
   1. Phát biểu định lý Fermat nhỏ
   2. Kiểm tra Fermat
      1. Khái niệm
      2. Thuật toán kiểm tra Fermat
   3. Chứng minh
   4. Ví dụ
   5. Bài tập
2. Định lý Euler và Hàm phi Euler
   1. Định nghĩa
   2. Tính chất
   3. Ví dụ
   4. 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 prime

Khi 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

1. 616 mod 17
2. 1516 mod 17
3. 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