What is Euler's totient function?

Euler's totient function is also known as the phi function φ\varphi. It calculates the number of positive integers, aa, that are less than nn and co-primeTwo numbers are considered to be co-prime if the only positive integer that divides them is 1, meaning that greatest common divisor of a and n is 1. GCD(a, n) = 1 to nn. Where n∈Nn \in \mathbb{N} is the input to the totient function. The totient function is defined by the rule given below.

How does it work?

The totient function calculates the greatest common divisor of the integers kk in the range 1≤k≤n1 \le k \le n. If the greatest common divisor of kk and nn is equal to 11, then we increase the count of the output aa by 1.

To understand the working of the totient function in more detail, we take an example of n=5n=5, where nn serves as the input to the totient function, φ(5)\varphi(5). Then the gcd of nn and kk is calculated, where k={1,2,3,4,5}k = \{1,2,3,4,5\}. If the gcd is equal to 11, we increase the count of the output aa by 11, and at the end aa represents the output of the totient function as shown in the illustration below.

1 of 5

Properties of Euler's totient function

The properties of Euler’s totient function make it easier to solve for the output a little easier and computationally less expensive, given that certain conditions are met. The properties of Euler’s totient function are as follows.

1.Input nn is a prime number

If the input, nn, of the totient function is a prime numberPrime numbers are only divisible by 1 and themselves, which makes the gcd of the prime number and all numbers less than it equal to 1.. Then the result of the totient function is equal to the equation given below.

Example

The input, nn, is equal to 33. Then the output of the function φ(3)=2\varphi(3) = 2, as gcd(1,3)=1gcd (1, 3) = 1 and gcd(2,3)=1gcd (2, 3) = 1.

2.Input nn is in the form of pkp^k

If the input, nn, of the totient function is in the form pkp^k, where pp is a prime number, and kk is any natural number. Then the result of the totient function is equal to the equation given below.

Example

The input ,nn, is equal to 44 or 222^2. Then the output of the function φ(22)=2\varphi(2^2) = 2, as gcd(1,4)=1gcd (1, 4) = 1 and gcd(3,4)=1gcd (3, 4) = 1. If we plug the values of pp and kk into the equation given above, we get the following equation.

Simplifying the equation gives us the following result.

This example shows the proof of the property of an Euler's totient function where the input, nn, is in the form of pkp^k.

3.Input nn is in the form of p⋅qp\cdot q

If the input, nn , of the totient function is in the form p⋅qp\cdot q, where pp and qq are distinct prime numbers. Then the result of the totient function is equal to the equation given below.

Example

The input, nn, is equal to 66 or 2⋅32\cdot3. Then the output of the function φ(2⋅3)=2\varphi(2 \cdot 3) = 2, as gcd(1,6)=1gcd (1, 6) = 1 and gcd(5,6)=1gcd (5, 6) = 1. If we plug the values of pp and kk into the equation given above, we get the following equation.

Simplifying the equation gives us the following result:

This example shows the proof of the property of an Euler's totient function where the input, nn, is in the form of p⋅qp \cdot q.

4.Input nn is in the form of a⋅ba \cdot b

If the input, nn, of the totient function is in the form a⋅ba \cdot b, where aa and bb are co-prime positive integers. Then the result of the totient function is equal to the equation given below.

Example

The input, nn, is equal to 1010 or 2⋅52\cdot5. Then the output of the function φ(2⋅5)=4\varphi(2 \cdot 5) = 4, as gcd(1,10)=1gcd (1, 10) = 1, gcd(3,10)=1gcd (3, 10) = 1, gcd(7,10)=1gcd (7, 10) = 1, and gcd(9,10)=1gcd (9, 10) = 1. If we plug the values of aa and bb into the equation given above, we get the following equation.

Applying the first property on φ(2)\varphi(2) and φ(5)\varphi(5), as 22 and 55 are prime numbers.

Simplifying the equation gives us the following result.

This example shows the proof of the property of an Euler's totient function where the input nn is in the form of a⋅ba \cdot b.

Applications of Euler's totient function

Euler's totient functions serve as the basis for modern-era cryptography. It is also useful in other places in number systems where the goal is to find the count of the co-prime number of a number. The applications of the function are as follows.

  • Euler's theorem: Euler's theorem uses Euler's totient function to extend the functionality of Fermat's little theorem, as Euler's theorem is valid for all positive integer values.

  • RSA encryption: The totient function is used in conjunction with Euler's theorem in RSA for the process of key generation, encryption, and decryption.

Code example

The code below shows how Euler's totient function values are calculated. Change the value of the variable, a, to change the input to the totient function.

#include <iostream>
using namespace std;
int gcd(int k, int n)
{
    int gcdValue = 1;
    // To select the largest number
    if(k > n)
    {
        swap(k, n);
    }
    for(int i = 1 ; i <= k; i++)
    {   // To if "i" is the common divisor of two number
        if(k % i == 0 && n % i == 0) 
        {
            gcdValue = i;
        }
    }
    return gcdValue;
}
int totient(int n)
{  
    int result = 0;
    int gcdValue = 1;
    for(int i = 1 ; i <= n; i++)
    {   
        gcdValue = gcd(i, n);
        if(gcdValue == 1)
        {
            result += 1;
        }
    }
   return result;
}
  
int main()
{
    // Feel free to change a
    int a = 10;
    cout << "totient " << a << " : " << totient(a); 
    return 0;
}

Explanation

The explanation of the code above is as follows:

  • Line 9–12: The if condition ensures that the larger number is in the variable, n, and the second largest is in the variable, k.

  • Line 14–20: The for loop divides k and n with i to check if both the variables are divisible by i. The if condition updates the value of the variable gcdValue if i is a common divisor of k and n. At the end of the for loop, gcdValuecontains the greatest common divisor of variables k and n.

  • Line 30–37: The for loop calls the function gcd() with i and n as input and the result is stored in the variable gcdValue. The if condition checks if the value of the variable gcdValue is equal to 1. If it is, the value of the variable, result, is increased by 1.

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved