Euler, một trong những người bận rộn nhất trong lịch sử Toán học, lần đầu tiên chứng minh hàm này vào năm 1763. Ông đã cố gắng sử dụng số pi ( π) để biểu thị hàm nhưng hóa ra số pi đã bị chiếm dụng. Năm 1801, Gauss đề nghị chúng ta sử dụng phi ( ) để thay thế. Nó được đặt tên là 'Totient Function' vào năm 1879, bởi James Joseph Sylvester.

Với tên và ký hiệu đã được giải quyết, hãy xem nó làm gì. Một cặp nguyên tố cùng nhau là nơi ước chung lớn nhất mà hai số chia sẻ là 1. Họ không có các yếu tố chung lớn hơn; chúng tương đối nguyên tố.

Hàm Totient cho chúng ta biết một số có bao nhiêu nguyên tố nhỏ nhất nhỏ hơn chính nó. Các đồng nguyên tố nhỏ hơn của 9 là 1, 2, 4, 5, 7 & 8. (9) = 6. Nhưng làm thế nào nó làm điều đó?

Tìm Totient

Đối với số nguyên tố

Đối với các số nguyên tố, giá trị Totient 1nhỏ hơn chính nó. Mọi số nhỏ hơn một số nguyên tố đều là số nguyên tố tương đối với nó. Đây là định nghĩa của một số nguyên tố. Vì vậy, đối với bất kỳ số nguyên tố p, (p) = p -1. Điều đó đã đủ đơn giản.

Đối với quyền lực chính

Đối với một số nguyên tố pđược nâng lên thành lũy thừa k, các số duy nhất nhỏ hơn số pᵏđó KHÔNG phải là số nguyên tố của nó là các bội số khác của p. Điều này là do plà yếu tố duy nhất trong pᵏ.

Yếu tố của tất cả pᵏcó thể được biểu diễn: p, 2p, 3p, ..., pᵏ⁻¹p.

pᵏ⁻¹nhất thiết phải là bội số lớn nhất của plớn hơn hoặc bằng pᵏbởi vì pᵏ⁻¹p = p.

Do đó, chúng tôi biết rằng pᵏcó pᵏ⁻¹các số nhỏ hơn nó không phải là nguyên tố cùng nhau. Có pᵏcác số nguyên nhỏ hơn pᵏ. Nếu pᵏ⁻¹không nguyên tố cùng nhau thì pᵏ - pᵏ⁻¹các số nguyên nguyên tố cùng nhau pᵏ.

Đối với các lũy thừa nguyên tố, công thức đếm các số nguyên tố cùng nhau nhỏ hơn nó là: (pᵏ) = pᵏ - pᵏ⁻¹.

Đối với mọi thứ khác

Đối với những số không phải là số nguyên tố cũng không phải là lũy thừa nguyên tố, chúng ta sử dụng Công thức tích Euler. Nó hoạt động như sau.

Giải quyết cho n, có jthừa số nguyên tố, công thức tích có dạng:

n x (1 — 1/p₁) x (1 — 1/p₂) x ... x (1 — 1/pⱼ).

n = 42
> which has 3 prime factors
j = 3
ϕ(42) = ϕ(7 x 2 x 3) = 42 x (1 — 1/7) x (1 — 1/2) x (1 — 1/3) = 12.
ϕ(42) = 12

Một trong những thừa số nguyên tố của 42 là 3. Chúng ta biết rằng 1 trong 3 số là bội số của 3 và 2 trong 3 số còn lại thì không. Vì vậy, chúng tôi nhân 42 2/3để cung cấp cho chúng tôi số lượng các số nhỏ hơn 42 không chia sẻ thừa số 3.

Lặp lại quy trình này cho tất cả các số nguyên tố của 42 sẽ như sau: 6/7 x 1/2 x 2/3 = 6/21. Điều này cho chúng ta tỷ lệ của tất cả các số nhỏ hơn 42 không có thừa số nguyên tố nào. Để có được số lượng, chúng ta có thể thực hiện tỷ lệ nhân với tổng: 6/21 x 42 = 12.

Chúng ta cũng có thể sử dụng điều này như một bằng chứng chứng thực cho các cường quốc nguyên tố. Chúng tôi nhận thấy rằng đối với bất kỳ lũy thừa nguyên tố nào pᵏ, giá trị tổng là (pᵏ) = pᵏ - pᵏ⁻¹.

pᵏ — pᵏ⁻¹
pᵏ — (pᵏ x p⁻¹)
pᵏ — (pᵏ x 1/p)
pᵏ(1 — 1/p)

Sử dụng hàm Totient

Bạn được trang bị để tìm giá trị của nó trong mọi trường hợp, nhưng tại sao bạn lại muốn? Euler's Totient được dựa rất nhiều khi làm việc với Hàm Carmichael, như chúng ta đã thấy trong phần giải thích về nó trong một bài đăng trước đó . Do đó, nó rất quan trọng đối với mật mã kỹ thuật số.

Totient cũng có ý nghĩa đối với hai phỏng đoán chưa được giải quyết: Phỏng đoán của Lehmer và phỏng đoán của Carmichael.

Chúc bạn học toán vui vẻ.

Hơn ?

Tôi viết bản tin ngắn nhất thế giới. Một điều nhanh chóng mà tôi đã học được hoặc nhìn thấy hoặc đọc được trong tuần, vào mỗi Thứ Tư.

Tôi muốn nó là bản tin dễ tiếp cận nhất, chính xác nhất mà bạn nhận được.

Nó có thể đáng để thử. Hủy đăng ký cũng dễ dàng.

Nó được gọi là . Hẹn gặp bạn ở đó!