Chapter 2

Prime Numbers

Prime numbers, the building blocks of integers, have been studied extensively
over the centuries. Being able to present an integer uniquely as product of
primes is the main reason behind the whole theory of numbers and behind the
interesting results in this theory. Many interesting theorems, applications and
conjectures have been formulated based on the properties of prime numbers.
In this chapter, we present methods to determine whether a number is prime
or composite using an ancient Greek method invented by Eratosthenes. We also
show that there are infinitely many prime numbers. We then proceed to show
that every integer can be written uniquely as a product of primes.
We introduce as well the concept of diophantine equations where integer so-
lutions from given equations are determined using the greatest common divisor.
We then mention the Prime Number theorem without giving a proof of course in
addition to other conjectures and major results related to prime numbers.

2.1 The Sieve of Eratosthenes

Definition 8. A prime is an integer greater than 1 that is only divisible by 1 and
itself.

31
Example 15. The integers 2, 3, 5, 7, 11 are prime integers.

Note that any integer greater than 1 that is not prime is said to be a composite
number.

We now present the sieve of Eratosthenes. The Sieve of Eratosthenes is an

ancient method of finding prime numbers up to a specified integer. This method
was invented by the ancient Greek mathematician Eratosthenes. There are
several other methods used to determine whether a number is prime or
composite. We first present a lemma that will be needed in the proof of several
theorems.

Lemma 3. Every integer greater than one has a prime divisor.

Proof. We present the proof of this Lemma by contradiction. Suppose that there
is an integer greater than one that has no prime divisors. Since the set of integers
with elements greater than one with no prime divisors is nonempty, then by the
well ordering principle there is a least positive integer n greater than one that has
no prime divisors. Thus n is composite since n divides n. Hence

n = abwith 1 < a < nand 1 < b < n.

Notice that a < n and as a result since n is minimal, a must have a prime divisor
which will also be a divisor of n.

Theorem 12. If n is a composite integer, then n has a prime factor not exceeding
√
n.

Proof. Since n is composite, then n = ab, where a and b are integers with 1 <
√
a ≤ b < n. Suppose now that a > n, then
√
n<a≤ b

and as a result
√ √
ab > n n = n.
2.1. THE SIEVE OF ERATOSTHENES 33
√
Therefore a ≤ n. Also, by Lemma 3, a must have a prime divisor a1 which is
√
also a prime divisor of n and thus this divisor is less than a1 ≤ a ≤ n.

We now present the algorithm of the Sieve of Eratosthenes that is used to de-
termine prime numbers up to a given integer.

The Algorithm of the Sieve of Eratosthenes

1. Write a list of numbers from 2 to the largest number n you want to test.
Note that every composite integer less than n must have a prime factor less
√
than n. Hence you need to strike off the multiples of the primes that are
√
less than n

2. Strike off all multiples of 2 greater than 2 from the list . The first
remaining number in the list is a prime number.

3. Strike off all multiples of this number from the list.

4. Repeat the above steps until no more multiples are found of the prime
√
inte- gers that are less than n

Exercises

1. Use the Sieve of Eratosthenes to find all primes less than 100.

2. Use the Sieve of Eratosthenes to find all primes less than 200.

3. Show that no integer of the form a3 + 1 is a prime except for 2 = 13 + 1.

4. Show that if 2n − 1 is prime, then n is prime.

Hint: Use the identity (akl − 1) = (ak − 1)(ak(l−1) + ak(l−2) + ... + ak + 1).
2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 34

2.2 The infinitude of Primes

We now show that there are infinitely many primes. There are several ways to
prove this result. An alternative proof to the one presented here is given as an
exercise. The proof we will provide was presented by Euclid in his book the
Elements.

Theorem 13. There are infinitely many primes.

Proof. We present the proof by contradiction. Suppose there are finitely many
primes p1, p2, ..., pn, where n is a positive integer. Consider the integer Q such
that
Q = p1p2...pn + 1.

By Lemma 3, Q has at least a prime divisor, say q. If we prove that q is not one
of the primes listed then we obtain a contradiction. Suppose now that q = pi for 1
≤ i ≤ n. Thus q divides p1p2...pn and as a result q divides Q − p1p2...pn.
Therefore q divides 1. But this is impossible since there is no prime that divides
1 and as a result q is not one of the primes listed.

The following theorem discusses the large gaps between primes. It simply
states that there are arbitrary large gaps in the series of primes and that the
primes are spaced irregularly.

