Euler’s Totient Function often symbolised as ϕ(n), is one of the most important and fascinating functions in number theory. Named after the mathematician Leonhard Euler, it counts the number of integers upto a given integer n that are coprime to n. This function has deep applications in number theory, cryptography, and even combinatorics.
What is Euler’s Totient Function?
In number theory, Euler’s Totient Function counts the positive integers up to a given integer n that are relatively prime to n. It is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common integer gcd(n,k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
Definition
For any positive integer n, ϕ(n) is the count of integers k (where 1<=k<=n) such that GCD(n,k)=1.
For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.
To compute ϕ(n) effectively, we rely on the prime factorisation of n. If the prime factorisation of n is:
where p1,p2,…,pk are the distinct prime factors of n, then ϕ(n) is given by:
where the product is over the distinct prime numbers dividing n.
Explanation of the Formula
Effect of Prime Factors: If n is to be divided by a prime p then there are n/p multiples of the p’s till n or (p,2p,3p,…). The problem is these multiples are not coprime to n, thus we deduct this count for each distinct prime factor of n.
Product Form: The product form
accounts for all distinct primes dividing n, and the multiplication by n adjusts the final count based on the fraction of numbers that are not divisible by any of these prime factors.
Also, Phi is a multiplicative function. This means that if gcd(m, n)=1
then φ(m).φ(n) = φ(m.n).
- The fundamental theorem of arithmetic expression states that unique expression,
where p1 < p2 < ... < pr are prime numbers and each ki ≥ 1 (The case when n = 1 corresponds to the empty product.). Repeatedly using the multiplicative property of φ and the formula for φ(pk) gives
![{isplaystyle {egin{array}{rcl}arphi (n)&=&arphi (p_{1}^{k_{1}})arphi (p_{2}^{k_{2}})dots arphi (p_{r}^{k_{r}})[.1em]&=&p_{1}^{k_{1}}eft(1-{rac {1}{p_{1}}}ight)p_{2}^{k_{2}}eft(1-{rac {1}{p_{2}}}ight)dots p_{r}^{k_{r}}eft(1-{rac {1}{p_{r}}}ight)[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}dots p_{r}^{k_{r}}eft(1-{rac {1}{p_{1}}}ight)eft(1-{rac {1}{p_{2}}}ight)dots eft(1-{rac {1}{p_{r}}}ight)[.1em]&=&neft(1-{rac {1}{p_{1}}}ight)eft(1-{rac {1}{p_{2}}}ight)dots eft(1-{rac {1}{p_{r}}}ight).nd{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7447918f84f4509322dda0b4aa4384ab8072a93)
- Proof of Multiplicativity:
Lemma: Let 𝑛1 and 𝑛2 be two coprime integers. A positive integer 𝑥≤𝑛1⋅𝑛2 is coprime to 𝑛1⋅𝑛2 if and only if 𝑔𝑐𝑑(𝑥 𝑚𝑜𝑑 𝑛1,𝑛1) = 1 and 𝑔𝑐𝑑(𝑥 𝑚𝑜𝑑 𝑛2,𝑛2)=1.
We can rephrase this lemma with two statements:
Firstly, for every pair of integers (𝑎1,𝑎2) such that 0≤𝑎1<𝑛1, 0≤𝑎2<𝑛2, 𝑔𝑐𝑑(𝑎1,𝑛1)=1, and 𝑔𝑐𝑑(𝑎2,𝑛2)=1, the integer 𝑥 corresponding to this pair is coprime to 𝑛1⋅𝑛2.
Secondly, for every integer 𝑥 in the interval [1,𝑛1⋅𝑛2] that is coprime to 𝑛1⋅𝑛2, its corresponding pair (𝑎1,𝑎2) has the following property: 𝑔𝑐𝑑(𝑥 𝑚𝑜𝑑 𝑛1,𝑛1)=1 and 𝑔𝑐𝑑(𝑥 𝑚𝑜𝑑 𝑛2,𝑛2)=1.
Now, consider two coprime integers 𝑛1 and 𝑛2. We know that every number 𝑥 in the interval [1,𝑛1⋅𝑛2] that is coprime to 𝑛1⋅𝑛2 has its corresponding pair of integers (𝑎1,𝑎2) such that 𝑎1 is coprime to 𝑛1 and 𝑎2 is coprime to 𝑛2. It also works the other way, every pair of integers (𝑎1,𝑎2) such that 𝑎1 is coprime to 𝑛1 and 𝑎2 is coprime to 𝑛2 has its corresponding integer 𝑥 coprime to 𝑛1⋅𝑛2.
Therefore, the number of positive integers that are not greater than 𝑛1⋅𝑛2 and coprime to it is equal to the number of pairs (𝑎1,𝑎2) where 0≤𝑎1<𝑛1 and 0≤𝑎2<𝑛2 such that 𝑎1 is coprime to 𝑛1 and 𝑎2 is coprime to 𝑛2. The number of such pairs is obviously 𝜙(𝑛1)𝜙(𝑛2) since we can choose 𝑎1 in 𝜙(𝑛1) ways and 𝑎2 in 𝜙(𝑛2) ways. Thus, 𝜙(𝑛1⋅𝑛2)=𝜙(𝑛1)⋅𝜙(𝑛2).
Properties of Euler Totient Function
φ(n) the Euler Totient Function is full of impressive properties that qualify it to be a significant tool in number theory and cryptography. In the following section, we elaborate upon its key properties as a starting point of our analysis.
Prime Number Property: If p is a prime number, then every integer q such that 1 ≤ 𝑞 < 𝑝 is coprime with p. Therefore, the totient function for a prime number p is: 𝜙 ( 𝑝 ) = 𝑝 − 1. Example For 𝑝 = 7, a prime number, the integers less than 7 are 1, 2, 3, 4, 5, 6. All of these are coprime with 7, so: 𝜙 ( 7 ) = 6.
Multiplicative Property: The Euler Totient Function also has the property of multiplicative property Since m and n are coprime means they have a GCD of 1 then 𝜙 ( 𝑚 × 𝑛 ) = 𝜙 ( 𝑚 ) 𝜙 ( 𝑛 ) For instance we take 𝑚 = 4 and 𝑛 = 9 which are coprimes. We have: Like Euclid, 𝜙 ( 36 ) = 𝜙 ( 4 ) 𝜙 ( 9 ) = 2.6 = 12.
Prime Power Property: Prime Power Property: To compute the above for p^k, the totient function is
The use of this property makes it easy to perform powers of primes. Example For 𝑝 = 3 and 𝑘 = 2, we have: 𝜙(3^2) = 3^2 − 3^(2 − 1) = 9− 3 = 6. Thus, it is possible to identify several values by considering that numbers 1, 2, 4, 5, 7, 8 and 9 have no common factors but 1.
Sum Over Divisors: Another fascination with the Totient Function is that it has an interesting property of summing to 𝑛 for all divisors 𝑑 of 𝑛: ∑ 𝑑 ∣ 𝑛 𝜙 ( 𝑑 ) = 𝑛. The property finds use in proofs, and solution to problems in number theory. For 𝑛 = 6, the divisors are 1, 2, 3 and 6 For 𝑛 = 8, the divisors are 1, 2, 4, and 8. We calculate: 𝜙 ( 1 ) = 1 , 𝜙 ( 2 ) = 1 , 𝜙 ( 3 ) = 2 , 𝜙 ( 6 ) = 2 . Thus: The sum of 𝜙 ( 1 ), 𝜙 ( 2 ), 𝜙 ( 3 ), 𝜙 ( 6 ) = 1 + 1 + 2 + 2=6.
Implementation
Naive Approach:
The naive approach involves iterating through all numbers from 1 to n and checking if each is coprime with n. This method is straightforward but inefficient for large n.
Efficient calculation of Totient function:
Implementation in O(√n):
int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
Introduction to the Sieve of Eratosthenes
The Sieve of Eratosthenes is a classic algorithm used to find all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number starting from 2. This method is efficient and runs in 𝑂 ( 𝑛 log log 𝑛 ).
#include <iostream>
#include <vector>
std::vector<bool> sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p <= n; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
int main() {
int n = 30;
std::vector<bool> primes = sieveOfEratosthenes(n);
std::cout << "Prime numbers up to " << n << " are: ";
for (int i = 2; i <= n; ++i) {
if (primes[i]) {
std::cout << i << " ";
}
}
std::cout << std::endl;
return 0;
}
Adapting the Sieve for the Totient Function
Implementation of Euler’s Totient Function from 1 to n.
To calculate totient of all the numbers between 1 and n, we can use the same idea as Seive of Eratosthenes and the complexity is O(nloglogn).
void phi_1_n(int n){
vector<int> phi(n+1);
for(int i=0; i<=n; i++){
phi[i]=i;
}
for (int i = 2; i <= n; i++) {
if (phi[i] == i) {
for (int j = i; j <= n; j += i)
phi[j] -= phi[j] / i;
}
}
}
We can also find totient from 1 to n using the divisor sum property. This implementation uses Seive of Eratosthenes, but has more complexity: O(nlogn)
void phi_1_n(int n) {
vector<int> phi(n + 1);
phi[0] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++)
phi[i] = i - 1;
for (int i = 2; i <= n; i++)
for (int j = 2 * i; j <= n; j += i)
phi[j] -= phi[i];
}
Applications
Applications in Cryptography: The Euler Totient Function is crucial in RSA encryption, a widely used public-key cryptosystem. RSA's security relies on the difficulty of factoring large numbers and the properties of the Euler Totient Function. Specifically, it is used in the key generation process to ensure that the encryption and decryption keys are valid.
Application in Number Theory: The function is used in various proofs and theorems, including Euler's theorem, which states that for any integer a and n that are coprime, a^φ(n) ≡ 1 (mod n). This theorem is a generalization of Fermat's Little Theorem.
Euler's theorem and Euler's totient function occur quite often in practical applications, for example both are used to compute the modular multiplicative inverse.
Example Problem
Problem Statement:
Prime(n) is defined as number of primes less than equal to n.
Totient(n) is defined as the number of positive integers less than or equal to n that are relatively prime to n.
F(n) = Prime(n) – Totient(n)
and we don’t like negative values, so if F(n) < 0, consider it as 0.
G(n) = Totient(n) ^ (Factorial (F(n)))
You are given a number n. You have to output G(n) % 10^9+7.
**Input:**First line consists of T, the number of test cases. Each of the next T lines contains one integer n.
**Output:**Output T lines each line containing the value of function G(n) % 10^9+7
Constraints: 1<=T<=100, 1<=n<=10000000
Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 10000000;
vector<bool> isPrime(MAXN + 1, true);
vector<int> primeCount(MAXN + 1, 0);
vector<int> phi(MAXN + 1, 0);
vector<long long> factorial(MAXN + 1, 1);
void sieve(int n) {
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
for (int j = i * 2; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 1; i <= n; i++) {
primeCount[i] = primeCount[i - 1] + isPrime[i];
}
}
void phi_1_to_n(int n) {
for (int i = 1; i <= n; i++) {
phi[i] = i;
}
for (int i = 2; i <= n; i++) {
if (phi[i] == i) {
for (int j = i; j <= n; j += i) {
phi[j] -= phi[j] / i;
}
}
}
}
void compute_factorials(int n) {
for (int i = 2; i <= n; i++) {
factorial[i] = (factorial[i - 1] * i) % MOD;
}
}
long long mod_exp(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
int main() {
sieve(MAXN);
phi_1_to_n(MAXN);
compute_factorials(MAXN);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int prime_n = primeCount[n];
int totient_n = phi[n];
int F_n = max(0, prime_n - totient_n);
long long G_n = mod_exp(totient_n, factorial[F_n], MOD);
cout << G_n << endl;
}
return 0;
}
