5 NOV 2017 • 3 mins read Hàm phi ((varphi)) Euler của một trong những nguyên dương (n) được tư tưởng là số những số nguyên dương (m) không vượt quá (n) thế nào cho ((m,n)=1). Ví dụ, số 10 gồm 4 số nguyên dương ko vượt thừa 10 và nguyên tố với mọi người trong nhà với 10, sẽ là 1, 3, 7, 9. Như vậy, (varphi(10)=4). nếu (n=p) là số nguyên tố, hay thấy (varphi(p)=p-1). Giả dụ (n=p^k) thì (varphi(p^k)=p^k-p^k-1). Chứng minh: Có tổng cộng (p^k) số nguyên dương đề xuất xét. Trong những đó, các số (m) có ước chung lớn nhất với (n) không giống 1 sẽ sở hữu được dạng (m=px), với (x) là bất kể số nguyên dương nào đảm bảo an toàn (pxleq p^k), do vậy có tổng số (p^k-1) quý hiếm (x) như thế. Suy ra số những số nguyên tố bên nhau với (n) là (p^k-p^k-1). (QED) giả dụ (n=p_1p_2) (với (p_1 eq p_2)) thì (varphi(p_1p_2) = varphi(p_1) imesvarphi(p_2)). Chứng minh: Có tổng cộng (p_1p_2) số nguyên dương phải xét. Trong số đó, những số (m) có ước chung lớn nhất với (n) khác 1 sẽ sở hữu được dạng (m=p_1x) hoặc (m=p_2x) làm sao để cho (mleq n). Trong trường đúng theo đầu, (x) trải lâu năm từ (1) mang lại (p_2). Trong trường hòa hợp sau, (x) trải dài từ (1) cho (p_1). Mặc dù nhiên, bao gồm hai quý giá (m) được đếm hai lần, đó là (p_1p_2). Bởi thế có tổng cộng (p_1+p_2-1) số ko nguyên tố cùng mọi người trong nhà với (n). Như vậy: nếu như (n=ab) (với (a,b) nguyên tố thuộc nhau) thì (varphi(ab)=varphi(a) imesvarphi(b)) (trường hợp tổng quát hơn của định lý trước). Chứng minh: tất cả các số nguyên dương (m) không vượt vượt (n=ab) gồm dạng (m=aq+r) với (q,r) là những số nguyên theo lần lượt nằm trong vòng (<0,b-1>) với (<1,a>). Công việc cần có tác dụng là đếm xem tất cả bao nhiêu cặp quý giá ((q,r)) thỏa bài toán. Bước 1: chọn (r). Nhận ra rằng (d=(r,a) eq 1), nếu như không, (mvdots d) với (nvdots d) suy ra ((m,n) eq 1). Xét vấn đề chọn những giá trị (r) thỏa mãn nhu cầu ((r,a)=1), có tổng số (varphi(a)) quý giá (r) như thế. Bước 2: lựa chọn (q). Cùng với mỗi giá trị (r) vẫn chọn, có tổng cộng (b) số (m=aq+r) cần được xét, cùng với (q) chạy từ (0) đến (b-1). Vày (a) và (b) nguyên tố cùng nhau nên những số (r), (a+r), (2a+r), (dots), ((b-1)a+r) lúc đem phân tách cho (b) đem phần dư sẽ cho ra các kết quả đôi một không giống nhau, làm cho tập hợp (,1,dots,b-1\). Ta đề xuất chọn ra các giá trị (m) nguyên tố với mọi người trong nhà với (b). Trong trường hợp đó, công dụng (m mod b) đề nghị ra một trong những nguyên tố cùng mọi người trong nhà với (b) với khác 0. Bao gồm (varphi(b)) quý hiếm (q) để tạo nên các quý hiếm (m) như thế. Các số nguyên được chọn qua hai cách sẽ vừa nguyên tố với mọi người trong nhà với (a) và (b), mặt khác ((a,b)=1), đề nghị chúng cũng nguyên tố cùng mọi người trong nhà với (ab). Áp dụng nguyên tắc nhân thì bao gồm (varphi(a)varphi(b)) số.


Bạn đang xem: Phi hàm euler


Xem thêm: Giám Sát Công Trình Tiếng Anh Là Gì, Có Ý Nghĩa Thế Nào? Giám Sát Công Trình Tiếng Anh Là Gì

(QED) Định lý Euler: với đa số số nguyên dương (n) nguyên tố cùng nhau với (a), ta có:

Định lý nhỏ dại Fermat chỉ ra rằng nếu (p) là một trong những nguyên tố thì:

Nếu ((a,p) = 1) thì ta gồm ((a^p-1 - 1) vdots p Leftrightarrow a^p-1 equiv 1pmodp). Đây là một trường hợp nhỏ dại của định lý Euler cùng với (n=p)