Theorem 14. Given any positive integer n, there exists n consecutive composite
integers.

Proof. Consider the sequence of integers

(n + 1)! + 2, (n + 1)! + 3, ..., (n + 1)! + n, (n + 1)! + n + 1

Notice that every integer in the above sequence is composite because k divides
(n + 1)! + k if 2 ≤ k ≤ n + 1 by 4.
2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 35

Exercises

1. Show that the integer Qn = n! + 1, where n is a positive integer, has a

prime divisor greater than n. Conclude that there are infinitely many
primes. Notice that this exercise is another proof of the infinitude of
primes.

2. Find the smallest five consecutive composite integers.

3. Find one million consecutive composite integers.

4. Show that there are no prime triplets other than 3,5,7.

2.3 The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic is one of the most important results in
this chapter. It simply says that every positive integer can be written uniquely as
a product of primes. The unique factorization is needed to establish much of
what comes later. There are systems where unique factorization fails to hold.
Many of these examples come from algebraic number theory. We can actually
list an easy example where unique factorization fails.
Consider the class C of positive even integers. Note that C is closed under
multiplication, which means that the product of any two elements in C is again
in
C. Suppose now that the only number we know are the members of C. Then we
have 12 = 2.6 is composite where as 14 is prime since it is not the product of two
numbers in C. Now notice that 60 = 2.30 = 6.10 and thus the factorization is not
unique.
We now give examples of the unique factorization of integers.

Example 16. 99 = 3 · 3 · 11 = 32 · 11, 32 = 2 · 2 · 2 · 2 · 2 = 25

2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 36

2.3.1 The Fundamental Theorem of Arithmetic

To prove the fundamental theorem of arithmetic, we need to prove some lemmas

about divisibility.

Lemma 4. If a,b,c are positive integers such that (a, b) = 1 and a | bc, then a | c.

Proof. Since (a, b) = 1, then there exists integers x, y such that ax + by = 1. As a

result, cax + cby = c. Notice that since a | bc, then by Theorem 4, a divides cax
+ cby and hence a divides c.

We can generalize the above lemma as such: If (a,ni) = 1 for every i = 1,

2, · · · , n and a | n1n2 · · · nk+1, then a | nk+1. We next prove a case of this
generalization and use this to prove the fundamental theorem of arithmetic.

Lemma 5. If p divides n1n2n3...nk, where p is a prime and ni > 0 for all 1 ≤

i ≤ k, then there is an integer j with 1 ≤ j ≤ k such that p | nj.

Proof. We present the proof of this result by induction. For k = 1, the result is
trivial. Assume now that the result is true for k. Consider n1n2...nk+1 that is
divisible by p. Notice that either

(p, n1n2...nk) = 1 or (p, n1n2...nk) = p.

Now if (p, n1n2...nk) = 1 then by Lemma 4, p | nk+1. Now if p | n1n2...nk, then by

the induction hypothesis, there exists an integer i such that p | ni.

We now state the fundamental theorem of arithmetic and present the proof
using Lemma 5.

Theorem 15. The Fundamental Theorem of Arithmetic Every positive integer

different from 1 can be written uniquely as a product of primes.
2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 37

Proof. If n is a prime integer, then n itself stands as a product of primes with a

single factor. If n is composite, we use proof by contradiction. Suppose now that
there is some positive integer that cannot be written as the product of primes.
Let n be the smallest such integer. Let n = ab, with 1 < a < n and 1 < b < n.
As a result a and b are products of primes since both integers are less than n. As
a result, n = ab is a product of primes, contradicting that it is not. This shows
that every integer can be written as product of primes. We now prove that the
representation of a positive integer as a product of primes is unique. Suppose
now that there is an integer n with two different factorizations say
n = p1p2...ps = q1q2...qr
where p1, p2, ...ps, q1, q2, ...qr are primes,
p1 ≤ p2 ≤ p3 ≤ ... ≤ psand q1 ≤ q2 ≤ q3 ≤ ... ≤ qr.

Cancel out all common primes from the factorizations above to get
pj1 pj2 ...pju = qi1 qi2 ...qiv

Thus all the primes on the left side are different from the primes on the right
side. Since any pjl (l = 1, · · · , n) divides pj1 pj2 ...pju , then pjl must divide qi1
qi2 ...qiv , and hence by Lemma 5, pj1 must divide qjk for some 1 ≤ k ≤ v
which is impos- sible. Hence the representation is unique.

