Scribd
Upload
30 views15 pages

MFCS Module-L1-7

Euler's totient function counts the number of positive integers up to a given integer n that are relatively prime to n. It is written as Φ(n) and counts the number of integers between 1 and n that share no common factors with n other than 1. The properties of the Euler totient function include that Φ(p

Uploaded by

Dr K Rajendra Prasad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
30 views15 pages

MFCS Module-L1-7

Euler's totient function counts the number of positive integers up to a given integer n that are relatively prime to n. It is written as Φ(n) and counts the number of integers between 1 and n that share no common factors with n other than 1. The properties of the Euler totient function include that Φ(p

Uploaded by

Dr K Rajendra Prasad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

Fermat Numbers

2𝑛
An integer is of the form 𝐹𝑛 = 2 + 1; n ≥ 0

If 𝐹𝑛 is the prime then it is Fermat’s Prime

𝐹0=3
𝐹1=5
𝐹2=17
𝐹3=257
𝐹4=655537
𝐹5=4294967297 ( it is divisible by 641)
These Fermat numbers are used in the cryptography
Fermat Theorem
Fermat Theorem
Fermat Theorem
Fermat Theorem
Euler’s Totient Function

Euler's totient function counts the positive integers up to a given


integer n that are relatively prime to n

It is written using the Greek function Φ(n) and it also called as Euler’s
phi function

It is the number of integers k in the range 1 ≤ k ≤ n for which the


greatest common divisor gcd(n, k) is equal to 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.
Properties of Euler’s Totient Function

1. For a prime number p, Φ(p) = p – 1

Examples:
Φ(5)=4
Φ(7)=6
Φ(13)=12
Properties of Euler’s Totient Function

2. For two prime numbers a and b Φ(a.b)= Φ(a). Φ(b)=(a-1).(b-1)

Examples:
Φ(15)= Φ(3)* Φ(5)=2*4=8
Φ(35)=?
Φ(21)=?
Φ(65)=?
Φ(22)=?
Φ(39)=?
Properties of Euler’s Totient Function

3. For a prime number p, ∅ 𝒑𝒌 = 𝒑𝒌 − 𝒑𝒌−𝟏

Φ(32) = Φ(25) =32-16=16


Φ(125)=?
Φ(243)=?

5
Properties of Euler’s Totient Function

4. For two number a and b,


∅ 𝒂. 𝒃 = ∅ 𝒂 . ∅ 𝒃 . 𝒈𝒄𝒅(𝒂, 𝒃)/ ∅ 𝒈𝒄𝒅 𝒂, 𝒃 , 𝒊𝒇 𝒈𝒄𝒅 𝒂, 𝒃 ≠1

∅ 𝒂. 𝒃 = ∅ 𝒂 . ∅ 𝒃 , 𝒊𝒇 𝒈𝒄𝒅 𝒂, 𝒃 = 𝟏

Examples:
∅ 𝟒. 𝟔 =?

∅ 𝟔. 𝟖 =?
Properties of Euler’s Totient Function

5. Sum of values of totient functions of all divisors of n is equal to


n.
෍∅ 𝑑 = 1
𝑑/𝑛
Properties of Euler’s Totient Function
Properties of Euler’s Totient Function

Criteria of n Formula
Φ(n) ‘n’ is a prime Φ(n) = n-1
(Euler’s n= p * q, p and q are Φ(n)=(p-1)*(q-1)
totient prime numbers
function n= a * b; Φ(n) =n x*(1-1/p1)* (1- 1/p2)
or finding Either a or b
composite numbers
number of Or
co-primes) Both a and b are
composite numbers
Properties of Euler’s Totient Function

1. Φ(n)=Φ(1000)=Φ(23 53)=?
2. Determine ϕ(37) And ϕ(35)
using Euler Totient function?
3. Define Euler totient function and
how it uses to find co primes for
the integers

You might also like