The sieve of Eratosthenes:

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n
is smaller than 10 million or so.

Following is the algorithm to find all the prime numbers less than or equal to a given integer n by
the Eratosthene’s method:

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Explanation with Example:

Let us take an example when n = 100. So, we need to print all prime numbers smaller than or equal
to 100.

We create a list of all numbers from 2 to 100.

According to the algorithm we will mark all the numbers which are divisible by 2 and are greater
than or equal to the square of it.
Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3
and are greater than or equal to the square of it.

We move to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal
to the square of it.
We move to our next unmarked number 7 and mark all multiples of 7 and are greater than or equal
to the square of it.

We continue this process, and our final table will look like below:
Chinese remainder theorem:

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the
Euclidean division of an integer n by several integers, then one can determine uniquely the
remainder of the division of n by the product of these integers, under the condition that the divisors
are pairwise coprime (no two divisors share a common factor other than 1).

For example, if we know that the remainder of n divided by 3 is 2, the remainder of n divided by 5 is
3, and the remainder of n divided by 7 is 2, then without knowing the value of n, we can determine
that the remainder of n divided by 105 (the product of 3, 5, and 7) is 23. Importantly, this tells us
that if n is a natural number less than 105, then 23 is the only possible value of n.

First we need to understand inverse and congruence.

Inverse of mod function:

Find inverse for 3 modulo 7

7 = 2*3 +1 [using Euclidean rules]

 1 = 7 – 2*3
 1 = -2*3 [here we remove 7 because if we divide by 7 then it becomes completely divisibe]
So, inverse for 3 modulo 7 is -2
Congruence:

For a positive integer n, two integers a and b are said to be congruent modulo n (or a is congruent
to b modulo n), if a and b have the same remainder when divided by n (or equivalently if a − b is
divisible by n). It can be expressed as, a ≡ b mod n.

Example:

Prove that, 17 ≡ 5 mod 6

Here, a=17, b=5 and n=6

a mod n = 17 mod 6 = 5

b mod n = 5 mod 6 = 5

So, we can say that, 17 ≡ 5 mod 6 (proved)

Problem:

If, x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 then find the value of x using Chinese remainder
theorem?

Solution:

Given,

x ≡ 2 mod 3

x ≡ 3 mod 5

x ≡ 2 mod 7

First we need to check that every pair of (3,5,7) must not contain gcd greater than 1. Here, gcd(3,5)
is 1, gcd(5,7) is 1 and gcd(3,7) is also 1. So, this is valid.

Let, r1 = 2, r2 = 3 and r3 = 2

m1 = 3, m2 = 5 and m3 = 7

m = m1*m2*m3 = 3*5*7 = 105

M1 = m/m1 = 105/3 = 35

Y1 = M1 modulo m1 = 35 modulo 3 = 2 [here 2 is the inverse of 35 mod 3]

M2 = m/m2 = 105/5 = 21

Y2 = M2 modulo m2 = 21 modulo 5 = 1 [here 1 is the inverse of 21 mod 5]

Y3 = M3 modulo m3 = 15 modulo 7 = 1 [here 1 is the inverse of 15 mod 7]

Now, x ≡ r1*M1*Y1 + r2*M2*Y2 + r3*M3*Y3 = 2*35*2 + 3*21*1 + 2*15*1 = 233

x ≡ 23 mod 105

Another solutions can be x ≡ 348 [adding 105 with 233]

x ≡ 128 [subtracting 105 from 233]

smallest solution possible x ≡ 23

Euler’s Phi Function:

Euler’s Phi function is number of positive integers less than ‘n’ that are relatively prime to ‘n’.

Example: Find φ(5)?

Solution:

Here, n=5. Numbers less than 5 are 1,2,3,4

We need to find the gcd of each smaller number with the given number,

gcd(1,5) = 1

gcd(2,5) = 1

gcd(3,5) = 1

gcd(4,5) = 1

Though the results are all 1 so the answer should be, φ(5) = 4

Example: Find φ(8)?

Solution:

Here, n=8. Numbers less than 5 are 1,2,3,4,5,6,7

We need to find the gcd of each smaller number with the given number,

gcd(1,8) = 1

gcd(2,8) = 2
gcd(3,8) = 1

gcd(4,8) = 2

gcd(5,8) = 1

gcd(6,8) = 2

gcd(7,8) = 1

Though the results are 1 for (1,3,5,7) so the answer should be, φ(8) = 4

Finding Euler Phi using formula:

Case 1: if, n is prime then, φ(n) = (n-1)

Case 2: if, n = p * q and p and q are both prime then, φ(n) = (p-1) * (q-1)

Case 3: if, n = p * q

Either p or q is composite

Both p and q are composite

Then, φ(n) = n * (1-1/p1) * (1-1/p2) * …….

Example: Find φ(5)?

Solution: here, n = 5 which is prime number.

So, according to case1, φ(5) = (5-1) = 4

Example: Find φ(21)?

Solution: here, n = 21 which is not prime number. But we can denote 21 by using two prime
numbers like 3 and 7. Let, p = 3 and q = 7

So, according to case2, φ(21) = (p-1)*(q-1) = (3-1)*(7-1) = 12

Solution:

This is a special case where we can denote 25 by using 5*5 where 5 is prime. But in this case we are
strictly prohibited to use case2 because here 5 appears 2 times as p and q. here p and q must
contain different values. So, in that case we need to use case3.