Remark 1. The unique representation of a positive integer n as a product of

primes can be written in several ways. We will present the most common rep-
resentations. For example, n = p1p2p3...pk where pi for 1 ≤ i ≤ k are not
necessarily distinct. Another example would be
j
n = pa1 pa2 pa3 ...pa (2.1)
1 2 3 j

where all the pi are distinct for 1 ≤ i ≤ j. One can also write a formal product
Y
n= pαi i , (2.2)
all primes pi
2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 38

where all but finitely many of the αiJ s are 0.

Example 17. The prime factorization of 120 is given by 120 = 2·2·2·3·5 =

23·3·5. Notice that 120 is written in the two ways described in 1.

We know describe in general how prime factorization can be used to

determine the greatest common divisor of two integers. Let

a = pa1 pa2 ...pan and b = pb1 pb2 ...pbn,

1 2 n 1 2 n

where we exclude in these expansions any prime p with power 0 in both a and b
(and thus some of the powers above may be 0 in one expansion but not the
other). Of course, if one prime pi appears in a but not in b, then ai =ƒ 0 while bi
= 0, and vise versa. Then the greatest common divisor is given by

min(a1,b2) min(a2,b2)
(a, b) = p 1 p 2 ...pmin(ann,bn)

where min(n, m) is the minimum of m and n.

The following lemma is a consequence of the Fundamental Theorem of
Arith- metic.

Lemma 6. Let a and b be relatively prime positive integers. Then if d divides ab,
there exists d1 and d2 such that d = d1d2 where d1 is a divisor of a and d2 is a
divisor of b. Conversely, if d1 and d2 are positive divisors of a and b,
respectively, then d = d1d2 is a positive divisor of ab.

Proof. Let d1 = (a, d) and d2 = (b, d). Since (a, b) = 1 and writing a and b in
terms of their prime decomposition, it is clear that d = d1d2 and (d1, d2) = 1. Note
that every prime power in the factorization of d must appear in either d1 or d2.
Also the prime powers in the factorization of d that are prime powers dividing a
must appear in d1 and that prime powers in the factorization of d that are prime
powers dividing b must appear in d2.
2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 39

Now conversely, let d1 and d2 be positive divisors of a and b, respectively.

Then
d = d1d2

is a divisor of ab.

2.3.2 More on the Infinitude of Primes

There are also other theorems that discuss the infinitude of primes in a given
arith- metic progression. The most famous theorem about primes in arithmetic
progres- sion is Dirichlet’s theorem

Theorem 16. Dirichlet’s Theorem Given an arithmetic progression of terms

an+ b , for n = 1, 2, ... ,the series contains an infinite number of primes if a and
b are relatively prime,

This result had been conjectured by Gauss but was first proved by Dirichlet.
Dirichlet proved this theorem using complex analysis, but the proof is so chal-
lenging. As a result, we will present a special case of this theorem and prove that
there are infinitely many primes in a given arithmetic progression. Before stating
the theorem about the special case of Dirichlet’s theorem, we prove a lemma
that will be used in the proof of the mentioned theorem.

Lemma 7. If a and b are integers both of the form 4n + 1, then their product ab
is of the form 4n + 1

Proof. Let a = 4n1 + 1 and b = 4n2 + 1, then

ab = 16n1n2 + 4n1 + 4n2 + 1 = 4(4n1n2 + n1 + n2) + 1 = 4n3 + 1,

where n3 = 4n1n2 + n1 + n2.

Theorem 17. There are infinitely many primes of the form 4n + 3, where n is a
positive integer.
2.3. THE FUNDAMENTAL THEOREM OF ARITHMETIC 40

Proof. Suppose that there are finitely many primes of the form 4n + 3, say p0 =
3, p1, p2, ..., pn. Let
N = 4p1p2...pn + 3.

Notice that any odd prime is of the form 4n + 1 or 4n + 3. Then there is at least
one prime in the prime factorization of N of the form 4n + 3, as otherwise, by
Lemma 7, N will be in the form 4n + 1. We wish to prove that this prime in the
factorization of N is none of p0 = 3, p1, p2, ..., pn. Notice that if

3 | N,

then 3 | (N − 3) and hence

3 | 4p1p2...pn

which is impossible since pi ƒ= 3 for every i. Hence 3 doesn’t divide N . Also, the
other primes p1, p2, ..., pn don’t divide N because if pi | N , then

