Euler's Phi Function

Definition (Euler's φ-Function) For each integer let denote the number of positive integers less than and relatively prime to and let The function is called the Euler's -function, or sometimes the totient function.

Proposition (Euler's φ-Function)

    (i) If is a prime number and is positive, then
    
    (ii) If and are different prime numbers, then
    
    (iii) If then
    
    (iv) If then
    
    (v) If is prime, then
    
    (vi) If is the unique prime factorization of then

   

    Proof. (i) By Euclid's Lemma, the integers such that and is divisible by are Thus the number of positive integers less than and relatively prime to is
    
    (ii) By Euclid's Lemma, an integer will satisfy if and only if or and the number of such is Thus the number of such that and is
    
    (iv) There are congruence classes which are represented by an integer relatively prime to in Let these representatives be The products are all distinct because and since each product is still relatively prime to there is a representative from each of the congruence classes Therefore, Since as desired.
    
    (v) If then otherwise and so since Therefore, as desired.

Example (Euler's φ-Function) Solve the functional equation involving the Euler tuotient function.

    Solution. The claim is that for some integers and To see this let be the highest power of dividing then



for some integer Since we must have or and so or Now we should try to bound the exponents if we can.
    If then and so Therefore, and must be or 1. If then and there is no such prime. Therefore, must be 0,1, or 2.  Finally, we have

    

Example (Euler's φ-Function) Solve the functional equation involving the Euler tuotient function.

    Solution. The claim is that for some integers and To see this let be the highest power of dividing then



for some integer Since we must have and so Now we should try to bound the exponents if we can.

    If then and so or Therefore, and must be or 1. If the and so Therefore, must be 0,1, or 2. If then and so Therefore, must be or less. If then and so which is not possible. We are left with and , and   Finally, we have
    

Example (Euler φ-Functional Equation) Show that if is an odd integer, then

    Solution. Since is an odd integer and so

Example (Euler φ-Function and Divisibility) Show that

    Solution. Let be the prime factorization of Since we have where for Using we have

















Therefore, as desired.

• print this page
• pages linking here
• related pages