MODULE 1.

DIVISIBILITY AND PRIMES Lecture 6

1.6 Lecture 6

Preamble: In this lecture we will discuss how primes are distributed amongst the set
of natural numbers.

Keywords: prime number theorem, Goldbach conjecture, twin prime conjecture

1.6.1 Prime Number Theorem

One way to look at how prime numbers are distributed is to count the number of integers
not exceeding a real number x. This gives us a function, which we denote by π(x). By
definition,
π(x) = #{p ≤ x | p is a prime} x ∈ R.

For example, π(9.5) = 4. The Prime Number Theorem tells us about the asymptotic
behavior of π(x), i.e., the behavior of π(x) as a function when x is very large. Gauss,
one of the most influential mathematician, conjectured in 1793 that the value of π(x) is
very close to the value of the more familiar function
 x
dt
li(x) =
2 log t

in the sense that

π(x)
→ 1 as x → ∞.
li(x)
This was later proved by by Hadamard and de la Valleé Poussin in 1896, and is known as
the Prime Number Theorem. The proof is beyond the scope of these notes. By applying
l’Hospital’s rule, one can observe that

li(x)
lim = 1.
x→∞ x/ log x

The Prime number theorem can be restated as

π(x)
→ 1 as x → ∞,
x/ log x

and interpreted as showing that the proportion π(x) x of primes amongst the positive
integers n ≤ x is approximately log x for large x. Since log1 x → 0 as x → ∞, the theorem
1

says that the primes occur less and less frequently among larger integers.

20
MODULE 1. DIVISIBILITY AND PRIMES Lecture 6

1.6.2 Conjectures about Primes

There are many open questions and “conjectures” involving primes. A conjecture is a
statement for which there is enough evidence but which is not still proved mathemati-
cally. Twin prime conjecture is one such famous conjectures involving primes.

DEFINITION 1.30. If p is a prime number such that p + 2 is also a prime, then p and
p + 2 are called twin primes.

The Twin Prime Conjecture: There are infinitely many twin primes.I.e., there are
infinitely many pairs of primes such as (3, 5), (5, 7), (11, 13), . . ..

A more general conjecture is Polignac’s conjecture, which states that for any posi-
tive integer n there are infinitely many primes p such that p + 2n is also a prime. The
twin-prime conjecture is a special case of Polignac’s conjecture with n = 1.

Another unanswered question involves the Fibonacci sequence Fn , which is defined as

F0 = 1, F1 = 1, F2 = 1 + 1 = 2, Fn = Fn−1 + Fn−2 for n ≥ 2. The question whether
there are infinitely many primes in the Fibonacci sequence is still open.

Bertrand Conjecture: For each natural number n ≥ 2, there exists a prime number
p such that p lies between n and 2n.

The above conjecture has been verified up to large values by Bertrand, who formulated
it in 1845. It was proved by Tchebysheff in 1852. As a consequence of this conjecture,
one can show that the n-th prime does not exceed 2n for n ≥ 2.

THEOREM 1.31. If pn denotes the n-th prime, then pn < 2n for n ≥ 2.

Proof: We use induction on n. The assertion is clear for n = 2. Assume it is true for
n = k ≥ 2. Then, by Bertrand’s conjecture there is a prime p such that 2k < p < 2k+1 .
Then, pk < p. Therefore, we have found a prime bigger than the first k primes which is
less than 2k+1 . 

21
MODULE 1. DIVISIBILITY AND PRIMES Lecture 6

1.6.3 Goldbach Conjecture

Goldbach Conjecture: Any even number greater than 4 can be expressed as a sum
of two odd primes.

For example, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 + 5 etc. One can take as large an even

number as possible and find two primes of which the given number is a sum. However, a
proof has been elusive for more than 240 years, since Goldbach first put this question to
Euler, who was one of the leading mathematicians of that era. A similar open question
is that any even number can be written as the difference of two primes, for example,
2 = 5 − 3, 4 = 7 − 3, 6 = 11 − 5, · · · etc.

