Định Lý Euler – Wikipedia Tiếng Việt

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. (Tìm hiểu cách thức và thời điểm xóa thông báo này)

Bài viết hoặc đoạn này cần được wiki hóa để đáp ứng tiêu chuẩn quy cách định dạng và văn phong của Wikipedia. Xin hãy giúp sửa bài viết này bằng cách thêm bớt liên kết hoặc cải thiện bố cục và cách trình bày bài.

Định lý Euler phát biểu rằng nếu n (n thuộc N*) là số nguyên dương bất kỳ và a là số nguyên tố cùng nhau với n, thì

a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}

trong đó φ(n) là ký hiệu của phi hàm Euler đếm số các số nguyên giữa 1 và n nguyên tố cùng nhau với n. Đây là tổng quát hóa của định lý nhỏ Fermat vì nếu n = p là số nguyên tố thì φ(p) = p − 1.

Định lý này có thể được sử dụng để dễ dàng giản ước với module n rất lớn. Ví dụ tìm chữ số tận cùng của số 7222.

7222 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 49 ≡ 9 (mod 10). Vậy 7222 có chữ số tận cùng là 9.

Định lý Euler cũng là định lý cơ bản của các hệ thống mã hóa RSA tuy nhiên, việc sử dụng định lý Euler là không đủ (và không cần thiết) để chứng nhận tính hợp lệ của mã hóa RSA. Trong RSA, kết quả ròng của lần đầu tiên mã hóa tin nhắn văn bản gốc, sau đó giải mã nó, sẽ tăng số mũ của một số đầu vào lớn bằng k φ ( n ) + 1 {\displaystyle k\varphi (n)+1} , đối với một số nguyên dương k {\displaystyle k} . Trong trường hợp số ban đầu tương đối nguyên tố với n {\displaystyle n} , định lý Euler sẽ đảm bảo rằng số đầu ra được giải mã bằng với số đầu vào ban đầu, trả lại bản văn bản gốc. Tuy nhiên, vì n {\displaystyle n} là sản phẩm của hai số nguyên tố riêng biệt, p {\displaystyle p} và q {\displaystyle q} , khi số được mã hóa là bội số của p {\displaystyle p} hoặc q {\displaystyle q} , Định lý Euler không áp dụng và cần sử dụng quy định duy nhất của Định lý phần dư Trung Quốc. Định lý phần dư Trung Quốc cũng đủ trong trường hợp số tương đối nguyên tố với n {\displaystyle n} , và do đó định lý Euler không đủ và cũng không cần thiết.

Chứng minh

Gọi a 1 , a 2 , ⋯ , a φ ( n ) {\displaystyle a_{1},a_{2},\cdots ,a_{\varphi (n)}} là các số nguyên dương nhỏ hơn n {\displaystyle n} và nguyên tố cùng nhau với n {\displaystyle n} . Với mọi 2 số phân biệt i , j ∈ { 1 , 2 , ⋯ , φ ( n ) } {\displaystyle i,j\in \{1,2,\cdots ,\varphi (n)\}} : ( a i , n ) = ( a j , n ) = 1 ⇒ ( a a i , n ) = ( a a j , n ) = 1 ; a a i ≢ a a j ( mod n ) {\displaystyle (a_{i},n)=(a_{j},n)=1\Rightarrow (aa_{i},n)=(aa_{j},n)=1;aa_{i}\not \equiv aa_{j}{\pmod {n}}} . Do vậy, a a 1 , a a 2 , ⋯ , a a φ ( n ) {\displaystyle aa_{1},aa_{2},\cdots ,aa_{\varphi (n)}} là một hoán vị theo mô-đun n {\displaystyle n} của a 1 , a 2 , ⋯ , a φ ( n ) {\displaystyle a_{1},a_{2},\cdots ,a_{\varphi (n)}} .

Suy ra a 1 a 2 ⋯ a φ ( n ) ≡ ( a a 1 ) ( a a 2 ) ⋯ ( a a φ ( n ) ) ≡ a φ ( n ) a 1 a 2 ⋯ a φ ( n ) ( mod n ) {\displaystyle a_{1}a_{2}\cdots a_{\varphi (n)}\equiv (aa_{1})(aa_{2})\cdots (aa_{\varphi (n)})\equiv a^{\varphi (n)}a_{1}a_{2}\cdots a_{\varphi (n)}{\pmod {n}}} .

Giản ước đồng dư thức, a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} .

Định lý đã được chứng minh

Tham khảo