pi | (N − 4p1p2...pn) = 3.

Hence none of the primes p0, p1, p2, ..., pn divides N. Thus there are infinitely
many primes of the form 4n + 3.

Exercises

1. Find the prime factorization of 32, of 800 and of 289.

2. Find the prime factorization of 221122 and of 9!.

3. Show that all the powers of in the prime factorization of an integer a are
even if and only if a is a perfect square.

4. Show that there are infinitely many primes of the form 6n + 5.

2.4. LEAST COMMON MULTIPLE 41

2.4 Least Common Multiple

We can use prime factorization to find the smallest common multiple of two pos-
itive integers.

Definition 9. The least common multiple (l.c.m.) of two positive integers is the
smallest positive integer that is a multiple of both.

We denote the least common multiple of two positive integers a an b by (a, b).

Example 18. (2, 8) = 8, (5, 8) = 40

We can figure out (a, b) once we have the prime factorization of a and b. To
do that, let
a = pa1 pa2 ...pan and b = pb1 pb2 ...pbn,
1 2 m 1 2 m

where (as above) we exclude any prime with 0 power in both a and b. Then
max(a1,b1) max(a2,b2) max(an,bn)
(a, b) = p1 p2 ...pm , where max(a, b) is the maximum of
the two integers a and b. We now prove a theorem that relates the least common
multiple of two positive integers to their greatest common divisor. In some
books, this theorem is adopted as the definition of the least common multiple.
To prove the theorem we present a lemma

Lemma 8. If a and b are two real numbers, then

min(a, b) + max(a, b) = a + b

Proof. Assume without loss of generality that a ≥ b. Then

max(a, b) = a and min(a, b) = b,

and the result follows.

Theorem 18. Let a and b be two positive integers. Then

1. (a, b) ≥ 0;
2.5. LINEAR DIOPHANTINE EQUATIONS 42

2. (a, b) = ab/(a, b);

3. If a | m and b | m, then (a, b) | m

Proof. The proof of part 1 follows from the definition.

As for part 2, let
a = pa1 pa2 ...pan and b = pb1 pb2 ...pbn.
1 2 m 1 2 m

Notice that since

min(a1,b2) min(a2,b2)
(a, b) = p 1 p 2 ...pmin(ann,bn)

and
max(a1,b1) max(a2,b2)
max(an,bn)
(a, b) = p1 p2 ...pm ,
then
max(a1,b1) max(a2,b2) max(an,bn) min(a1,b2) min(a2,b2) min(an,bn)
(a, b)(a, b) = p1 p2 ...pm p1 p2 ...pn
max(a1,b1)+min(a1,b1) max(a2,b2)+min(a2,b2)
1= p p2 ...pmax(a
m
n,bn)+min(an,bn)

= pa1+b
1
1 a2+b2
p 2 ...p(an+b n
n)

= pa1 pa2 ...panpb1 pb2 ...pbn = ab

1 2 m 1 2 m

Note also that we used Lemma 8 in the above equations. For part 3, it would be a
nice exercise to show that ab/(a, b) | m (Exercise 6). Thus (a, b) | m.

Exercises

1. Find the least common multiple of 14 and 15.

2. Find the least common multiple of 240 and 610.

3. Find the least common multiple and the greatest common divisor of 25567211
and 23587213.

4. Show that every common multiple of two positive integers a and b is

divis- ible by the least common multiple of a and b.
2.5. LINEAR DIOPHANTINE EQUATIONS 43

5. Show that if a and b are positive integers then the greatest common
divisor of a and b divides their least common multiple. When are the least
common multiple and the greatest common divisor equal to each other.

6. Show that ab/(a, b) | m where m =< a, b >.

2.5 Linear Diophantine Equations

In this section, we discuss equations in two variables called diophantine
equations. These kinds of equations require integer solutions. The goal of this
section is to present the set of points that determine the solution to this kind of
equations. Geo- metrically speaking, the diophantine equation represent the
equation of a straight line. We need to find the points whose coordinates are
integers and through which the straight line passes.

Definition 10. A linear equation of the form ax + by = c where a, b and c are

integers is known as a linear diophantine equation.

Note that a solution to the linear diophantine equation (x0, y0) requires x0 and
y0 to be integers. The following theorem describes the case in which the
diophantine equation has a solution and what are the solutions of such equations.

