Euler's Totient Function  Euler's Theorem
Totient function (denoted by $\phi:\mathbb{N} \rightarrow \mathbb{N}$ ), also known as phifunction or Euler's Totient function, is a mathematical function which counts the number of integers in the range $[1, n]$ (both inclusive) that are coprime to $n$ or we can say whose GCD with n is 1.
Note:
 2 positive integers a and b are said to be coprime if their greatest common factor/divisor is equal to 1, that is,
 $1$ is considered coprime to all numbers.
Example of Euler's Totient Function
Example 1
For an small example, let's take $n = 10$.
The numbers less than 10 are as follows:
Out of these,
 1 is coprime to 10 (by definition).
 2 and 5 completely divide 10, therefore, are not coprime to 10.
 4, 6, 8 are divisible by 2 (just like 10), therefore, their greatest common divisor is 2. Therefore, they are also not coprime to 10..
 3, 7, 9 neither divide 10 nor share any common factor with it. Therefore, by definition of coprime numbers, we saw earlier, these numbers are coprime to 10.
Therefore, there are 4 numbers less than 10 that are coprime to it. These are
Therefore,
Example 2
Let's take a bigger n, say 24.
In range [1,24] there are total 8 numbers 1,5,7,11,13,17,19,23 are there whose gcd with 24 is equal to 1 (they are coprime to it). Therefore:
How to Compute Φ(n) for an Input n?
Suppose you're given an integer $n \in \mathbb{N}$. Using the fundamental theorem of arithmetic, we know that $n$ can be decomposed as a product of the positive integral powers of its prime factors. Therefore,
(1):
where $p_i$ are prime factors of $n$.
Now using an interesting property of the totient function, which states that
(2):
provided that $a, b, c$ are coprime to each other.
Using $(1)$ and $(2)$, we get
(3):
Another interesting property of the totient function $\phi(m)$ is that if $m$ is a power of a prime number, say $p^{\alpha}$ where $\alpha \ge 1$, then,
(4):
Using $(4)$ and $(3)$, we get
(5):
Taking $p_i^{\alpha_i}$ common from $i^{th}$ term from RHS of $(5)$, we get
Hence we get
The above equation gives us a method to calculate $\phi(n)$ for any desired $n$.
Code Implementation
Using the result we derived above, it is quite easy to write a program to calculate $\phi(n)$ for an input $n$.
C++ Implementation 1
Explanation:
The algorithm initializes answer with n and iterates through primes up to the square root of n, dividing n by each prime divisor found. It updates answer by multiplying it with (1  1/p), ensuring accuracy. If n remains greater than 1 after this process, it accounts for the last prime factor of n. This optimized approach efficiently calculates Euler's Totient function, addressing precision errors by using multiplication instead of division.
Time Complexity: $\mathcal{O}({\sqrt{n}})$
Space Complexity: $\mathcal{O}(1)$
C++ Implementation 2
Explanation: This optimized implementation efficiently computes Euler's totient function ($\phi$) for all integers up to $n$ using the Sieve of Eratosthenes. Rather than factorizing each number individually, it iterates through primes and updates their multiples by subtracting $\phi[j]/i$. For prime numbers, it subtracts 1. This approach ensures efficiency by avoiding redundant computations.
Time Complexity: $\mathcal{O}(n\log(\log{n}))$
Space Complexity: $\mathcal{O}(n)$
C++ Implementation 3 (Using Divisor Sum Property)
Explanation: This implementation leverages the divisor sum property of the totient function. Initially, subtracting ϕ(1) from all numbers, the ith element of the phi vector initializes as i1. When processing element i, previous phi values remain unchanged. Subsequently, phi[i] subtracts from multiples of i starting from 2*i up to n. Upon completion, the phi array holds the ϕ values for numbers 1 to n. This optimized approach efficiently computes totient values, exploiting the properties of integer factorization.
Time Complexity: $\mathcal{O}(n\log{(n)})$
Space Complexity: $\mathcal{O}(n)$
Properties of Euler's Totient Function
In addition to the aboveused properties, we also have the following results related to the Totient function:

If $p$ is a prime number, then
$\phi(p) = p1$ 
If $p$ is a prime number and $m$ is a positive integer (that is, $m \ge 1$), then
$\phi(p^m) = p^{m}p^{m1}$ 
For any two positive integers $m$ and $n$ we have
$\phi(mn) = \phi(m)\cdot\phi(n)\cdot \frac{\gcd(m, n)}{\phi(\gcd(m, n))}$Considering the case when $m$ and $n$ are coprime, then $\gcd(m,n)=1$. In such a scenario, the above relation reduces to
$\phi(mn) = \phi(m)\cdot\phi(n)$ 
The sum of values of the totient function over the positive divisors of $n$ equals $n$ itself. In other words:
$\sum_{kn} \phi{(k)} = n$ 
If $m$ and $n$ are two prime numbers, then using (1) and (3), we get:
$\phi(mn) = \phi(m)\cdot\phi(n) = (m1)\cdot(n1)$This property is used in the RSA algorithm.
Application of Totient Function in Euler's Theorem
Euler's theorem (sometimes also called as Euler's totient theorem) which makes use of Euler's totient function, states the following:
If $a$, $n$ $\in \mathbb{N}$ are relatively prime, then
$a^{\phi(n)} \equiv 1\mod{n}$
The converse of the Euler's theorem also holds, which is stated as:
If $a^{\phi(n)} \equiv 1 \mod{n}$, then $a$ and $n$ are relatively prime.
A special case of this theorem where $n$ is a prime number is used in the RSA encryption algorithm. This special case of the theorem is popularly known as Fermat's Little Theorem and states that
$a^{n1} \equiv 1 \mod{n}$
Taking an example, suppose $a = 10$ and $n = 9$. Using the methods described above, we get $\phi(9) = 6$.
Therefore, $a^{\phi(n)} = 10^{6}$.
Applying the $\mod n \ (=\mod 9)$ operator on $10^6$, we get
which was the expected result since 10 and 9 don't have any common divisor other than 1, that is to say, they are coprime.
Suppose we had taken a number $n = 2$ which is not coprime to 10 (since their greatest common divisor is 2).
In this case, $\phi(n)= \phi(2) =1$.
Therefore, $a^{\phi(n)} = 10^{1} = 10$.
Applying the $\mod n \ (=\mod 2)$ operator on $10$, we get
Thus, we've verified that the theorem does not hold when $a$ and $n$ are not coprime.
Conclusion
 Euler's totient function, $\phi:\mathbb{N} \rightarrow \mathbb{N}$, counts the number of integers between $1$ and $n$ (both inclusive) that are coprime to $n$.
 If $p$ is a prime number, then
$\phi(p) = p1$
 The sum of values of the totient function over the positive divisors of $n$ equals $n$ itself.
 Totient Function is used in Euler's theorem, Fermat's Little theorem which is used in the RSA encryption algorithm.
 The value of Totient function for a number $n$ can be implemented in the best time complexity of $\mathcal{O}(n\log{(\log{n})})$ with an associated space complexity of $\mathcal{O}(n)$