Định lýĐã chứng minh

Định lý Euler (hàm phi)

Phát biểu

Nếu $\gcd(a,n)=1$ , thì $a^{\varphi(n)}\equiv 1 \pmod{n}$ , trong đó $\varphi(n)$ (hàm phi Euler) đếm số các số nguyên trong $\{1,\dots,n\}$ nguyên tố cùng nhau với $n$ .

Vì sao đúng?

Định lý này tổng quát hóa định lý Fermat nhỏ từ mô đun nguyên tố sang mô đun bất kỳ: cùng lập luận hoán vị áp dụng trên $\varphi(n)$ thặng dư khả nghịch theo mô đun $n$ , thay vì trên toàn bộ $1,\dots,p-1$ .

Phác thảo chứng minh

Gọi $R=\{r_1,\dots,r_{\varphi(n)}\}$ là các thặng dư theo mô đun $n$ nguyên tố cùng $n$ . Phép nhân với $a$ hoán vị $R$ , vì $\gcd(a,n)=1$ . Nhân tất cả các phần tử của $R$ trước và sau phép hoán vị này ta được $a^{\varphi(n)}\prod r_i \equiv \prod r_i \pmod n$ ; khử $\prod r_i$ (khả nghịch theo mô đun $n$ ) cho ra $a^{\varphi(n)}\equiv1\pmod n$ .

Người phát biểu

Leonhard Euler

Người chứng minh

chứng minh năm 1763Leonhard Euler

Chủ đề chứa định lý này

Đồng dư và số học modulo Định lý Fermat nhỏ, định lý Euler

Định lý liên quan

Định lý Fermat nhỏ

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Leonhard Euler (1763). Theoremata arithmetica nova methodo demonstrata
G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers · DOI:10.1093/oso/9780199219858.001.0001