Discrete Mathematics lecture notes pdf free download
Lecture Notes on Discrete Mathematics
A K Lal S Pati
November 20, 2016
Basic Set Theory
1.1 Common Notations
The following are some notations we shall follow throughout this document.
N : the set of natural numbers
N : the setN∪0, called the set of whole numbers
Z : the set of integers
Q : the set of rational numbers
R : the set of real numbers
n : the set1,2,...,n
A : the complement of a set A in some set that will be clear from the context
P(A) : the power set of A
A×B : the cartesian product of A and B
∅ : the empty set
pa : the integer p divides the integer a
We expect the readers to have familiarity with the following deﬁnitions.
Deﬁnition 1.2.1. Let A and B be two sets.
1. Subset of a set If C is a set such that each element of C is also an element of A, then
C is said to be a subset of the set A, denoted C⊆A.
2. Equality of sets The sets A and B are said to be equal if A⊆ B and B⊆A, denoted
3. Cartesian product of sets The cartesian product of A and B, denoted A×B, is the
set of all ordered pairs (a,b), where a∈ A and b∈ B. Speciﬁcally, A×B =(a,b) a∈
4. Set complement Let C⊆ A. The complement of C in A, denoted C , is a set that
containseveryelementofAthatisnotanelementofC. Speciﬁcally,C =x∈Ax6∈C.
DRAFT8 CHAPTER 1. BASIC SET THEORY
5. Set union Theunion of A andB, denoted A∪B, is the set that exactly contains all the
elements of A and all the elements of B. Speciﬁcally, A∪B =xx∈A or x∈B.
6. Set intersection The intersection of A and B, denoted A∩B, is the set that only
contains the common elements of A and B. Speciﬁcally, A∩B =x x∈A and x∈B.
The set A and B are said to be disjoint if A∩B =∅.
7. Set diﬀerence Theset diﬀerence of A and B, denoted A\B, is a set that contains all
those elements of A which are not in B. Speciﬁcally, A\B =x∈Ax6∈B.
8. Symmetric diﬀerence The symmetric diﬀerence of A and B, denoted AΔB, equals
Example 1.2.2. Let A=b,c,b,c,b and B =a,b,c. Then
1. A∩B =b,
2. A∪B =a,b,c,b,c,b,c,
3. A\B =b,c,b,c,
4. B\A=a,c, and
5. AΔB =b,c,b,c,a,c.
The following are a few well known facts. The readers are supposed to verify them for clarity.
Fact 1.2.3. 1. For any set A, we have A⊆A and∅⊆A.
2. If A⊆B then it is not necessary that B⊆A.
3. For any set A and B, the sets A\B, A∩B and B\A are pairwise disjoint. Thus, A∪B
is their disjoint union. That is,
A∪B = (A\B)∪(A∩B)∪(B\A). (1.1)
4. For any setA andB, thesets A\B andA∩B are disjoint. Thus,A is their disjoint union.
A= (A\B)∪(A∩B) (1.2)
5. If B⊆A, then A= (A\B)∪B (follows from (1.2)).
6. AΔB = (A∪B)\(A∩B) (follows from (1.1) and Item 3).
Deﬁnition 1.2.4. Power set Let A be a set and B⊆ A. Then, the set that contains all
subsets of B is called the power set of B, denotedP(A).
Example 1.2.5. 1. Let A =∅. Then,P(∅) =∅,A =∅.
2. Let A =∅. Then,P(A) =∅,A =∅,∅.
3. Let A =a,b,c. Then,P(A) =∅,a,b,c,a,b,a,c,b,c,a,b,c.
DRAFT1.2. PRELIMINARIES 9
4. LetA =b,c,b,c. Then,P(A) =∅,b,c,b,c,b,c,b,c.
Deﬁnition 1.2.6. Relation, domain set and codomain set Let A and B be two sets. A
relation f from A to B, denoted f : A→ B, is a subset of A×B. The set A is called the
domain set and the set B is called the codomain set. Thus, for any sets A and B the sets∅
and A×B are always relations from A to B.
Example 1.2.7. Let A = 3, B =a,b,c and f =(1,a),(1,b),(2,c). Then, f :A→B is a
relation. We can draw a picture for f.
Deﬁnition 1.2.8. 1. Domain, range and inverse relation Let f : A→ B be a relation.
f wemeanthesetrngf:=b (x,b)∈f. Theinverseoff isf :=(y,x) (x,y)∈f.
Notice that f is a relation from B to A. For example, the relation f in Example 1.2.7
has domf =1,2, rngf =a,b,c and f =(a,1),(b,1),(c,2).
2. Pre-imageandimage Letf :A→B bearelationand(x,y)∈f. Wecallxapre-image
of y and y an image of x. Also, for any set X, we deﬁne f(X) :=y(x,y)∈f,x∈X.
Thus, f(X)=∅ if X∩A=∅. We write f(x) to mean f(x). We write f(x)=y to mean
that f(x)=y. For example, consider the relation f in Example 1.2.7. Then,
(a) f(1) =a,b, f(2) =c and f(3) =∅.
−1 −1 −1 −1
(b) f (c) = 2, f (b) = 1, f (1) =∅, f (4) =∅.
(c) for X =1,4,c, one has f(X) =a,b and f (X) =2.
Deﬁnition 1.2.9. Single valued relation and function A relation f : A→ B is single
valued if f(x) is a singleton, for each a∈ domf. A function f from A to B is a single valued
relation such that domf = A. Henceforth, for any function f, we assume that domf =6 ∅.
For example, the relation f in Example 1.2.7 is not single valued. However, if we delete (1,a)
from f, then it is single valued. Moreover, to make f a function from A to B, we need to
add either (3,a), or (3,b), or (3,c). In particular, the relations g =(1,b),(2,c),(3,b) and
g =(1,b),(2,c),(3,a) are indeed functions.
The following is an immediate consequence of the deﬁnition.
We use pictures to help our understanding and they are not parts of proof.
The domain set is the setfrom which we deﬁneourrelations butdomf is the domain oftheparticular relation
f. They are diﬀerent.
DRAFT10 CHAPTER 1. BASIC SET THEORY
Proposition 1.2.10. Let f :A→B be a relation and S be any set. Then,
1. f(S)6=∅⇔ dom(f)∩S =6 ∅.
2. f (S) =6 ∅⇔ rng(f)∩S6=∅.
Proof. We will prove only one way implication. The other way is left for the reader.
Part 1: Since f(S)6=∅, one can ﬁnd a∈ S∩A and b∈ B such that (a,b)∈ f. This, in turn,
implies that a∈ dom(f). As a∈S, a∈ dom(f)∩S.
Part 2: Since rng(f)∩S6=∅, one can ﬁndb∈ rng(f)∩S and a∈A such that (a,b)∈f. This,
in turn, implies that a∈f (b)⊆f (S) as b∈S.
Deﬁnition 1.2.11. One-one/Injection A function f :A→B is called one-one (also called
aninjection), iff (b)≤ 1, for each b∈B. Equivalently, f :A→B is one-one iff(x)6=f(y)
is true, foreach pairx6=y inA. Equivalently, f is one-one ifx =y is true, for each pairx,y∈A
Let p(x) be a polynomial in x with integer coeﬃcients. Then, by writing ‘f : Z→ Z is
a function deﬁned by f(x) = p(x)’, we mean the function f =(a,p(a)) a∈ Z. For
example, the function f(x) =x stands for the set(a,a )a∈Z.
Example 1.2.12. 1. InDeﬁnition1.2.9, thefunctiong isone-onewhereasg isnotone-one.
2. The function f :Z→Z deﬁned by f(x)=x is not one-one.
3. The function f :N→N deﬁned by f(x)=x is one-one.
4. The function f : 3→a,b,c,d deﬁned by f(1) = c, f(2) = b and f(3) = a, is one-one.
Verify that there are 24 one-one functions f :3→a,b,c,d.
5. Let∅ =6 A(B. Then, f(x)=x is a one-one map from A to B.
6. There is no one-one function from the set 3 to its proper subset 2.
7. There are one-one functions f from the setN to its proper subset2,3,.... One of them
is given by f(1) = 3, f(2) = 2 and f(n)=n+1, for n≥ 3.
Deﬁnition 1.2.13. Restriction function Let f : X→ Y be a function and A⊆ X, A =6 ∅.
Then, by f we mean the restriction of f to A and denote it byf . That is, f =(x,y)
A A A
Example 1.2.14. Deﬁne f :R→R as f(x) = 1 if x is irrational and f(x) = 0 if x is rational.
Then, f :Q→R is the constant 0 function. That is, f (x) = 0, for all x∈= domf =Q.
Proposition 1.2.15. Let f : A→ B be a one-one function and C be a nonempty subset of A.
Then, f is also one-one.
Proof. Let if possible, f (x) = f (y), for some x,y∈ C. Then, by deﬁnition of f , we have
C C C
f(x)=f(y). As f is one-one, we get x =y. Thus, f is one-one.
DRAFT1.2. PRELIMINARIES 11
Deﬁnition 1.2.16. Onto/Surjection A function f : A→ B is called onto (also called a
surjection), if f (b) =6 ∅, for each b∈ B. Equivalently, f : A→ B is onto if ‘each z∈ B has
some pre-image in A’.
Example 1.2.17. 1. In Deﬁnition 1.2.9, the function g is onto whereas g is not onto.
2. There are 6 onto functions from 3 to 2. For example, f(1) = 1,f(2) = 2 and f(3) = 2
is one such function.
y if y∈A,
3. Let∅ =6 A( B. Choose a∈ A. Then, g(y) = is an onto map from
a if y∈B\A.
B to A.
4. There is no onto function from the set 2 to its proper superset 3.
5. There are onto functions f from the set2,3,... to its proper supersetN. One of them
Deﬁnition 1.2.18. Bijection and equivalent set Let A and B be two sets. A function
f : A→ B is said to be a bijection if f is one-one as well as onto. The sets A and B are said
to be equivalent if there exists a bijection f :A→B.
Example 1.2.19. 1. In Deﬁnition 1.2.9, the function g is a bijection.
2. The function f : 3→a,b,c deﬁned by f(1) = c, f(2) = b and f(3) = a, is a bijection.
Thus, the seta,b,c is equivalent to 3.
3. Let∅ =6 A⊆A. Then, f(x)=x is a bijection. Thus, the set A is equivalent to itself.
4. If f :A→B is a bijection then f : B→A is a bijection. Thus, if A is equivalent to B
then B is equivalent to A.
5. The set N is equivalent to2,3,.... Indeed the function f : N→2,3,... deﬁned by
f(1) = 3, f(2) = 2 and f(n)=n+1, for n≥ 3 is a bijection.
The following is known as the ‘principle of mathematical induction’ in weak form.
Axiom 1.2.20. Principle of mathematical induction (PMI): Weak form Let S⊆N be a
set which satisﬁes
1. 1∈S and
2. k+1∈S whenever k∈S.
Then, S =N.
Fact 1.2.21. 1. Let A,B and C be sets and let f : A→ B and g : B→ C be bijections.
Then, h :A→C deﬁned by h(x) =g(f(x)) is a bijection.
PMI is actually a part of Peano’ axioms that deﬁnes N as: a) 1 ∈ N. b) For each n ∈ N, the successor
s(n)∈N. c) 1 is not a successor of any natural number. d) If s(m) = s(n) happens for natural numbers m and
n, then m =n. e) Let S ⊆N such that 1∈S and s(k)∈S, for each k ∈S. Then, S =N.
DRAFT12 CHAPTER 1. BASIC SET THEORY
Proof. h is one-one: Let if possible h(x) = h(y), for some x,y∈ A. Then, by deﬁnition,
g(f(x)) = g(f(y)), for some f(x),f(y)∈ B. As g is one-one, we get f(x) = f(y). Now,
using f is one-one, we get x =y and hence h is one-one.
h is onto: Let c∈ C. Then, the condition that g is onto implies that there exists b∈ B
such that g(b) = c. Also, for b∈B, the condition that f is onto implies that there exists
a∈ A such that f(a) = b. Thus, we see that h(a) = g(f(a)) = g(b) = c and hence the
required result follows.
2. Let A and B be two disjoint sets and let f : A→ n and g : B→ m be two bijections.
f(x) if x∈A
Then, the function h : A∪B→ m+n deﬁned by h(x) = is a
g(x)+n if x∈B
3. Fix n≥ 2 and let f : A→ n be a bijection such that for a ﬁxed element a∈A, one has
f(x) if f(x)≤k−1
f(a) =k. Then, g :A\a→ n−1 deﬁned by g(x) = is
f(x)−1 if f(x)≥k+1
4. For any positive integers n and k, there is no bijection from n to n+k.
Proof. Let us ﬁx k and prove the result by induction on n. The result is clearly true for
n = 1 as k +1≥ 2. So, let the result be true for n. We need to prove it for n+1. On
the contrary, assume that there exists a bijection f : n + 1→ n + 1 +k. Then, by
Fact 18.104.22.168, we get a bijection g : n→ n+k, where a = n+1. Thus, we arrive at a
contradiction to the induction assumption.
Deﬁnition 1.2.22. Number of elements in a set A set A is said to be ﬁnite if either A is
empty or A is equivalent to n, for some natural number n. A set which is not ﬁnite is called
inﬁnite. We say ‘A has n elements’ or ‘the number of elements in A is n’ to mean that ‘A
is equivalent to n’. We writeA = n to mean that A has n elements. Conventionally, the
number of elements in an empty set is zero. If f : n→ A is a bijection, then A can be listed
asa =f(1),...,a =f(n).
Fact 1.2.23. 1. LetAandB betwodisjointsets withA =mandB=n. Then,A∪B=
Proof. Use Fact 22.214.171.124.
2. Any subset of n is ﬁnite.
Proof. We use PMI to prove this. It is true for n = 1. Let the result be true for n−1.
Now, let S⊆ n. If n6∈ S, then S⊆ n−1 and hence using PMI the result follows. If
n∈ S, let T = S\n. Then, by PMI, T is ﬁnite and hence by Fact 126.96.36.199, S is ﬁnite
as S is disjoint union of T andn.
3. Any subset of a ﬁnite set is ﬁnite.
Proof. LetS = n, for some n∈N. Then, there is a bijection f : S→ n. Let T⊆ S.
If T is empty then there is nothing to prove. Else, consider the map f : T → f(T).
DRAFT1.2. PRELIMINARIES 13
This map is a bijection. By Fact 188.8.131.52, f(T)⊆ n is ﬁnite and hence T is ﬁnite (use
4. Let A and B be two ﬁnite sets, thenA∪B=A+B−A∩B.
Proof. Using (1.1), A∪B = (A\B)∪(A∩B)∪(B\A). As the sets A\B, A∩B and
B\A are ﬁnite and pairwise disjoint, the result follows from Fact 184.108.40.206.
5. Let A be a nonempty ﬁnite set. Then, for any set B,A =A\B+A∩B.
Proof. As A is ﬁnite, A\B and A∩B are also ﬁnite. Now, use Fact 220.127.116.11.
6. Let A be a nonempty ﬁnite set and B⊆ A, thenB≤A. In particular, if B ( A then
Proof. Since B =A∩B, the result follows from Fact 18.104.22.168.
7. Let n andk be two ﬁxed positive integers. Then, there is no one-one function from n+k
Proof. Suppose there exists a one-one function f : n+k→ n, for some n and k. Put
B =f(n+k)⊆ n. Then, notice that f : n+k→B is a bijection and hence the sets B
and n+k are equivalent. Thus, by deﬁnition and Fact 22.214.171.124, n+k =B≤nn+1.
Or equivalently, k 1 contradicting the assumption that k≥ 1.
8. The setN is inﬁnite.
Proof. Assume that the set N is ﬁnite andN = n, for some natural number n. Let
f : N→ n be a bijection. Then, f is the restriction of f on n + 1. Thus, by
Proposition 1.2.15, f is also one-one, contradicting Fact 126.96.36.199.
9. Let A be a ﬁnite nonempty set and x be a ﬁxed symbol. Now, consider the set B =
(x,a)a∈A. Then,A =B.
Proof. Deﬁne the function f : A→ B by f(a) = (x,a), for all a∈ A. Then, f is a
10. Let A be an inﬁnite set and B⊇A. Then, B is inﬁnite.
Proof. If B is ﬁnite then by Fact 188.8.131.52, A is ﬁnite. A contradiction to A being an
11. Let A be an inﬁnite set and B be a ﬁnite set. Then, A\B is also inﬁnite. In particular,
if a∈A, then A\a is also inﬁnite.
Proof. If A\B is ﬁnite, then by Fact 184.108.40.206, the set (A\B)∪B is also ﬁnite. But
A⊆ (A\B)∪B and hence by Fact 220.127.116.11, A is ﬁnite as well. A contradiction toA being
an inﬁnite set.
12. A set A is inﬁnite if and only if there is a one-one function f :N→A.
Proof. Let A be inﬁnite. So, A6=∅. Let a ∈ A. Put f(1) = a and A = A\a. By
1 1 1 1
Fact 18.104.22.168, A is inﬁnite. Assume that we have deﬁned f(1),...,f(k) and obtained
A =A \a. As A was inﬁnite, by Fact 22.214.171.124, A is inﬁnite. Hence, A =6 ∅.
k k−1 k k−1 k k
DRAFT14 CHAPTER 1. BASIC SET THEORY
Let a ∈A . Deﬁnef(k+1) =a and A =A \a . By applying induction, f
k+1 k k+1 k+1 k k+1
gets deﬁned onN. Notice that by construction a ∈/a ,...,a. Hence, f is one-one.
k+1 1 k
Conversely, let f :N→A be one-one. Then, f :N→f(N) is a bijection. If f(N) is ﬁnite
thenN is ﬁnite as well, contradicting Fact 126.96.36.199. Hence, f(N) is inﬁnite. As f(N)⊆A,
using Fact 188.8.131.52, A is inﬁnite as well.
13. A set is inﬁnite if and only if it is equivalent to a proper subset of itself.
Proof. Let S be an inﬁnite set. Then, by Fact 184.108.40.206, there is a one-one function
x, if x6∈f(N)
f :N→ S. Now deﬁne a map g : S→ S\f(1) by g(x) =
f(k+1), if x =f(k).
Then, g is indeed a bijection. Thus, S is equivalent to its proper subset S\f(1).
Conversely, let S be a set and T a proper subset of S such that there is a bijection
f : S→ T. Suppose that S is ﬁnite and letS = n. Then, by Fact 220.127.116.11, T is also
ﬁnite andT = m n. On the other hand, by the assumption that S is ﬁnite and there
is a bijection from S to T, we have m =n, a contradiction.
Exercise 1.2.24. Optional
1. Do there exist unique sets X and Y such that X\Y =1,3,5,7 and Y\X =2,4,8?
2. In a class of 60 students, all the students play either football or cricket. If 20 students play
both football and cricket, determine the number of players for each game if the number of
students who play football is
(a) 14 more than the number of students who play cricket.
(b) exactly 5 times the number of students who play only cricket.
(c) a multiple of 2 and 3 and leaves a remainder 3 when divided by 5.
(d) is a factor of 90 and the number of students who play cricket is a factor of 70.
1.3 More on the Principle of Mathematical Induction
The following is known as the ‘principle of mathematical induction’ in strong form.
Theorem 1.3.1. Principle of mathematical induction (PMI): Strong form Let S⊆N be a
set which satisﬁes
1. 1∈S and
2. k+1∈S whenever k⊆S holds.
Then, S =N.
Proof. Deﬁne T =k∈ S k⊆ S. Then, 1∈ T as 1∈ S and 1⊆ S. Now, suppose
k∈T. Then, by deﬁnition k⊆S. Therefore, the hypothesis implies that k+1∈S and hence
k+1 = k∪k+1⊆S. Thus, k+1∈T. Hence, by using the weak form of PMI on T, we
conclude that T =N, which in turn implies that S =N.
DRAFT1.3. MORE ON THE PRINCIPLE OF MATHEMATICAL INDUCTION 15
Theorem 1.3.2. Another form of PMI Let S⊆Z be a set which satisﬁes
1. k ∈S and
2. k+1∈S wheneverk ,k +1,...,k⊆S.
Then,k ,k +1,...⊆S.
Proof. Consider T = x− (k − 1) x ∈ S,x ≥ k. Then, 1 ∈ T as k ∈ S and 1 =
0 0 0
k −(k −1). Now, let k⊆T. Then,k ,k +1,...,k +k−1⊆S. Hence, by the hypothesis,
0 0 0 0 0
(k +k−1)+1 =k +k∈S. Therefore, by deﬁnition of T, we have k+1∈T and hence using
the strong form of PMI, T =N. Thus, the required result follows.
The next result is commonly known as the Well-Ordering Principle which states that “every
nonempty subset of natural numbers contains its least element”.
Theorem 1.3.3. Application of PMI in strong form: A nonempty subset ofN contains its
minimum Let∅ =6 A⊆N. Then, the least element of A is a member of A.
Proof. For each ﬁxed positive integer k, let P(k) mean the statement ‘each nonempty subset A
ofN that contains k, also contains its minimum’.
Notice that P(1) is true. Now, assume that P(1),...,P(k) are true. We need to show that
P(k +1) is true as well. Hence, consider a set A such that k +1∈ A. If1,...,k∩A =∅,
then k +1 = minA, we are done. If r∈1,...,k∩A, then r≤ k and hence by induction
hypothesis, P(r) is true. So, P(k +1) is true. Hence, by the strong form of PMI the required
By using Theorem 1.3.2, we can also prove the following generalization of Theorem 1.3.3. The
proof is similar to the proof of Theorem 1.3.3 and is left to the reader.
Theorem 1.3.4. Well-ordering principle Fix k∈Z. Let A be a nonempty subset ofk,k+
1,.... Then, A contains its minimum element.
Theorem 1.3.5. Archimedean property for positive integers Let x,y∈ N. Then, there
exists n∈N such that nx≥y.
Proof. On the contrary assume that such an n∈N does not exist. That is, nx y for every
n∈ N. That is, y−nx∈ N, for all n∈ N. Now, consider the set S =y−nx n∈ N.
Then, y∈S and hence S is a nonempty subset ofN . Therefore, by the well-ordering principle
(Theorem 1.3.4), S contains its least element, say y−mx. Then, by assumption, the integer
y−(m+1)x≥ 0, y−(m+1)x∈S andy−(m+1)xy−mx. A contradicts to the minimality
of y−mx. Thus, our assumption is invalid and hence the required result follows.
The next result gives the equivalence of the weak form of PMI with the strong form of PMI.
Theorem 1.3.6. Equivalence of PMI in weak form and PMI in strong form Fix a natural
number k and let P(n) be a statement about a natural number n. Suppose that P means the
statement ‘P(n) is true, for each n∈N,n≥ k ’. Then, ‘P can be proved using the weak form
of PMI’ if and only if ‘P can be proved using the strong form of PMI’.
DRAFT16 CHAPTER 1. BASIC SET THEORY
Proof. Let us assumethat thestatement P has been proved usingthe weak form of PMI. Hence,
P(k ) is true. Further, whenever P(n) is true, we are able to establish that P(n+1) is true.
Therefore, we can establish that P(n+1) is true if P(k ),...,P(n) are true. Hence, P can be
proved using the strong form of PMI.
So, now let us assume that the statement P has been proved using the strong form of PMI.
Now, deﬁne Q(n) to mean ‘P(ℓ) holds for ℓ = k ,k + 1,...,n’. Notice that Q(k ) is true.
0 0 0
Supposethat Q(n) is true (this means that P(ℓ) is true forℓ =k ,k +1,...,n). By hypothesis,
P(ℓ) is true for ℓ =k ,k +1,...,n. This, in turn, means that Q(n+1) is true. Hence, by the
weak form of PMI, Q(n) is true for all n≥ k . Thus, we are able to prove P using the weak
form of PMI.
Theorem 1.3.7. Optional: Application of PMI in weak form: AM-GM inequality Fix a
positive integer n and let a ,a ,...,a be non-negative real numbers. Then
1 2 n
a +···+a √
Arithmetic Mean (AM):= ≥ a ···a =: (GM) Geometric Mean.
Proof. The inequality clearly holds for n = 1 and 2. Assume that it holds for every choice of n
non-negative real numbers. Now, leta ,...,a ,a bea set ofn+1non-negative real numbers
1 n n+1
a +a +···+a
1 2 n+1
with a = maxa ,...,a and a = mina ,...,a . Deﬁne A =
1 1 n+1 n+1 1 n+1
note that a ≥ A≥ a . Hence, (a −A)(A−a )≥ 0, i.e., A(a +a −A)≥ a a .
1 n+1 1 n+1 1 n+1 1 n+1
Now, apply induction hypothesis on the n non-negative real numbers a ,...,a ,a +a −A
2 n 1 n+1
a +···+a +(a +a −A)
2 n 1 n+1
a ·····a ·(a +a −A)≤ =A.
2 n 1 n+1
So, wehaveA ≥ (a ·a ·····a ·(a +a −A))·A≥ (a ·a ·····a )a a . Therefore,
2 3 n 1 n+1 2 3 n 1 n+1
by PMI, the inequality holds, for each n∈N.
Inthenextexample, weillustratetheuseofPMItoestablishsomegiven identities (properties,
statements) involving natural numbers.
Example 1.3.8. Prove that 1+2+···+n = .
Ans: The result is clearly true for n = 1. So, let us assume that 1+2+···+n = .
Then, using the induction hypothesis, we have
1+2+···+n+(n+1) = +(n+1) = (n+2).
Thus, the result holds for n+1 and hence by the weak form of PMI, the result follows.
Exercise 1.3.9. Optional Prove using PMI.
2 2 2
1. 1 +2 +···+n = .
2. 1+3+···+(2n−1) =n , for all n∈N.
3. n(n+1) is even, for all n∈N.
4. 3 divides n −n, for all n∈N.
DRAFT1.3. MORE ON THE PRINCIPLE OF MATHEMATICAL INDUCTION 17
5. 5 divides n −n, for all n∈N.
Practice1.3.10. WronguseofPMI:Canyouﬁndtheerror? The following isan incorrect
proof of ‘if a set of n balls contains a green ball then all the balls in the set are green’. Find the
Proof. The statement holds trivially for n = 1. Assume that the statement is true for n≤ k.
Take a collection B of k +1 balls that contains at least one green ball. From B , pick a
collection B of k balls that contains at least one green ball. Then, by the induction hypothesis,
each ball in B is green. Now, remove one ball from B and put the ball which was left out in
the beginning. Call it B . Again by induction hypothesis, each ball in B is green. Thus, each
ball in B is green. Hence, by PMI, our proof is complete.
Exercise 1.3.11. Optional
2 n k
1. Let x∈R with x =6 1. Then, prove that 1+x+x +···+x = x = .
2. Let a,a+d,a+2d,...,a+(n−1)d be the ﬁrst n terms of an arithmetic progression. Then,
S = (a+id) =a+(a+d)+···+(a+(n−1)d) = (2a+(n−1)d).
3. Let a,ar,ar ,...,ar be the ﬁrst n terms of a geometric progression, with r =6 1. Then,
S =a+ar+···+ar = ar =a .
4. Prove that
(a) 6 divides n −n, for all n∈N.
(b) 7 divides n −n, for all n∈N.
(c) 3 divides 2 −1, for all n∈N.
(d) 9 divides 2 −3n−1, for all n∈N.
(e) 10 divides n −n, for all n∈N.
2n+2 4 2
(f) 12 divides 2 −3n +3n −4, for all n∈N.
3 3 3
(g) 1 +2 +···+n = .
5. Determine a formula for 1·2+2·3+3·4+···+(n−1)·n and prove it.
6. Determine a formula for 1·2·3+2·3·4+3·4·5+···+(n−1)·n·(n+1) and prove it.
7. Determine a formula for 1·3·5+2·4·6+···+n·(n+2)·(n+4) and prove it.
8. Informative For all n≥ 32, there exist nonnegative integers x and y such that n =
5x+9y. Hint: First prove it for the starting 5 numbers, 32,33,34,35,36.
9. Informative Prove that, for all n≥ 40, there exist nonnegative integers x and y such
that n = 5x+11y.
10. For every positive integer n≥ 3 prove that 2 n 2n+1.
DRAFT18 CHAPTER 1. BASIC SET THEORY
11. Let r∈R with r −1. Then, prove that
(1+r) ≥ 1+rn for all n∈N. (1.3)
12. Informative Prove that for µ 0,
p(p+1) 1 p (p+1) p(p+1)(2p+1)
(1+lµ )≥ 1+ µ + − µ .
2 2 4 6
13. Informative By an L-shaped piece, we mean a piece of the type shown in the picture.
Consider a 2 ×2 square with one unit square cut. See picture.
L-shaped piece 4×4 and 8×8 squares with a unit square cut
Show that a 2 ×2 square with one unit square cut, can be covered with L-shaped pieces.
5 5 4 3 2
14. InformativeVerifythat (k+1)−k = 5k +10k +10k +5k+1. Now, putk = 1,2,...,n
n n n n n
P P P P P
5 4 3 2
and add to get (n+1) −1 = 5 k +10 k +10 k +5 k+ 1. Now, use
k=1 k=1 k=1 k=1 k=1
n n n n n
P P P P P
3 2 4
the formula’s for k , k , k and 1 to get a expression for k .
k=1 k=1 k=1 k=1 k=1
15. Informative: A general result than AM-GM
(a) Let a ,...,a be nonnegative real numbers such that the sum a +··· + a = 5.
1 9 1 9
a +a a +a
1 2 1 2
Assume that a =6 a . Consider , ,a ,...,a . Argue that a ···a ≤
1 2 3 9 1 9
a ···a .
(b) Let a ,...,a be any nonnegative real numbers such that the sum a +···+a =r .
1 n 1 n 0
Argue that the highest value of a ···a is obtained when a =··· =a =r /n.
1 n 1 n 0
(c) Let a ,...,a be ﬁxed nonnegative real numbers such that the sum a +···+a =r .
1 n 1 n 0
Conclude from the previous item that (r /n) ≥a ···a , the AM-GM inequality.
0 1 n
In this section, we study some properties of integers. We start with the ‘division algorithm’.
Lemma 1.4.1. Division algorithm Let a and b be two integers with b 0. Then, there exist
unique integers q,r such that a =qb+r, where 0≤r b. The integer q is called the quotient
and r, the remainder.
Proof. Existence: Take S =a+bxx∈Z∩N . Then, a+ab∈S. Hence, S is a nonempty
subset of N . Therefore, by the Well-Ordering Principle, S contains its minimum, say s . So,
s =a+bx , for some x ∈Z. Notice that s ≥ 0. We claim that s b.
0 0 0 0 0
DRAFT1.4. INTEGERS 19
If s ≥b then s −b≥ 0 and hence s −b =a+b(x −1)∈S, a contradiction to s being the
0 0 0 0 0
minimum element of S. Now, put q =−x and r = s . Thus, we have obtained q and r such
that a =qb+r, with 0≤r b.
Uniqueness: Assumethatthereexistintegersq ,q ,r andr satisfyinga =q b+r ,0≤r b
1 2 1 2 1 1 1
anda =q b+r ,0≤r b. Withoutlossofgenerality,weassumer ≤r . Then,0≤r−r b.
2 2 2 1 2 2 1
Notice that r −r = (q −q )b. So, 0≤ (q −q )bb. But the only integer multiple of b which
2 1 1 2 1 2
lies in 0,b) is 0. Hence, q −q = 0. Thus, r =r as well. This completes the proof.
1 2 1 2
Deﬁnition 1.4.2. Divisibility
1. Divisor Let a,b∈Z with b6= 0. If a =bc, for some c∈Z then b is said to divide (be a
divisor of) a and is denoted ba.
(as 1a) and ﬁnite (as a positive divisor of a is less than or equal toa).
2. Greatest common divisor Let a and b be two nonzero integers. Then, the set S of
their common positive divisors is nonempty and ﬁnite. Thus, S contains its greatest
element. This element is called thegreatest common divisor of a and b and is denoted
gcd(a,b). On similar lines one can deﬁne the greatest common divisor of non-zero integers
a ,a ,...,a as the largest positive integer that divides each of a ,a ,...,a , denoted
1 2 n 1 2 n
gcd(a ,...,a ).
3. Relatively prime/Co-primeintegers An integer a is said to berelatively prime to an
integer b if gcd(a,b) = 1. Or, two integersa andb are said to beco-prime if gcd(a,b) = 1.
The next remark follows directly from the deﬁnition and the division algorithm.
Remark 1.4.3. Let a,b∈Z\0 and d = gcd(a,b). Then, for any positive common divisor c
of a and b, one has cd.
The next result is often stated as ‘the gcd(a,b) is an integer linear combination of a and b’.
Theorem 1.4.4. Be´zout’s identity Let a and b be two nonzero integers. Then, there exist
integers x ,y such that d =ax +by , where d = gcd(a,b).
0 0 0 0
Proof. Consider the set S =ax+by x,y∈Z∩N. Then, either a∈ S or−a∈ S. Thus, S
is a nonempty subset ofN. Hence, by the Well-ordering principle, S contains its least element,
say d. As d∈S, we have d=ax +by , for some x ,y ∈Z. We claim that d= gcd(a,b).
0 0 0 0
Notethatdispositive. Letcbeanypositivecommondivisorofaandb. Then,cax +by =d
as x ,y ∈Z. We now show that da and db.
By division algorithm, there exist integers q andr such that a =dq+r, with 0≤r d. Thus,
we need to show that r = 0.
On the contrary, assume that 0r d. Then
r =a−dq =a−q(ax +by ) =a(1−qx )+b(−qy )∈ax+byx,y∈Z.
0 0 0 0
DRAFT20 CHAPTER 1. BASIC SET THEORY
Hence, r is a positive integer in S which is strictly less than d. This contradicts the fact that d
is the least element of S. Thus, r = 0 and hence da. Similarly, db.
of two integers, commonly known as the Euclid’s algorithm.
Discussion 1.4.5. 1. Note that d, the number obtained by the application of the Well-
ordering principle in the proof of Theorem 1.4.4 has the property that d divides ax+by,
for all x,y∈Z. So, for every choice of integers x,y, gcd(a,b) divides ax+by.
2. Let a,b∈ Z\0. By division algorithm, a =bq +r, for some integers q,r∈ Z with
0≤r b. Then,
gcd(a,b) =gcd(a,b) = gcd(b,r).
To show the second equality, note that r = a−bq and hence gcd(a,b) r. Thus,
gcd(a,b)gcd(b,r). Similarly, gcd(b,r) gcd(a,b) as a =bq+r.
3. We can now apply the above idea repeatedly to ﬁnd the greatest common divisor of two
given nonzero integers. This is called the Euclid’s algorithm. For example, to ﬁnd
gcd(155,−275), we proceed as follows
−275 = (−2)·155+35 (so, gcd(−275,155) = gcd(155,35))
155 = 4·35+15 (so, gcd(155,35) = gcd(35,15))
35 = 2·15+5 (so, gcd(35,15) = gcd(15,5))
15 = 3·5 (so, gcd(15,5) = 5).
To write 5= gcd(155,−275) in the form 155x +(−275)y , notice that
5 = 35−2·15 = 35−2(155−4·35) = 9·35−2·155 = 9(−275+2·155)−2·155 = 9·(−275)+16·155.
Also, notethat275 = 5·55and155 = 5·31andthus,5 = (9+31x)·(−275)+(16+55x)·155,
for all x∈ Z. Therefore, we see that there are inﬁnite number of choices for the pair
(x,y)∈Z , for which d =ax+by.
4. Euclid’salgorithm Ingeneral,giventwononzerointegersaandb,thealgorithmproceeds
a = bq +r with 0≤r b, b =r q +r with 0≤r r ,
0 0 0 0 1 1 1 0
r = r q +r with 0≤r r , r =r q +r with 0≤r r ,
0 1 2 2 2 1 1 2 3 3 3 2
. = .
r = r q +r with 0≤r r , r =r q .
ℓ−1 ℓ ℓ+1 ℓ+1 ℓ+1 ℓ ℓ ℓ+1 ℓ+2
The process will take at most b−1 steps as 0≤ r b. Also, note that gcd(a,b) = r
and r can be recursively obtained, using backtracking. That is,
r =r −r q =r −q (r −r q )=r (1+q q )−q r =··· .
ℓ+1 ℓ−1 ℓ ℓ+1 ℓ−1 ℓ+1 ℓ−2 ℓ−1 ℓ ℓ−1 ℓ+1 ℓ ℓ+1 ℓ−2
DRAFT1.4. INTEGERS 21
Exercise 1.4.6. 1. Let a,b,c∈N. Then, prove the following:
(a) If gcd(a,b) =d, then gcd( , ) = 1.
(b) gcd(a,bc) = 1 if and only if gcd(a,b) = 1 and gcd(a,c) = 1.
2. Prove that the system 15x+12y =b has a solution for x,y∈Z if and only if 3 divides b.
3. Diophantine Equation Let a,b,c∈Z\0. Then, the linear system ax+by =c, in the
unknowns x,y∈Z has a solution if and only if gcd(a,b) divides c. Furthermore, determine
all pairs (x,y)∈Z×Z such that ax+by is indeed c.
4. Let a ,a ,...,a ∈N. Then, prove that gcd(a ,a ,...,a )= gcd(gcd(a ,a ),a ,...,a ).
1 2 n 1 2 n 1 2 3 n
5. Euclid’s algorithm can sometimes be applied to check whether two numbers which are func-
tions of an unknown integer n, are relatively prime or not? For example, we can use the
algorithm to prove that gcd(2n+3,5n+7) = 1 for every n∈Z.
6. Informative Suppose amilkman has only3cans of sizes7,9 and 16liters. If the milkman
has 16 litres of milk then using the 3 cans, speciﬁed as above, what is the minimum number
of operations required to deliver 1 liter of milk to a customer? Explain.
To proceed further, we need the following deﬁnitions.
Deﬁnition 1.4.7. Prime/Composite numbers
1. unity The positive integer 1 is called the unity (or the unit element) ofZ.
2. prime A positive integer p is said to be a prime, if p is not a unit and p has exactly
two positive divisors, namely, 1 and p.
3. composite A positive integer r is called composite if r is neither a unit nor a prime.
We are now ready to prove an important result that helps us in proving the fundamental
theorem of arithmetic.
Lemma 1.4.8. Euclid’s lemma Let p be a prime and let a,b∈Z. If p ab then either p a
Proof. If pa, we are done. So, assume that p∤a. As p is a prime, gcd(p,a) = 1. Thus, we can
ﬁnd integers x,y such that 1 =ax+py. As pab, we have
pabx+pby =b(ax+py)=b·1 =b.
Thus, if pab then either pa or pb.
As a repeated application of Lemma 1.4.8, we have the following result and hence the proof is
Corollary 1.4.9. Let n be an integer such that nab and gcd(n,a) = 1. Then, nb.
DRAFT22 CHAPTER 1. BASIC SET THEORY
Now, we are ready to prove the fundamental theorem of arithmetic that states that ‘every
positive integer greater than 1 is either a prime or is a product of primes. This product is
unique, except for the order in which the prime factors appear’.
Theorem 1.4.10. Fundamental theorem of arithmetic Let n∈ N with n≥ 2. Then,
there exist prime numbers p p ··· p and positive integers s ,s ,...,s such that
1 2 1 2
s s t t
1 2 k 1 2 ℓ
n = p p ···p , for some k≥ 1. Moreover, if n also equals q q ···q , for distinct primes
1 2 k 1 2 ℓ
q q ··· q and positive integers t ,t ,...,t then k =ℓ and for each i, 1≤i≤k, p =q
1 2 ℓ 1 2 ℓ i i
and s =t .
Proof. We prove the result using the strong form of the principle of mathematical induction.
The result is clearly true for n = 2. So, let the result be true for all m,2≤m≤n−1. If n is a
prime, then we have nothing to prove. Else, n has a prime divisor p. Then, apply induction on
to get the required result.
Theorem 1.4.11. Euclid: Inﬁnitude of primes The number of primes is inﬁnite.
Proof. On the contrary assume that the number of primes is ﬁnite, say p = 2,p = 3,...,p .
1 2 k
Now, consider the positive integer N = p p ···p +1. Then, we see that none of the primes
1 2 k
p ,p ,...,p divides N which contradicts Theorem 1.4.10. Thus, the result follows.
1 2 k
1 1 1
Example 1.4.12. Prove that for all n≥ 2, the number 1+ + +···+ is not an integer.
2 3 n
1 1 1
Proof. Suppose there exists n≥ 2 such that 1 + + +··· + = N, for some positive
2 3 n
integer N. Now, let r be the largest positive integer such that 2 ≤ n. Then, N− =
1 1 1 1
1+ +···+ + +···+ . Also, let K = lcm(2,3,...,2 −1,2 +1,...,n). Then,
2 2 −1 2 +1 n
note that 2 does not divide K as r was the largest positive integer such that 2 ≤n. Also, we
N·2 −1 M
for some positive integer M. Or equivalently, 2 M = K(N· 2 − 1). Thus, we arrive at a
contradiction that 2 divides the left-hand-side whereas it does not divide the right-hand-side.
Proposition 1.4.13. Primality testing Let n∈N with n≥ 2. Suppose that for every prime
p≤ n, p does not divide n, then n is prime.
Proof. Suppose n = xy, for 2≤ x,y n. Then, either x≤ n or y≤ n. Without loss of
generality, assume x≤ n. If x is a prime, we are done. Else, take a prime divisor of x to get
Exercise1.4.14. Informative Prove that there are inﬁnitely many primes of the form 4n−1.
Deﬁnition 1.4.15. Least common multiple Let a,b∈Z. Then, the least common mul-
tiple of a and b, denoted lcm(a,b), is the smallest positive integer that is a multiple of both a
DRAFT1.4. INTEGERS 23
Theorem 1.4.16. Let a,b∈ N. Then, gcd(a,b)· lcm(a,b) = ab. Thus, lcm(a,b) = ab if and
only if gcd(a,b) = 1.
Proof. Let d = gcd(a,b). Then, d = as +bt, for some s,t∈ Z, a = a d, b = b d, for some
a ,b ∈N. We need to show that lcm(a,b) = a b d = ab = a b, which is clearly a multiple of
1 1 1 1 1 1
both a and b. Let c∈N be any common multiple of a and b. To show, a b d divides c. Note
c cd c(as+bt) c c
= = = s+ t∈Z
a b d (a d)·(b d) ab b a
1 1 1 1
as , ∈ Z and s,t∈ Z. Thus, a b d = lcm(a,b) divides c and hence lcm(a,b) is indeed the
smallest. Thus, the required result follows.
Exercise 1.4.17. 1. If gcd(b,c) =1, then gcd(a,bc) = gcd(a,b)·gcd(a,c).
n n n
2. If gcd(a,b) =d, then gcd(a ,b ) =d for all n∈N.
Deﬁnition 1.4.18. Modular Arithmetic Fix a positive integer n. Then, ‘an integer a is said
to be congruent to an integer b modulo n’, denoted a≡b (mod n), if n divides a−b.
Example 1.4.19. 1. The numbers±10 and 22 are equivalent modulo 4 as 4 12 = 22−10
and 432 = 22−(−10).
2. Let n∈N be a perfect square. That is, there exists an integer m such that n =m . Then,
n≡ 0,1 (mod 4) as any integer m≡ 0,±1,2 (mod 4) and hence m ≡ 0,1 (mod 4).
3. Let S =15,115,215,.... Then, S doesn’t contain any perfect square as for each s∈S,
s≡ 3 (mod 4).
4. It can be easily veriﬁed that any two even (odd) integers are equivalent modulo 2 as
22(l−m) = 2l−2m (22(l−m) = ((2l+1)−(2m+1))).
5. Let n be a ﬁxed positive integer and let S =0,1,2,...,n−1.
(a) Then,by divisionalgorithm, foranya∈Zthereexists auniqueb∈S such thatb≡a
(mod n). The number a (mod n) (in short, b) is called the residue of a modulo n.
(b) Thus, the set of integers,Z = a+kn :k∈Z. Thatis, every integer is congruent
to an element of S. The set S is taken as the standard representative for the set
of residue classes modulo n.
Theorem 1.4.20. Let n be a positive integer. Then, the following results hold.
1. Let a≡b (mod n) and b≡c (mod n), for some a,b,c∈Z. Then, a≡c (mod n).
2. Let a≡b (mod n), for some a,b∈Z. Then, a+c≡b+c (mod n), a−c≡b−c (mod n)
and ac≡bc (mod n), for all c∈Z.
3. Let a≡b (mod n) andc≡d (mod n), for some a,b,c,d∈Z. Then, a±c≡b±d (mod n)
and ac≡bd (mod n). In particular, a ≡b (mod n), for all m∈N.
4. Let ac≡ bc (mod n), for some non-zero a,b,c∈ Z. Then, a≡ b (mod n), whenever
gcd(c,n) = 1. In general, a≡b (mod ).
DRAFT24 CHAPTER 1. BASIC SET THEORY
Proof. We will only prove two parts. The readers should supply the proof of other parts.
Part 3: Note that ac−bd≡ac−bc+bc−bd≡c(a−b)+b(c−d). Thus, nac−bd, whenever
na−b and nc−d.
In particular, taking c = a and d = b and repeatedly applying the above result, one has
a ≡b (mod n), for all m∈N.
Part 4: Let gcd(c,n) = d. Then, there exist non-zero c ,n ∈Z and c = c d,n = n d. Thus,
1 1 1 1
n ac−bc means that n d c d(a−b). This, in turn implies that n c (a−b). Hence, by
1 1 1 1
Corollary 1.4.9, we get =n a−b.
Theorem 1.4.21. Fermat’s Little Theorem Let p be a prime and n ∈ N. Then, n ≡
n (mod p).
Proof. Note that if pn, then obviously, n ≡ n (mod p). So, let us assume that gcd(p,n) = 1.
Then, we need to show that n ≡ 1 (mod p).
To do this, we consider the set S =n (mod p),2n (mod p),...,(p−1)n (mod p). Since,
gcd(p,n) = 1, by second and fourth parts of Theorem 1.4.20, an≡ bn (mod p) if and only if
a≡b (mod p). Thus, S≡1,2,...,p−1. Hence,
n (p−1) =n·2n·····(p−1)n≡ 1·2·····(p−1).
Thus, the condition gcd((p−1),p) = 1 implies that n ≡ 1 (mod p).
Before coming to the next result, we look at the following examples.
Example 1.4.22. 1. As gcd(251,13) = 1, we see that 251 ≡ 1 (mod 13). Hence, 251
leaves the remainder 1, when divided by 13.
2. As 255≡ 2 (mod 23), gcd(255,23) = 1. Hence,
27 22 5 5
255 ≡ (255 )·(255 ) (mod 23)≡ 2 (mod 23)≡ 32 (mod 2)3≡ 9 (mod 2)3.
3. Note that 3·9+13·(−2)≡ 1 (mod 13). So, the system 9x≡ 4 (mod 13) has the solution
x≡x·1≡x·(3·9+13·(−2))≡ 3·9x≡ 3·4≡ 12 (mod 13).
4. Verify that 9·(−5)+23·(2) = 1. Hence, the system 9x≡1 (mod 23) has the solution
x≡x·1≡x(9·(−5)+23·(2))≡ (−5)·(9x)≡−5≡ 18 (mod 23).
5. The system 3x≡ 15 (mod 30) has solutions x = 5,15,25, whereas the system 7x = 15 has
only the solution x = 15. Also, verify that the system 3x≡ 5 (mod 30) has no solution.
Theorem 1.4.23. Linear Congruence Let n be a positive integer and let a and b be non-zero
integers. Then, the system ax≡b (mod n) has at least one solution if and only if gcd(a,n)b.
Moreover, if d =gcd(a,n) then ax≡b (mod n) has exactly d solutions in0,1,2,...,n−1.
DRAFT1.4. INTEGERS 25
Proof. Let x be a solution of ax≡ b (mod n). Then, by deﬁnition, ax −b = nq, for some
q∈Z. Thus, b =ax −nq. But, gcd(a,n)a,n and hence gcd(a,n)ax −nq =b.
Suppose d = gcd(a,n) b. Then, b = b d, for some b ∈ Z. Also, by Euclidean algorithm,
there exists x ,y ∈Z such that ax +ny =d. Hence,
0 0 0 0
a(x b )≡b (ax )≡b (ax +ny )≡b d≡b (mod n).
0 1 1 0 1 0 0 1
This completes the proof of the ﬁrst part.
To proceed further, assume that x ,x are two solutions. Then, ax ≡ ax (mod n) and
1 2 1 2
hence, by Theorem 18.104.22.168, x ≡ x (mod ). Thus, we can ﬁnd x ∈0,1,..., such that
1 2 2
x =x +k is a solution ofax≡b (mod n), for 0≤k≤d−1. Verify that thesex’s are distinct
and lie between 0 and n−1. Hence, the required result follows.
Exercise 1.4.24. 1. Prove Theorem 1.4.20.
2. Prove that the numbers 19,119,219,... cannot be perfect squares.
3. Prove that the numbers 10,110,210,... cannot be perfect squares.
4. Prove that the system 3x≡ 4 (mod 28) is equivalent to the system x≡ 20 (mod 28).
5. Determine the solutions of the system 3x≡ 5 (mod 65).
6. Determine the solutions of the system 15x≡ 295 (mod 100).
7. Prove that the pair of systems 3x≡ 4 (mod 28) and 4x≡ 2 (mod 27) is equivalent to
the pair x≡ 20 (mod 28) and x≡ 14 (mod 27). Hence, prove that the above system is
equivalent to solving either 20+28k≡ 14 (mod 27) or 14+27k≡ 20 (mod 28) for the
unknown quantity k. Thus, verify that k = 21 is the solution for the ﬁrst case and k = 22
for the other. Hence, x = 20+28·21 = 608 = 14+22·27 is a solution of the above pair.
8. Let p be a prime. Then, prove that p = , for 1≤k≤p−1.
9. Informative Let p be a prime. Then, the set
(a) Z =0,1,2,...,p−1 has the following properties:
i. for every a,b∈Z , a+b (mod p)∈Z .
ii. for every a,b∈Z , a+b =b+a (mod p).
iii. for every a,b,c∈Z , a+(b+c)≡(a+b)+c (mod p).
iv. for every a∈Z , a+0≡a (mod p).
v. for every a∈Z , a+(p−a)≡ 0 (mod p).
(b) Z =1,2,...,p−1 has the following properties:
i. for every a,b∈Z , a·b (mod p)∈Z .
ii. for every a,b∈Z , a·b =b·a (mod p).
iii. for every a,b,c∈Z , a·(b·c)≡ (a·b)·c (mod p).
iv. for every a∈Z , a·1≡a (mod p).
v. for every a∈Z , a·b≡ 1 (mod p). To see this, note that gcd(a,p) = 1. Hence,
by Euclid’s algorithm, there exists x,y∈Z such that ax+py = 1. Deﬁne b≡ x
(mod p). Then,
a·b≡a·x≡a·x+p·y≡ 1 (mod p).