Euler Totient Function

Definition (Euler Totient 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.

Example (Euler Totient Function) Determine for and

Example (Euler Totient Function) Verify and     

Proposition (Euler Totient Function)

    (i) If is a prime number and is positive, then ; and in particlar when
    
    (ii) If and are different prime numbers, 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

Proposition (Euler Totient Function)

    (i) If and is prime, then

    (ii) If is prime, then

    (iii) If then

    (iv) If then
    
    (v) If is the unique prime factorization of then

   

Example (Euler Totient Function) Determine for and

Example (Euler Totient 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 and so for some integer and thus

  

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

    
    
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 Totient 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.

Using the equation,



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 Totient Function) Show that if is an odd integer, then

    Solution. Since is an odd integer and so
    

Example (Euler Totient Function) Show that

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

















Therefore, as desired.

Proposition (Euler's Theorem) If then

Proposition (Euler's Theorem Solves Linear Congruence Equation) The solution to the linear congruence is provided

    Proof. If then by Euler's theorem and so multiplying by we have and so is a solution.
    

Example (Euler's Theorem Solves Linear Congruence Equation) Solve the linear congruence

    Solution. The solution is where and . Thus,

Example (Finding Digits with Euler's Theorem) Find the last digit of the decimal expansion of

    Solution. Since and by Euler's Theorem we have,

.

So the last digit in the expansion of is 1 and thus the last digit in the expansion of is of course 2.
    Since and by Euler's Theorem we have,

.

So the last digit in the expansion of is 7 and thus the last digit in the expansion of is of course 9. Since the sum of integers with last digit of 2 and last digit of 9 is 1, the last digit of is a 1.

Example (Finding Digits with Euler's Theorem) Find the last digit of the decimal expansion of

• print this page
• pages linking here
• related pages