Theorem 19. The equation ax + by = c has integer solutions if and only if d | c

where d = (a, b). If the equation has one solution x = x0, y = y0, then there are
infinitely many solutions and the solutions are given by

x = x0 + (b/d)t y = y0 − (a/d)t

where t is an arbitrary integer.

Proof. Suppose that the equation ax + by = c has integer solution x and y. Thus
since d | a and d | b, then
d | (ax + by) = c.
2.5. LINEAR DIOPHANTINE EQUATIONS 44

Now we have to prove that if d | c, then the equation has integral solution.
Assume that d | c. By theorem 9, there exist integers m and n such that

d = am + bn.

And also there exists integer k such that

c = dk

Now since c = ax + by, we have

c = dk = (ma + nb)k = a(km) + b(nk).

Hence a solution for the equation ax + by = c is

x0 = km and y0 = kn.

What is left to prove is that we have infinitely many solutions. Let

x = x0 + (b/d)t and y = y0 − (a/d)t.

We have to prove now that x and y are solutions for all integers t. Notice that

ax + by = a(x0 + (b/d)t) + b(y0 − (a/d)t) = ax0 + by0 = c.

We now show that every solution for the equation ax + by = c is of the form

x = x0 + (b/d)tand y = y0 − (a/d)t.

Notice that since ax0 + by0 = c, we have

a(x − x0) + b(y − y0) = 0.

Hence
a(x − x0) = b(y − y0).
2.5. LINEAR DIOPHANTINE EQUATIONS 45

Dividing both sides by d, we get

a/d(x − x0) = b/d(y − y0).

Notice that (a/d, b/d) = 1 and thus we get by Lemma 4 that a/d | y − y0. As a
result, there exists an integer t such that y = y0 − (a/d)t. Now substituting y − y0
in the equation
a(x − x0) = b(y − y0).

We get
x = x0 + (b/d)t.

Example 19. The equation 3x+6y = 7 has no integer solution because (3, 6) = 3
does not divide 7.
Example 20. There are infinitely many integer solutions for the equation 4x +
6y = 8 because (4, 6) = 2 | 8. We use the Euclidean algorithm to determine m
and n where 4m + 6n = 2. It turns out that 4(−1) + 6(1) = 2. And also 8 = 2.4.
Thus x0 = 4.(−1) = −4 and y0 = 4.1 = 4 is a particular solution. The solutions
are given by
x = −4 + 3t y = 4 − 2t
for all integers t.

Exercises

1. Either find all solutions or prove that there are no solutions for the
diophan- tine equation 21x + 7y = 147.

2. Either find all solutions or prove that there are no solutions for the
diophan- tine equation 2x + 13y = 31.

3. Either find all solutions or prove that there are no solutions for the
diophan- tine equation 2x + 14y = 17.
2.5. LINEAR DIOPHANTINE EQUATIONS 46

4. A grocer orders apples and bananas at a total cost of $8.4. If the apples
cost 25 cents each and the bananas 5 cents each, how many of each type of
fruit did he order.

2.6 The function [x] , the symbols ”O”, ”o” and ”∼”
We start this section by introducing an important number theoretic function. We
proceed in defining some convenient symbols that will be used in connection
with the growth and behavior of some functions that will be defined in later
chapters.

2.6.1 The Function [x]

.

Definition 11. The function [x] represents the largest integer not exceeding x. In
other words, for real x, [x] is the unique integer such that

x − 1 < [x] ≤ x < [x] + 1.

We also define ((x)) to be the fractional part of x. In other words ((x)) =

x − [x].
We now list some properties of [x] that will be used in later or in more advanced
courses in number theory.

1. [x + n] = [x] + n, if n is an integer.

2. [x] + [y] ≤ [x + y].

3. [x] + [−x] is 0 if x is an integer and -1 otherwise.

4. The number of integers m for which x < m ≤ y is [y] − [x].

2.6. THE FUNCTION [X] , THE SYMBOLS ”O”, ”O” AND ”∼” 47

5. The number of multiples of m which do not exceed x is [x/m].

Using the definition of [x], it will be easy to see that the above properties are
direct consequences of the definition.
We now define some symbols that will be used to estimate the growth of number
theoretic functions. These symbols will be not be really appreciated in the
context of this book but these are often used in many analytic proofs.

2.6.2 The ”O” and ”o” Symbols