Note that if Goldbach conjecture is true, then any odd integer n > 7 will be a sum of
three odd primes: n − 3 is an even integer bigger than 4, hence n − 3 = p1 + p2 for two
odd primes p1 and p2 by Goldbach conjecture and n = 3 + p1 + p2 . In a major progress,
Hardy and Littlewood showed that under another conjecture (known as the Riemann
Hypothesis , which we will allude to towards the final lectures) every sufficiently large
odd integer can be expressed as the sum of three odd primes. It has also been proved
that ‘almost all’ even integers satisfy Goldbach conjecture in the following sense: if g(x)
is the number of even integers n not exceeding a real number x such that n does not
satisfy the Goldbach Conjecture, then

g(x)
lim = 0.
x→∞ x
However, note that the above result does not rule out the possibility that there still may
be infinitely many even integers which are not expressible as sum of two primes. The
vanishing of the above limit merely says that such occurrence will be very rare.

22
Module 2

Congruence

2.1 Lecture 1

Preamble: In this lecture we will introduce the notion of congruence. We will show
that for any integer n, congruence modulo n is an equivalence relation on the set Z
of integers. We will define complete and reduced system of residues. We will deduce
divisibility criterion for 9 and 11 as a simple application of the notion of congruence.

Keywords: congruence, equivalence relation, residues, reduced residues

2.1.1 Congruence

DEFINITION 2.1. Let n be any non-zero integer. Define a relation

≡ mod n

on Z by
a ≡ b mod n if and only if n | (a − b).

For example,
12 ≡ 3 mod 9, 31 ≡ 6 mod 5.

PROPOSITION 2.2. The relation ‘≡ modulo n’ is an equivalence relation.

Proof: We have to show that the relation is

26
MODULE 2. CONGRUENCE Lecture 1

1. reflexive (i.e., every integer is related to itself),

2. symmetric (i.e., if a is related to b then b is related to a), and

3. transitive (i.e., if a is related to b, and b is related to c, then a is related to c).

Now,

• a ≡ a modulo n ∀a ∈ Z as n | (a − a).

• a ≡ b modulo n implies b ≡ a modulo n as

n | (a − b) =⇒ n | (b − a) ∀a, b ∈ Z.

• a ≡ b modulo n and b ≡ c modulo n imply a ≡ c modulo n, as

 
n | (a − b), n | (b − c) =⇒ n | (a − b) + (b − c) ∀a, b, c ∈ Z. 

DEFINITION 2.3. The equivalence class of an integer a, denoted by [a], is referred to as

the congruence class or residue class of a. Thus,

[a] = {b ∈ Z | b ≡ a mod n}.

It is enough to consider positive modulus, as

n | (a − b) ⇔ (−n) | (a − b).

Henceforth we will consider n to be a positive integer.

PROPOSITION 2.4. a ≡ b mod n if and only if they leave the same remainder upon
division by n.

Proof: By division algorithm , we can write

a = nq + r, 0 ≤ r ≤ n − 1,
b = nl + r, 0≤s≤n−1
=⇒ (a − b) = n(p − l) + (r − s).

If r = s, it is clear from the last line that n divides a − b. Conversely, if a ≡ b mod n,

that the last step above tells us that n | (r − s). But

0 ≤ r ≤ n − 1, 0≤s≤n−1
=⇒ −(n − 1) ≤ (r − s) ≤ (n − 1).

27
MODULE 2. CONGRUENCE Lecture 1

Hence n | (r − s) implies r − s = 0. 

The following corollary is obvious from the proposition.

COROLLARY 2.5. If a leaves the remainder r upon division by n then a and r are in
the same congruence class modulo n, i.e., [a] = [r].

COROLLARY 2.6. For any integer n, there are n distinct congruence classes modulo n.

Proof: The only possible remainders upon division by n are 0, 1, · · · , n − 1. So any

integer a must be congruent to one of these n remainders. So the number of congruence
classes is not more than n. Any two distinct remainders in the above list can not be
equivalent by proposition 2.4. Hence the corollary follows. .

DEFINITION 2.7. A set of congruence classes is called a complete residue system if any
given integer belongs to one of the congruence classes in the set.

Thus, the set {[0], [1], · · · , [n − 1]} is an example of a complete residue system for n.
This complete residue system of n is usually denoted by Zn .

2.1.2 Properties of Congruence

