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, $a$ , that are less than $n$ 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 $n$ . Where $n \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 $k$ in the range $1 \le k \le n$ . If the greatest common divisor of $k$ and $n$ is equal to $1$ , then we increase the count of the output $a$ by 1.

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

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 $n$ is a prime number

If the input, $n$ , 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.

This example shows the proof of the property of an Euler's totient function where the input $n$ is in the form of $a \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.

What is Euler's totient function?

How does it work?

Properties of Euler's totient function

1.Input $n$ is a prime number

Example

2.Input $n$ is in the form of $p^k$

Example

3.Input $n$ is in the form of $p\cdot q$

Example

4.Input $n$ is in the form of $a \cdot b$

Example

Applications of Euler's totient function

Code example

Explanation

What is Euler's totient function?

How does it work?

Properties of Euler's totient function

1.Input nnn is a prime number

Example

2.Input nnn is in the form of pkp^kpk

Example

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

Example

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

Example

Applications of Euler's totient function

Code example

Explanation

1.Input $n$ is a prime number

2.Input $n$ is in the form of $p^k$

3.Input $n$ is in the form of $p\cdot q$

4.Input $n$ is in the form of $a \cdot b$