Định lý Euler

Định lý Euler được coi như là một mở rộng của định lý Fermat nhỏ. Đây là định lý “xương sống” của mật mã học hiện đại với đóng góp to lớn trong phương pháp mã hóa công khai RSA. Định lý được phát biểu như sau:

Nếu (a,n)=1, \forall a,n \in \mathbb{N} thì a^{\varphi (n)} \equiv 1 \pmod n với {\varphi (n)} = |\{k | k<n, (k,n)=1\}|

Thực ra, có rất nhiều cách chứng minh định lý trên, ví dụ một cách điển hình là thông qua lý thuyết nhóm. Tuy nhiên, xin giới thiệu một cách chứng minh rất đẹp bằng chứng minh sơ cấp như sau:

Gọi tập R=\{x_1, x_2, ..., x_{\varphi(n)}\} là các số dư của phép chia a:r. Như vậy, ta có: 0<x_i<n.

Xét ánh xạ

    \begin{align*}  f:R\longrightarrow aR \\ \mathbf{x} \longmapsto  f(\mathbf{x})=a \mathbf{x} \pmod n \end{align*}

Mệnh đề: \forall x_i, x_j \in R, x_i=x_j \iff ax_i \equiv ax_j \pmod n (bạn đọc tự chứng minh)

Theo mệnh đề trên, ta có f là đơn ánh mà lại có |R|=|aR|, như vậy f chính là một phép hoán vị trên tập R, suy ra:

\prod_{(i=1)}^{\varphi(n)}{a_i}=\prod_{(i=1)}^ {\varphi(n)}{b_i}, \forall a \in R, \forall b \in aR

Vì thế:

\prod_{(i=1)}^{\varphi(n)}  {x_i}=\prod_{(i=1)}^{\varphi(n)}  (ax_i)=a^ {\varphi(n)}  \prod_{(i=1)}^ {\varphi(n)} {x_i} \pmod n

Giản ước hai vế cho \prod_{(i=1)}^{\varphi(n)}  {x_i} ta có đpcm.

No Comments

Post A Comment