φ(25) = 25 * (1 - 1/5) = 25 * (4/5) = 20

So, φ(25) is equal to 20.

Example: Find φ(7000)?

Solution:

Here, n = 7000 = 23 * 53 * 71 and distinct prime factors are 2, 5 and 7

φ(n) = n * (1-1/p1) * (1-1/p2) * …….

φ(7000) = 7000 * (1-1/2) * (1-1/5) * (1-1/7)

φ(7000) = 7000 * (1/2) * (4/5) * (6/7)

φ(7000) = 2400

Extended Euclidean Algorithm:

Extended Euclidean Algorithm is an extension of Euclidean Algorithm which finds two things for
integer a and b: It finds the value of GCD(a,b). It finds two integers x and y such that, ax + by =
gcd(a,b).

Problem: Use extended Euclidean algorithm to write a linear combination of 1180 and 482?

Solution:

Using basic Euclidean process,

1180 = 482(2) +216

482 = 216(2) + 50

216 = 50(4) + 16

50 = 16(3) + 2

16 = 2(8) + 0 [here we find the remainder 0]

2 = 1180( _ ) + 482( _ ) and to do that we need to start from the end now,

50 = 16(3) + 2

2 = 50 – 16(3)

= 50 + 16(-3)

= 50 + (216+50(-4))(-3)

= 216(-3) + 50(13)

= 216(-3) + (482+216(-3))(13)

= 216(-29) + 482(13)

= (1180 + 482(-2)) (-29) + 482(13)

= 1180(-29) + 482(71)
Application of prime factorization:

Prime factorization is the process of expressing a number as the product of its prime factors. This
concept has various applications across different fields. Here are some practical applications of
prime factorization:

 Cryptography:
RSA Algorithm: Prime factorization is crucial in the RSA (Rivest-Shamir-Adleman)
encryption algorithm, a widely used method for secure communication. The security of RSA
relies on the difficulty of factoring the product of two large prime numbers.
 Computer Science:
Data Compression: Prime factorization is used in certain data compression algorithms,
where numbers are represented as the product of prime factors, reducing the amount of
data needed to store them.
Error Detection and Correction: Prime factorization can be employed in error-detecting and
error-correcting codes in computer systems.
 Mathematics Education:
Teaching Factorization: Prime factorization is an essential concept in mathematics
education. It helps students understand the relationship between numbers and primes, as
well as the fundamental theorem of arithmetic.
 Economics:
Currency Denominations: Prime factorization can be applied in determining the
denominations of currency to minimize the number of coins or bills needed for transactions.
 Biology:
Genetics: In biology, prime factorization has been used as a metaphor to explain the
inheritance of traits. Just as traits are determined by a combination of genes, numbers can
be represented as a combination of prime factors.
 Chemistry:
Chemical Formulas: The concept of prime factorization is indirectly related to the
determination of chemical formulas, where the ratio of atoms is expressed in its simplest
form.
 Physics:
Wave Frequencies: In physics, prime factorization can be used in the analysis of wave
frequencies and their harmonics.
 Number Theory:
Research and Pure Mathematics: Prime factorization plays a central role in number theory
and has applications in various branches of pure mathematics.
 Network Design:
Network Routing: Prime factorization can be applied in optimizing network routing
algorithms, where the goal is to find the most efficient path between two points.
 Manufacturing and Production:
Resource Allocation: In manufacturing and production planning, prime factorization can be
used to optimize resource allocation and scheduling.
Application of phi:

The function ϕ(n), also known as Euler's totient function, is used in various applications in number
theory and cryptography. Here are some notable applications:

 RSA Cryptosystem:
As mentioned earlier, Euler's totient function (ϕ) is used in the RSA algorithm for key
generation. It is used to calculate ϕ(n), where n is the product of two large prime numbers.
The value of ϕ(n) is essential in selecting the public and private exponents to ensure the
security of the encryption.
 Cryptography and Modular Arithmetic:
Euler's totient function plays a crucial role in modular arithmetic, especially in situations
where finding the modular multiplicative inverse is important. For a given modulus n, the
value ϕ(n) represents the count of positive integers less than n that are coprime to ‘n’. This
property is utilized in various cryptographic algorithms.
 Coprime Generation:
ϕ(n) helps in generating a set of numbers that are coprime ton. This is useful in applications
such as generating public and private keys in cryptography or finding numbers relatively
prime to a given modulus.
 Number Theory and Counting:
Euler's totient function is often used in number theory to count the number of positive
integers less than or equal to n that are coprime to n. It provides valuable information about
the distribution of coprime numbers.
 Group Theory:
In group theory, ϕ(n) is related to the number of elements in the multiplicative group of
integers modulo n. This connection is fundamental in understanding the properties of these
groups.
 Primitive Roots:
Euler's totient function is involved in the study of primitive roots. The number of primitive
roots modulo n is given by ϕ(ϕ(n)). Primitive roots have applications in various areas,
including number theory and cryptography.
 Carmichael Function:
The Carmichael function (λ) is related to Euler's totient function. It is used in certain
cryptographic algorithms and has applications in determining the least common multiple of
certain numbers.
 Public-Key Cryptography and Diffie-Hellman Key Exchange:
Euler's totient function is related to the security of public-key cryptographic systems, and it
plays a role in the Diffie-Hellman key exchange protocol, which allows two parties to
securely agree on a shared secret key over an untrusted communication channel.