Question? Leave a message!




Lecture Notes on Discrete Mathematics

Discrete Mathematics lecture notes pdf free download
ShawnPacinocal Profile Pic
ShawnPacinocal,United States,Researcher
Published Date:09-07-2017
Your Website URL(Optional)
Comment
Lecture Notes on Discrete Mathematics A K Lal S Pati November 20, 2016 DRAFTChapter 1 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 0 Z : the set of integers Q : the set of rational numbers R : the set of real numbers n : the set1,2,...,n c 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 1.2 Preliminaries We expect the readers to have familiarity with the following definitions. Definition 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 A =B. 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. Specifically, A×B =(a,b) a∈ A,b∈B. c 4. Set complement Let C⊆ A. The complement of C in A, denoted C , is a set that c containseveryelementofAthatisnotanelementofC. Specifically,C =x∈Ax6∈C. 7 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. Specifically, 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. Specifically, A∩B =x x∈A and x∈B. The set A and B are said to be disjoint if A∩B =∅. 7. Set difference Theset difference of A and B, denoted A\B, is a set that contains all those elements of A which are not in B. Specifically, A\B =x∈Ax6∈B. 8. Symmetric difference The symmetric difference of A and B, denoted AΔB, equals (A\B)∪(B\A). 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. That is, 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). Definition 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. Definition 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 1 relation. We can draw a picture for f. a 1 2 b c 3 f Definition 1.2.8. 1. Domain, range and inverse relation Let f : A→ B be a relation. 2 Then,bythedomainoff wemeanthesetdomf:=a(a,y)∈fandbytherangeof −1 f wemeanthesetrngf:=b (x,b)∈f. Theinverseoff isf :=(y,x) (x,y)∈f. −1 Notice that f is a relation from B to A. For example, the relation f in Example 1.2.7 −1 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 define 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) =∅. −1 (c) for X =1,4,c, one has f(X) =a,b and f (X) =2. Definition 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 1 g =(1,b),(2,c),(3,a) are indeed functions. 2 The following is an immediate consequence of the definition. 1 We use pictures to help our understanding and they are not parts of proof. 2 The domain set is the setfrom which we defineourrelations butdomf is the domain oftheparticular relation f. They are different. 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 ∅. −1 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 find 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 findb∈ rng(f)∩S and a∈A such that (a,b)∈f. This, −1 −1 in turn, implies that a∈f (b)⊆f (S) as b∈S. Definition 1.2.11. One-one/Injection A function f :A→B is called one-one (also called −1 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 whenever f(x)=f(y). Convention: Let p(x) be a polynomial in x with integer coefficients. Then, by writing ‘f : Z→ Z is a function defined by f(x) = p(x)’, we mean the function f =(a,p(a)) a∈ Z. For 2 2 example, the function f(x) =x stands for the set(a,a )a∈Z. Example 1.2.12. 1. InDefinition1.2.9, thefunctiong isone-onewhereasg isnotone-one. 2 1 2 2. The function f :Z→Z defined by f(x)=x is not one-one. 2 3. The function f :N→N defined by f(x)=x is one-one. 0 4. The function f : 3→a,b,c,d defined 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. Definition 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 (x,y)∈f,x∈A. Example 1.2.14. Define 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. Q 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. C Proof. Let if possible, f (x) = f (y), for some x,y∈ C. Then, by definition 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. C DRAFT1.2. PRELIMINARIES 11 Definition 1.2.16. Onto/Surjection A function f : A→ B is called onto (also called a −1 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 Definition 1.2.9, the function g is onto whereas g is not onto. 2 1 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 is f(x)=x−1. Definition 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 Definition 1.2.9, the function g is a bijection. 2 2. The function f : 3→a,b,c defined 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. −1 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,... defined 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 satisfies 1. 1∈S and 2. k+1∈S whenever k∈S. 1 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 defined by h(x) =g(f(x)) is a bijection. 1 PMI is actually a part of Peano’ axioms that defines 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 definition, 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 defined by h(x) = is a g(x)+n if x∈B bijection. 3. Fix n≥ 2 and let f : A→ n be a bijection such that for a fixed element a∈A, one has ( f(x) if f(x)≤k−1 f(a) =k. Then, g :A\a→ n−1 defined by g(x) = is f(x)−1 if f(x)≥k+1 a bijection. 4. For any positive integers n and k, there is no bijection from n to n+k. Proof. Let us fix 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 1.2.21.3, we get a bijection g : n→ n+k, where a = n+1. Thus, we arrive at a contradiction to the induction assumption. Definition 1.2.22. Number of elements in a set A set A is said to be finite if either A is empty or A is equivalent to n, for some natural number n. A set which is not finite is called infinite. 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). 1 n Fact 1.2.23. 1. LetAandB betwodisjointsets withA =mandB=n. Then,A∪B= m+n. Proof. Use Fact 1.2.21.2. 2. Any subset of n is finite. 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 finite and hence by Fact 1.2.23.1, S is finite as S is disjoint union of T andn. 3. Any subset of a finite set is finite. 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). T DRAFT1.2. PRELIMINARIES 13 This map is a bijection. By Fact 1.2.23.2, f(T)⊆ n is finite and hence T is finite (use Fact 1.2.21.1). 4. Let A and B be two finite 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 finite and pairwise disjoint, the result follows from Fact 1.2.23.1. 5. Let A be a nonempty finite set. Then, for any set B,A =A\B+A∩B. Proof. As A is finite, A\B and A∩B are also finite. Now, use Fact 1.2.23.1. 6. Let A be a nonempty finite set and B⊆ A, thenB≤A. In particular, if B ( A then BA. Proof. Since B =A∩B, the result follows from Fact 1.2.23.5. 7. Let n andk be two fixed positive integers. Then, there is no one-one function from n+k to n. 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 definition and Fact 1.2.23.6, n+k =B≤nn+1. Or equivalently, k 1 contradicting the assumption that k≥ 1. 8. The setN is infinite. Proof. Assume that the set N is finite 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 n+1 Proposition 1.2.15, f is also one-one, contradicting Fact 1.2.23.7. n+1 9. Let A be a finite nonempty set and x be a fixed symbol. Now, consider the set B = (x,a)a∈A. Then,A =B. Proof. Define the function f : A→ B by f(a) = (x,a), for all a∈ A. Then, f is a bijection. 10. Let A be an infinite set and B⊇A. Then, B is infinite. Proof. If B is finite then by Fact 1.2.23.3, A is finite. A contradiction to A being an infinite set. 11. Let A be an infinite set and B be a finite set. Then, A\B is also infinite. In particular, if a∈A, then A\a is also infinite. Proof. If A\B is finite, then by Fact 1.2.23.1, the set (A\B)∪B is also finite. But A⊆ (A\B)∪B and hence by Fact 1.2.23.3, A is finite as well. A contradiction toA being an infinite set. 12. A set A is infinite if and only if there is a one-one function f :N→A. Proof. Let A be infinite. So, A6=∅. Let a ∈ A. Put f(1) = a and A = A\a. By 1 1 1 1 Fact 1.2.23.11, A is infinite. Assume that we have defined f(1),...,f(k) and obtained 1 A =A \a. As A was infinite, by Fact 1.2.23.11, A is infinite. Hence, A =6 ∅. k k−1 k k−1 k k DRAFT14 CHAPTER 1. BASIC SET THEORY Let a ∈A . Definef(k+1) =a and A =A \a . By applying induction, f k+1 k k+1 k+1 k k+1 gets defined 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 finite thenN is finite as well, contradicting Fact 1.2.23.8. Hence, f(N) is infinite. As f(N)⊆A, using Fact 1.2.23.10, A is infinite as well. 13. A set is infinite if and only if it is equivalent to a proper subset of itself. Proof. Let S be an infinite set. Then, by Fact 1.2.23.12, there is a one-one function ( x, if x6∈f(N) f :N→ S. Now define 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 finite and letS = n. Then, by Fact 1.2.23.6, T is also finite andT = m n. On the other hand, by the assumption that S is finite 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 satisfies 1. 1∈S and 2. k+1∈S whenever k⊆S holds. Then, S =N. Proof. Define T =k∈ S k⊆ S. Then, 1∈ T as 1∈ S and 1⊆ S. Now, suppose k∈T. Then, by definition 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 satisfies 1. k ∈S and 0 2. k+1∈S wheneverk ,k +1,...,k⊆S. 0 0 Then,k ,k +1,...⊆S. 0 0 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 definition of T, we have k+1∈T and hence using 0 0 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 fixed 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 result follows. 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. 0 Then, y∈S and hence S is a nonempty subset ofN . Therefore, by the well-ordering principle 0 (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 0 statement ‘P(n) is true, for each n∈N,n≥ k ’. Then, ‘P can be proved using the weak form 0 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. 0 Therefore, we can establish that P(n+1) is true if P(k ),...,P(n) are true. Hence, P can be 0 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, define 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, 0 0 weknowthatP hasbeenprovedusingthestrongformofPMI.Thatis,P(n+1)istruewhenever P(ℓ) is true for ℓ =k ,k +1,...,n. This, in turn, means that Q(n+1) is true. Hence, by the 0 0 weak form of PMI, Q(n) is true for all n≥ k . Thus, we are able to prove P using the weak 0 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 √ 1 n n Arithmetic Mean (AM):= ≥ a ···a =: (GM) Geometric Mean. 1 n n 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 . Define A = . Then, 1 1 n+1 n+1 1 n+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 to get p a +···+a +(a +a −A) 2 n 1 n+1 n a ·····a ·(a +a −A)≤ =A. 2 n 1 n+1 n 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. n(n+1) Example 1.3.8. Prove that 1+2+···+n = . 2 n(n+1) Ans: The result is clearly true for n = 1. So, let us assume that 1+2+···+n = . 2 Then, using the induction hypothesis, we have n(n+1) n+1 1+2+···+n+(n+1) = +(n+1) = (n+2). 2 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. n(n+1)(2n+1) 2 2 2 1. 1 +2 +···+n = . 6 2 2. 1+3+···+(2n−1) =n , for all n∈N. 3. n(n+1) is even, for all n∈N. 3 4. 3 divides n −n, for all n∈N. DRAFT1.3. MORE ON THE PRINCIPLE OF MATHEMATICAL INDUCTION 17 5 5. 5 divides n −n, for all n∈N. Practice1.3.10. WronguseofPMI:Canyoufindtheerror? 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 error. 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 k+1 k+1 collection B of k balls that contains at least one green ball. Then, by the induction hypothesis, k each ball in B is green. Now, remove one ball from B and put the ball which was left out in k k ′ ′ the beginning. Call it B . Again by induction hypothesis, each ball in B is green. Thus, each k k ball in B is green. Hence, by PMI, our proof is complete. k+1 Exercise 1.3.11. Optional n+1 n P x −1 2 n k 1. Let x∈R with x =6 1. Then, prove that 1+x+x +···+x = x = . x−1 k=0 2. Let a,a+d,a+2d,...,a+(n−1)d be the first n terms of an arithmetic progression. Then, n−1 X n S = (a+id) =a+(a+d)+···+(a+(n−1)d) = (2a+(n−1)d). 2 i=0 2 n−1 3. Let a,ar,ar ,...,ar be the first n terms of a geometric progression, with r =6 1. Then, n n−1 P r −1 n−1 i S =a+ar+···+ar = ar =a . r−1 i=0 4. Prove that 3 (a) 6 divides n −n, for all n∈N. 7 (b) 7 divides n −n, for all n∈N. 2n (c) 3 divides 2 −1, for all n∈N. 2n (d) 9 divides 2 −3n−1, for all n∈N. 9 (e) 10 divides n −n, for all n∈N. 2n+2 4 2 (f) 12 divides 2 −3n +3n −4, for all n∈N.   2 n(n+1) 3 3 3 (g) 1 +2 +···+n = . 2 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. n 2 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 n (1+r) ≥ 1+rn for all n∈N. (1.3) 12. Informative Prove that for µ 0,   p 2 2 Y p(p+1) 1 p (p+1) p(p+1)(2p+1) 2 (1+lµ )≥ 1+ µ + − µ . 2 2 4 6 l=1 13. Informative By an L-shaped piece, we mean a piece of the type shown in the picture. n n Consider a 2 ×2 square with one unit square cut. See picture. A B α β C γ L-shaped piece 4×4 and 8×8 squares with a unit square cut n n 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 2 2   2 a +a 1 2 a ···a . 3 9 2 (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 fixed nonnegative real numbers such that the sum a +···+a =r . 1 n 1 n 0 n Conclude from the previous item that (r /n) ≥a ···a , the AM-GM inequality. 0 1 n 1.4 Integers 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 0 subset of N . Therefore, by the Well-Ordering Principle, S contains its minimum, say s . So, 0 0 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 0 0 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 Definition 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. Discussion: Ifaisanonzerointegerthenthesetofpositivedivisorsofaisalwaysnonempty (as 1a) and finite (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 finite. 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 define 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 ). 1 n 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 definition 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 0 0 as x ,y ∈Z. We now show that da and db. 0 0 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. Thedivisionalgorithmgivesusanideatoalgorithmicallycomputethegreatestcommondivisor 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 find the greatest common divisor of two given nonzero integers. This is called the Euclid’s algorithm. For example, to find 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 0 0 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 infinite number of choices for the pair 2 (x,y)∈Z , for which d =ax+by. 4. Euclid’salgorithm Ingeneral,giventwononzerointegersaandb,thealgorithmproceeds as follows: 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 0 ℓ+1 and r can be recursively obtained, using backtracking. That is, ℓ+1 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 b (a) If gcd(a,b) =d, then gcd( , ) = 1. d d (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, specified 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 definitions. Definition 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 or pb. Proof. If pa, we are done. So, assume that p∤a. As p is a prime, gcd(p,a) = 1. Thus, we can find 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 omitted. 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 k k s t 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 . i i 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 n to get the required result. p Theorem 1.4.11. Euclid: Infinitude of primes The number of primes is infinite. Proof. On the contrary assume that the number of primes is finite, 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 1 r integer N. Now, let r be the largest positive integer such that 2 ≤ n. Then, N− = r 2 1 1 1 1 r r 1+ +···+ + +···+ . Also, let K = lcm(2,3,...,2 −1,2 +1,...,n). Then, r r 2 2 −1 2 +1 n r r note that 2 does not divide K as r was the largest positive integer such that 2 ≤n. Also, we see that r N·2 −1 M = r 2 K r r for some positive integer M. Or equivalently, 2 M = K(N· 2 − 1). Thus, we arrive at a r 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 a contradiction. Exercise1.4.14. Informative Prove that there are infinitely many primes of the form 4n−1. Definition 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 and b. 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 1 2 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 1 1 that c cd c(as+bt) c c = = = s+ t∈Z a b d (a d)·(b d) ab b a 1 1 1 1 c c as , ∈ Z and s,t∈ Z. Thus, a b d = lcm(a,b) divides c and hence lcm(a,b) is indeed the 1 1 a b 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. Definition 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 2. Let n∈N be a perfect square. That is, there exists an integer m such that n =m . Then, 2 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 verified 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 fixed 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. n−1 S (b) Thus, the set of integers,Z = a+kn :k∈Z. Thatis, every integer is congruent a=0 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) m m 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 n gcd(c,n) = 1. In general, a≡b (mod ). gcd(c,n) 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 m m 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 n Corollary 1.4.9, we get =n a−b. 1 gcd(c,n) Asanapplication, wehavethefollowingresult,popularlyknownastheFermat’slittletheorem. p Theorem 1.4.21. Fermat’s Little Theorem Let p be a prime and n ∈ N. Then, n ≡ n (mod p). p Proof. Note that if pn, then obviously, n ≡ n (mod p). So, let us assume that gcd(p,n) = 1. p−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, p−1 n (p−1) =n·2n·····(p−1)n≡ 1·2·····(p−1). 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. 12 12 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 definition, ax −b = nq, for some 0 0 q∈Z. Thus, b =ax −nq. But, gcd(a,n)a,n and hence gcd(a,n)ax −nq =b. 0 0 Suppose d = gcd(a,n) b. Then, b = b d, for some b ∈ Z. Also, by Euclidean algorithm, 1 1 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 first part. To proceed further, assume that x ,x are two solutions. Then, ax ≡ ax (mod n) and 1 2 1 2 n n hence, by Theorem 1.4.20.4, x ≡ x (mod ). Thus, we can find x ∈0,1,..., such that 1 2 2 d d n x =x +k is a solution ofax≡b (mod n), for 0≤k≤d−1. Verify that thesex’s are distinct 2 d 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 first case and k = 22 for the other. Hence, x = 20+28·21 = 608 = 14+22·27 is a solution of the above pair.  p p 8. Let p be a prime. Then, prove that p = , for 1≤k≤p−1. k k(p−k) 9. Informative Let p be a prime. Then, the set (a) Z =0,1,2,...,p−1 has the following properties: p i. for every a,b∈Z , a+b (mod p)∈Z . p p ii. for every a,b∈Z , a+b =b+a (mod p). p iii. for every a,b,c∈Z , a+(b+c)≡(a+b)+c (mod p). p iv. for every a∈Z , a+0≡a (mod p). p v. for every a∈Z , a+(p−a)≡ 0 (mod p). p ∗ (b) Z =1,2,...,p−1 has the following properties: p ∗ i. for every a,b∈Z , a·b (mod p)∈Z . p p ∗ ii. for every a,b∈Z , a·b =b·a (mod p). p ∗ iii. for every a,b,c∈Z , a·(b·c)≡ (a·b)·c (mod p). p ∗ iv. for every a∈Z , a·1≡a (mod p). p ∗ v. for every a∈Z , a·b≡ 1 (mod p). To see this, note that gcd(a,p) = 1. Hence, p by Euclid’s algorithm, there exists x,y∈Z such that ax+py = 1. Define b≡ x (mod p). Then, a·b≡a·x≡a·x+p·y≡ 1 (mod p). DRAFT