Let f (x) be a positive function and let g(x) be any function. Then O(f (x))
(pro- nounced ”big-oh” of f (x))denotes the collection of functions g(x) that
exhibit a growth that is limited to that of f (x) in some respect. The
traditional notation for stating that g(x) belongs to this collection is:

g(x) = O(f (x)).

This means that for sufficiently large x,

| g(x) |
< M, (2.3)
|f (x)|
where M is some positive number.

Example 21. sin(x) = O(x), and also sin(x) = O(1).

Now, the relation g(x) = o(f (x)), pronounced ”small-oh” of f (x), is used
to indicate that f (x) grows much faster than g(x). It formally says that
g(x)
lim = 0. (2.4)
x→∞ f
(x)
More generally, g(x) = o(f (x)) at a point b if
g(x)
lim = 0. (2.5)
x→b f
(x)
Example 22. sin(x) = o(x) at ∞, and xk = o(ex) also at ∞ for every constant
k.

The notation that f (x) is asymptotically equal to g(x) is denoted by ∼.

For- mally speaking, we say that f (x) ∼ g(x) if
f (x)
lim = 1. (2.6)
x→∞ g(x)
Example 23. [x] ∼ x.

The purpose of introducing these symbols is to make complicated mathemat-

ical expressions simpler. Some expressions can be represented as the principal
part that you need plus a remainder term. The remainder term can be expressed
using the above notations. So when you need to combine several expressions,
the remainder parts involving these symbols can be easily combined. We will
state now some properties of the above symbols without proof. These properties
are easy to prove using the definitions of the symbols.

1. O(O(f (x))) = O(f (x)),

2. o(o(f (x))) = o(f (x)).

3. O(f (x)) ± O(f (x)) = O(f (x)),

4. o(f (x) ± o(f (x)) = o(f (x)),

5. O(f (x)) ± O(g(x)) = O(max(f (x), g(x))),

There are some other properties that we did not mention here, properties that are
rarely used in number theoretic proofs.
Exercises

1. Prove the five properties of the [x]

2. Prove the five properties of the O and o notations in Example 24.

2.7. THEOREMS AND CONJECTURES INVOLVING PRIME NUMBERS 49

2.7 Theorems and Conjectures involving prime

num- bers
We have proved that there are infinitely many primes. We have also proved that
there are arbitrary large gaps between primes. The question that arises naturally
here is the following: Can we estimate how many primes are there less than a
given number? The theorem that answers this question is the prime number
theorem. We denote by π(x) the number of primes less than a given positive
number x. Many mathematicians worked on this theorem and conjectured many
estimates before Chebyshev finally stated that the estimate is x/logx. The prime
number theorem was finally proved in 1896 when Hadamard and Poussin
produced independent proofs. Before stating the prime number theorem, we
state and prove a lemma involving primes that will be used in the coming
chapters.

Lemma 9. Let p be a prime and let m ∈ Z+. Then the highest power of p dividing
m! is
Σ∞ Σ
m
Σ pi
i=1
Σ Σ
Proof. Among all the integers from 1 till m, there are exactly m integers that
Σ Σ p Σ
m
are divisible by p. These are p, 2p, ..., p p. Similarly we see that there are
Σ p
i
m

integers that are divisible by pi. As a result, the highest power of p dividing m! is
Σ .Σ m Σ Σ
m
ΣΣ Σ Σ Σ
m
i − i+1 =
i≥1 p p i≥1 p
i i

Theorem 20. The Prime Number Theorem Let x > 0 then

π(x) ∼ x/logx
 So this theorem says that you do not need to find all the primes less than x to
find out their number, it will be enough to evaluate x/logx for large x to find an
estimate for the number of primes. Notice that I mentioned that x has to be large
enough to be able to use this estimate.
Several other theorems were proved concerning prime numbers. many great
mathematicians approached problems that are related to primes. There are still
many open problems of which we will mention some.

Conjecture 1. Twin Prime Conjecture There are infinitely many pairs primes p
and p + 2.

Conjecture 2. Goldbach’s Conjecture Every even positive integer greater than 2

can be written as the sum of two primes.

Conjecture 3. The n2 + 1 Conjecture There are infinitely many primes of the

form n2 + 1, where n is a positive integer.

Conjecture 4. Polignac Conjecture For every even number 2n are there

infinitely many pairs of consecutive primes which differ by 2n.

Conjecture 5. Opperman Conjecture Is there always a prime between n2 and

(n + 1)2?