Congruence modulo n has many interesting properties which simplify a lot of computa-
tions. Some of these properties are listed below.

1. x ≡ y mod n =⇒ x + c ≡ y + c mod n ∀c ∈ Z.

2. x ≡ y mod n, z ≡ w mod n =⇒ xz ≡ yw mod n ∀c ∈ Z.

3. x ≡ y mod n =⇒ cx ≡ cy mod n ∀c ∈ Z.

4. x ≡ y mod n =⇒ xk ≡ y k mod n ∀k ∈ N.

5. x ≡ y mod n =⇒ f (x) ≡ f (y) mod n for any polynomial f (x) with integer
coefficients.

6. x ≡ y mod n =⇒ x ≡ y mod d for any divisor d of n.

n
7. ax ≡ ay mod n =⇒ x ≡ y mod gcd(a,n) .

8. ax ≡ ay mod n =⇒ x ≡ y mod n if gcd(a, n) = 1.

28
MODULE 2. CONGRUENCE Lecture 1

9. x ≡ y mod mi =⇒ x ≡ y mod lcm(mi ) for positive integers m1 . · · · , mr .

The first of the above properties follow easily from definition of congruence. Observe
that a ≡ b mod n implies that we can write as a = b + nk for some integer k. For the
second property above,

x = y + nk, z = w + nl =⇒ xz = yw + n(yl + kz + nkl) ≡ yw mod n.

The third property follows from the second by taking z = w = c. The fourth property
follows from the second by taking z = x, w = y to start with, then z = x2 , w = y 2 etc.
Then the fifth is a consequence of the preceding properties. The sixth property is clear
too, as
d | n, n | (a − b) =⇒ d | (a − b).

For the seventh property, we cancel the gcd d of n = dn1 and a = da1 to obtain

n | a(x − y)
=⇒ n1 | a1 (x − y)
=⇒ n1 | (x − y).

As n1 and a1 are coprime, the last step follows from corollary 1.15 in lecture 4, module 1.
Property 8 is a special case of the seventh. The last property follows from the definition
of the lcm. 

2.1.3 Divisibility Criterion for 9 and 11

We will now demonstrate the usefulness of the notion of congruence with some simple
applications. We will derive divisibility criterion for integers 9 and 11 using congruence.

PROPOSITION 2.8. A natural number is divisible by 9 (respectively by 3) if and only if

the sum of its digits in its decimal expansion is divisible by 9 (respectively by 3).

Proof: Let m be a natural number whose decimal expansion is

m = bk · 10k + bk−1 · 10k−1 + · · · + b1 · 10 + b0 , 0 ≤ bi < 10.

and let
S = bk + bk−1 + · · · + b1 + b0 ,

29
MODULE 2. CONGRUENCE Lecture 1

Now,

10 ≡ 1 mod 9
=⇒ 10k ≡ 1 mod 9
=⇒ bk · 10k + bk−1 · 10k−1 + · · · + b1 · 10 + b0 ≡ bk + bk−1 + · · · + b1 + b0 mod 9
=⇒ m ≡ S mod 9.

Thus 9 | m if and only if 9 | S. The proof for divisibility by 3 is identical. 

PROPOSITION 2.9. A positive integer is divisible by 11 if and only if the sum of its
digits with alternate signs in its decimal expansion is divisible by 11.

Proof: Let m be an integer whose decimal expansion is

m = bk · 10k + bk−1 · 10k−1 + · · · + b1 · 10 + b0 , 0 ≤ bi < 10.

and let
A = (−1)k bk + (−1)k−1 bk−1 + · · · − b1 + b0 . Now,

10 ≡ −1 mod 11
=⇒ 10k ≡ (−1)k mod 11
=⇒ bk · 10k + bk−1 · 10k−1 + · · · + b1 · 10 + b0 ≡ (−1)k bk + (−1)k−1 bk−1 + · · · − b1 + b0 mod 11
=⇒ m ≡ A mod 11.

Thus 11 | m if and only if 11 | A. 

We leave it as an exercise now to prove that a natural umber is divisible by 4 (respec-

tively by 8) if the integer formed by the last two (respectively the last three) digits is
divisible by 4 (respectively by 8).

30