Indian Institute of Information Technology
Allahabad
Department of Information Technology
Discrete mathematical Structures
C3 ASSIGNMENT
Name:- Prince kumar
Enrollment No:- IIT2021027
TOPIC :- Euler’s totient function
Definition :-Euler’s Totient function is the mathematical
multiplicative functions which count the positive integers up to the
given integer generally called as ‘n’ that are a prime number to ‘n’
and the function is used to know the number of prime numbers that
exist up to the given integer ‘n’.
Explanation :- To know how many prime numbers are coming up
to the given integer ‘n’ Euler’s Totient Function is used. It is also
called an arithmetic function. For an application or use of Euler’s
Totient function, two things are important. One is that the gcd
formed from given integer ‘n’ should be multiplicative to each other,
and the other is the numbers of gcd should be the prime numbers
only. The integer ‘n’ in this case should be more than 1. From a
negative integer, it is not possible to calculate the Euler’s Totient
Function. The principle, in this case, is that for ϕ(n), the
multiplicators called m and n should be greater than 1. Hence
denoted by 1<m<n and gcd (m, n) = 1. Sign ϕ is the sign used to
denote Totient Function.
Properties of Euler’s Totient Function :- There are some of
the different properties. Some of the properties of Euler’s totient
function is as under-
Φ is the symbol used to denote the function.
The function deals with the prime numbers’ theory.
The function is applicable only in the case of positive integers.
For ϕ (n), two multiplicative prime numbers are to be found to
calculate the function.
The function is a mathematical function and useful in many
ways.
If integer ‘n’ is a prime number, then gcd (m, n) = 1.
The function works on the formula 1< m< n where m and n are
the prime numbers and multiplicative numbers.
In general, the equation is
Φ (mn) = ϕ (m) * ϕ (n) (1- 1 / m) (1 – 1/ n)
The function basically counts the number of positive integers
less than the given integer, which is relatively prime numbers
to the given integer.
If given integer p is prime then ϕ (p) = p – 1
If the power of p is prime then, if a = pn is a prime power then
ϕ (pn) = pn – p ( n-1)
ϕ (n) is not one – one
ϕ (n) is not onto.
ϕ (n), n > 3 is always even.
ϕ( 10n) = 4 * 10 n-1
Calculate Euler’s Totient Function
Example :-
Q. Calculate ϕ (7)?
Soln: ϕ ( 7 ) = (1,2,3,4,5,6) = 6
As all numbers are prime to 7, hence it made it easy to
calculate the ϕ.
Q. Calculate ϕ ( 100 )?
Soln: As 100 is large number hence it is time consuming to
calculate from 1 to 100 the prime numbers which are prime
numbers with 100.
Hence we apply the formula below:
ϕ (100) = ϕ (m) * ϕ (n) (1- 1 / m) (1 – 1/ n)
ϕ (100) = 2 2 * 2 5
ϕ (100) = 2 2 * 2 5 * (1 – 1/2) * ( 1 – 1/5)
100 * 1/2 * 4/5 = 40.
Q. Calculate ϕ (240)?
Soln: Multiples of 240 are 16*5*3
ϕ (240) = ϕ (m) * ϕ (n) (1- 1 / m) (1 – 1/ n)
ϕ (240) = 2 4 * 5 * 3
if nM is not prime number the we use nm – nm-1
= ( 2 4 – 2 (4-1) ) * (51 – 5 (1-1)) * (3 1 – 3 (1-1) )
= (2 4 – 2 3) * (5 – 1) * (3 – 1) = 64
Applications
The various applications are as under:-
The function is used for defining RSA encryption system used
for internet security encryption.
Used in prime numbers theory.
Used in large calculations also.
Used in applications of elementary number theory.
Conclusion
Euler’s totient function is useful in many ways. It is used in the
RSA encryption system, which is used for security purposes.
The function deals with the prime number theory, and it is
useful in the calculation of large calculations also. The function
is also used in algebraic calculations and elementary numbers.
The symbol used to denote the function is ϕ, and it is also
called a phi function. The function consists of more theoretical
use rather than practical use. The practical use of the function
is limited. The function can be better understood through the
various practical examples rather than only theoretical
explanations. There are various rules for calculating the Euler’s
totient function, and for different numbers, different rules are
to be applied. The function was first introduced in 1763, but
because of some issues, it got recognition in 1784, and the
name was modified in 1879. The function is a universal function
and can be applied everywhere.
