Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page
This page accessed
times since March 26, 2005.Page created by: hjsmithh@sbcglobal.net
Changes last made on Monday, 06-Aug-07 20:47:34 PDT
Euler's totient function Phi(n) is defined as the number of integers <= n that are relatively prime to (i.e., do not contain any factor in common with) n. Phi(12) = 4 because of the 12 numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12 only the 4 numbers 1, 5, 7, and 11 are relatively prime to 12. By convention Phi(0) = 1. The first few values of Phi(n) for n = 1, 2, ... are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, ... .
To compute Phi(n), first factor n into its prime factors. For this document the following notation is used. An integral number n > 1 can be written as n = P1^A1 * P2^A2 * ... Pr^Ar where the Pi's are the various different prime factors, Ai the number of times Pi occurs in the prime factorization and r the number of prime factors.
The classic formula for Phi is:
but for computation the following formula is used
For example, 12 = 2^2 * 3^1, Phi(12) = (2 − 1)*2^1 * (3 − 1)*3^0 = 1*2 * 2*1 = 4.
Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page
times since March 26, 2005.