Class Notes (839,315)
Canada (511,260)
Mathematics (1,919)
MATH 135 (334)
Lecture

MATH135 - September 9-December 2, 2013

39 Pages
129 Views

Department
Mathematics
Course Code
MATH 135
Professor
Ross Willard

This preview shows pages 1,2,3,4. Sign up to view the full 39 pages of the document.
Description
⇚ Return to University Notes index MATH 135 Mathematical proofs. Section 004 Instructor: Name: Ross Willard Email: [email protected], [email protected] Office Hours: Tuesdays 9:00AM-10:00AM , Fridays 1:00PM-2:00PM, in MC 5058 Tutorials: Tuesdays 4:30PM-7:20PM (Drop-in to Biology 1 Room 271) 9/9/13 Show √ x(x − √ x) = x(1 − √ x): √ x( √ √− √ x) = √ √ x(1 − √ x) √ √ x( x√ 1) = √ √ x(1 − √ x) This is not a proof. Proofs: Avoid starting with thing trying to be proved (assuming the thing is true) Use english sentences to give details. Prove thax ≥ 2x ▯ x ≤ 0 ∧ x ≥ 2: Let x represent a real number. ;start by declaring assumptions 2 Assume2x ≥ 2x . Thenx − 2x ≥ 0 . Thenx(x − 2) ≥ 0 . This implies that ex ≥ 0 and x ≥ 2 , or thx ≤ 0 andx ≤ 2 . Ix ≥ 0 andx ≥ 2 , thex ≥ 2 . Ix ≤ 0 andx ≤ 2 , thex ≤ 0 . In conclusiox ≤ 0 and x ≥ 2 ix ≥ 2x . Check the converse: Assume x ≤ 0 , thex ⋅ x ≥ 0and2x ≤ 0 . 2 Thereforex ≥ 2x . Assume x ≥ 2 , thex ⋅ x >= 2x. Thereforex ≥ 2x . In conclusiox ≤ 0 and x ≥ 2 if and onlx ≥ 2x . 1 Show x + x >= 2 for ax > 0 : Letx represent a positive real number. Certainl(x − 1) ≥ 0 is true. 2 So x −22x + 1 ≥ 0 . 2 Thusx − 2x + 1 + 2x ≥ 0 + 2x , and is equivalenx + 1 ≥ 2x . 2 1 + 1 ≥ 2x x + ≥ 2 1 Since x > 0 , + 1 ≥ 2x is equivalent to+ x ≥ 2 . 1 Hence x + x ≥ 2 , which was to be proved. In handwriting,▯ (double right arrow) is considered an acceptable replacement for "Therefore", "Hence", "Then", "Thus". A proposition is a true statement, proved with a valid argument. A theorem is an important or significant proposition. A lemma is a helper proposition used in the proof of a theorem. A corollary is a proposition that follows almost immediately from a theorem. An axiom is a statement is assumed to be true, no proof needed. Propositions are derived from these. Summary Written solutions are primarily done in English. Proofs start with relevant assumptions or known true statements, and ends with the thing to be proved. 11/9/13 2 2 Show (x + y) − (x − y) = 4xy : Letx and y represent real numbers. 2 2 2 2 2 2 Clearly(x + y) − (x − y) = x + 2xy + y − (x − 2xy + y ) . Clearlyx + 2xy + y − (x − 2xy + y ) = x + 2xy + y − x + 2xy − y 2 2. 2 2 2 2 Clearlyx + 2xy + y − x + 2xy − y = 2xy + 2xy . Thus,(x + y) − (x − y) = 4xy by transitivity of equality. In the interests of style, multiple equalities can be written thus: Letx and y represent real numbers. 2 2 2 2 2 2 Clearly(x + y) − (x − y) = 4xy = x + 2xy + y − (x − 2xy + y ) , ⇒ x + 2xy + y − (x − 2xy + y ) = x + 2xy + y − x + 2xy − y 2 2, 2 2 2 2 ⇒ x + 2xy + y − x + 2xy − y = 2xy + 2xy . Thus,(x + y) − (x − y) = 4xy by transitivity of equality. (here,, means "which in turn") Only statements can imply other statements. Statements are sentences that can be true or false. They are complete sentences with subject(s) and verb(s). 2 + 2 = 4 (true statement: subject verb subject verb subject) 2 The equation x − 1 = 0 has 2 distinct real roots (true statement: subject verb subject) x > 0 (context required: open sentence) Compound statements are composed of several component statements: 0 < x < 1 Which is in fact: 0 < x and x < 1 abs(x) = 2 Which is in fact: 0x = 2 or x = -2 If A and B are statements, thA ∧ B (A wedge B) means "A and B ". If A and B are statements, thA ∨ B (A vee B) means "A and B ". If A and B are statements, thA ▯ B (A impliesB ) means "B is true whenA is true". The general formhypothesis implies conclusion . When proving with this, it is only necessary to prove that it is impossible for the hypothesis to be true but the conclusion to be false. For example, one can simply prove the hypothesis is always false, or the conclusion is always true. These statements commonly take the following forms: A impliesB. IA , theB . AsA , therefoBe. AsA , hencB . If 1 = 2, then 1 = 0. This implication is true, since the hypothesis is false. Implications are always true as long as the hypothesis is not true while the conclusion is false. If A and B are statements,A ▯en B (A if and onlyB) means A is true only whBis true". T represents truFrepresents false. IfA is a statement, ¬Aen(notA) means "noA ". Laws of Logic A ∧ (B∨ C) ≡ (A ∧ B) ∨ (A ∧ C) A ∨ (B∧ C) ≡ (A ∨ B) ∧ (A ∨ C) - distributivity law A ∧ B ≡ B∧ A A ∨ B ≡ B∨ A - commutativity law (A ∧ B) ∧ C ≡ A ∧ (B∧ C) (A ∨ B) ∨ C ≡ A ∨ (B∨ C) - associativity law Truth tables Truth tables show the truth value of a compound statement by determining the values of the component statements. Two statementsA andB are logically equivalent if and only if they have the same truth values in the A ≡ B ttole. We write represent this. AreA ▯ B and (¬A) ∨ B logically equivalent? (¬A) ∨ B A B A ▯ B T T T T T F F F F T T T F F T T Since both have the same truth table values, they are logically equivalent. 13/9/13 If an intemerdivides integnwithout any remainder, we wrm ∣ n. In other wor∃k ∈ Z,n = km . 3 ∣ - True statement6 = 2 ⋅ 3 7 4 ∣ - False statemen7 = 4⋅ 4 0 ∣ - True statement0 = 0 ⋅ 0 1|2is a statement, whilis an operation. 2 Sets A set is a collection of objects. The objects are called elements or members. Elements can be anything: numbers, letters, functions, cats, or even themselves sets. NotationA = {2,4,6,8} B = {1,2,…,98,99} Conventionally, we use capital letters to name identifiers that are sets. Common sets: N - natural numbers{1,2,3,…} Z - integer{…,−2,−1,0,1,2,…} R - real numbers Q - rational numbers - Q¯- irrational numbers C - complex numbers ∅- empty set An object belongs to a set if it is an ea ∈ Bt means "a is an element of B". All sets contain the empty set. A statement is a sentence that is either true or false. As a result, the following are not statements: 6 ∣ x x + 1 > 0 x ∈ {2,4,6,8} Are these true or false? It is not possible to know, sinxeis unknown.of An open sentence appears to be a statement, but contains unknowns (variables). In order to be a statement, the sentence must be viewed in a context where all these unknowns are given a value in their domain, and is either true or false when this is done. A variable is a symbol that always represents an element or elements from a designated set known as the domain. Set builder notation is used when there are too many elements in a set to list all of them. One way of writing it is as follows (type I): {x ∈ R 0 ≤ x < 2} {x ∈ N : 6 ∣ n} = {6,12,18,24} {var ∈ domain ( or : ) open_sentence} "Set ovar indomain such thaopen sentence" There is another set builder notation (type II): {3n + 1 n ∈ N} = {4,7,10,13,…} { x ∣n ∈ N} = [−0.5,0.5] x + 1 ∣ {function(var) ( or : ) var ∈ domain} "Set of valuesfunction(var) asvar ranges ovedomain " All other forms of set builder notation are incorrect. {n ∈ N n ∈ N} - valid type I set builder notation; "set of those natural numbers that belong to the set of real numbers" {x x ∈ R} - valid type II set builder notation; "set of all x such that x is a real number" 16/9/13 Basic Set Operations The union oA andB iA ∪ B . This is the set of all elements belongiAg orBe. This can be written as x ∈ A ∪ B ▯ x ∈ A ∨ x ∈ B , and is sometimes definA ∪ B = {x ∣ x ∈ A ∨ x ∈ B} . The intersection Afand B isA ∩ B . This is the set of all elements belonging to both A and B. This can be written as x ∈ A ∩ B ▯ x ∈ A ∧ x ∈ B , and is sometimes definA ∩ B = {x ∈ A x ∈ B} . The difference Af andB isA − B orA ∖ B . This is the set of all elements beA, but not Bo. This can be written as x ∈ A − B ▯ x ∈ A and x ∉ B , and is sometimes defineA − B = {x ∈ A x ∉ B} . The complement of a seA isA¯. This is the set of all elements in the universe of discourseAt.at are not in The cardinality of aAsis∣A∣. This is the number of elements it contains. We can construct a truth table of these operations: x ∈ A x ∈ B x ∈ A ∪ B x ∈ A ∩ B x ∈ A − B T T T T F T F T F T F T T F F F F F F F Two sets are equal if and only if they have exactly the same element{1,2,3} = {3,2,1} : "A is equal to B"). Inclusion: a set is a subset of another if every element of the first set is also contained in the {1,2} ⊆ {3,2,1} : "A is a subset of B"). In other word∀x ∈ A,x ∈ B . If a set is a subset of another, the second set is a superset of the first. A set is a proper subset of another if it is a subset and it is not{1,2} ⊂ {3,2,1} : "A is a proper subset of B"). n The number of subsets of any set i2 , where n is the number of elements in the set. List all the subsets{a,b,c} : We create a list of tuples of 0 and 1 of length 3, each one unique: (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) . This can be done via binary counting. Each position in the tuple corresponds to one element of the set. For example, position 1 corresponas, position 2 corresponds tob , and position 3 corresponds tc. For each tuple, we construct a set that contains only those elements that correspond to positions that have the value 1 in the tuple. These sets a∅,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c} . These are the subsets of the s{1,2,3} . Proving a statement of the formA ⊆ B : Let x be /assume x is a random /arbitrary /representative element of A Argue that x must be an element of B. This proves∀x,x ∈ A ▯ x ∈ B , which provesA ⊆ B . Prove {n ∈ N : 4 ∣ n} ⊆ {n ∈ N : 2 ∣ n} : LetA represent the first set. LetB represent the second set. Letx be an arbitrary element of A. Lety be an arbitrary element of B. Given that for Ax ∈ N and 4 ∣ x, we know that there must exist an integkrsuch that x = 4k . Given that for y ∈ N and 2 ∣ y, we know that there must exist an integkrsuch thaty = 2k . Clearlyx = 2(2k) . ′ ′ ′ So there must exist an integek such that x = 2k ; namely,k = 2k . Hence x ∈ N and 2 ∣ x. Therefore,x ∈ B . Sincex is arbitrary∀x,x ∈ A ▯ x ∈ B . Proving a statement of the formA = B has two general techniques: Technique 1: prove A ⊆ B , and then proveB ⊆ A , using the above strategy: "prove thaA iand B are sets, A − B = A = (A ∩ B) ". Letx be an arbitrary element ofA . So x ∈ A and x ∉ B . Ix ∈ A ∩ B , thenx ∈ A and x ∈ B . However, we know that x ∉ B . Therefore,x ∉ A ∩ B . Sincex ∈ A and x ∉ A ∩ B ,x ∈ A − (A ∩ B) . Sincex ∈ B ∀x ,A − B ⊆ A − (A ∩ B) . Now we prove the reverse. Lety be an arbitrary element oA − (A ∩ B) . Sox ∈ A and x ∉ A ∩ B . So (by DeMorgan's Law) x ∉ A , orx ∉ B . However, x ∈ A , sx ∉ B . Since x is representati∀x,x ∈ (A ∩ B) , andA − (A ∩ B) ⊆ A − B . Since both sides are subsets of or equal to each other, they are equal. 18/9/13 Technique 2: Prove tha∀x,x ∈ A ▯ x ∈ B : Let x be an arbitrary object. Ifx ∈ A , thex ∈ B . Ifx ∉ A , thex ∉ B . Therefore,x ∈ A ▯ x ∈ B . Prove that for any seRs,S ,T ,R∩ (S ∪ T) = (R∩ S) ∪ (R∩ T) . Let x be an arbitrary object. We know that x ∈ R∩ (S ∪ T) ▯ x ∈ R∧ (x ∈ S ∨ x ∈ T) . Recall thatP ∧ (Q ∨ R ≡ (P ∧ Q) ∨ (P ∧ R) . Clearly,x ∈ R∧ (x ∈ S ∨ x ∈ T) ▯ (x ∈ R∧ x ∈ S) ∨ (x ∈ R∧ x ∈ T) . This technique is only usable in certain situations. At other times, technique 1 is a better choice. A ≡ B is not equality, it works on two logical proposAtiand B . Quantifiers Two common phrases in math: Universal:open sentence for alsomething ; for eversomething , open sentence . Existentialopen sentence for some [something]; there exists a [something] such that statement. This can be written using quantifier symbols: ∀x ∈ R.x ≥ 0 2 For every element x in the seR , it is true x ≥ 0 . In short, for every real numbxr,x ≥ 0 . ∃x ∈ R,x − 3x + 2 = 0 There exists an elementx in the seR such thatx − 3x + 2 = 0 . 2 In short, there exists a real numxesuch thatx − 3x + 2 = 0 . Quantifiers are not part of the hypothesis or conclusion - they are se∀x,P(x) ▯ Q(x) is the same as writing ∀x,(P(x) ▯ Q(x)) . The hypothesis would beP(x) and the conclusion would beQ(x) . A quantified statement takes the form of(∀ or ∃)x ∈ S,open sentence . Negating a statement: A -f(x) has a real root. ¬A -f(x) does not have a real root. B - every integer is even. ¬B - some integer is not even. Formally: A : ∃x ∈ R,f(x) = 0 ¬A : ∀x ∈ R,f(x) ≠ 0 B : ∀x ∈ Z,2 ∣ x ¬B : ∃x ∈ Z,2 ∤ x Negate the statement every even integer is a power of 2 . A : ∀x ∈ Z,2 ∣ x ▯ x is a power of 2 . ¬A : ∃x ∈ Z,¬(2 ∣ x ▯ x is a power of 2) . Recall that¬(P ▯ Q) = P ∧ ¬Q . So the above is equivalent t¬A : ∃x ∈ Z,2 ∣ x ▯ x is not a power of 2 . There exists an integer which is even but is not a power of 2. General rules for negation: ¬(∀x ∈ S,P) ≡ ∃x ∈ S,¬P ¬(∃x ∈ S,P) ≡ ∀x ∈ S,¬P ¬(P ∧ Q) ≡ (¬P) ∨ (¬Q) - DeMorgan's law ¬(P ∨ Q) ≡ (¬P) ∧ (¬Q) - DeMorgan's law ¬(P ▯ Q) ≡ P ∧ (¬Q) ¬(P ▯ Q) ≡ P ▯ (¬Q) Proving quantified statements To prove ∀x ∈ S,P , use the select method: Let x be an arbitrary/representative/random element oS . Prove thatx makes P true. Prove A ∩ B ⊆ A : We must prove that ∀x ∈ A ∩ B,x ∈ A . Let x be a representative element A ∩ B . So x ∈ A and x ∈ B . Since P holds for any representative elemenx ,∀x ∈ A ∩ B,x ∈ A . Therefore,A ∩ B ⊆ A . To prove ∃x ∈ S,P , use the construct method: Construct/define/exhibit a specific elemextofS . Show that P is true for txi. Since x satisfiex ∈ S , this prove∃x ∈ S,P . Prove that8 ∣ (2013 − 1) : In other words, we must prove∃k ∈ Z,8k = 2013 2 − 1 . 2 Note: 2013 − 1 = (2013 + 1)(2013 − 1) = 8 ⋅ 1007 ⋅ 503 . Let k represent1007 ⋅ 503 . So 8k = 4(503) ⋅ 2(1007) , o(2013 − 1)(2013 + 1) . Clearly, this is equivalent to 2 . 2013 − 1 2 Then there exists an integer multiple of 8 equa2013 − 1 . Therefore,8 ∣ (2013 − 1) . ;wip: read chapter 14, 15, 10, 11 by Sept. 23 Prove or disprove that every real number has a real square root: 2 Let A represent the statement. In other wordA,is∀x ∈ R,∃y ∈ R, y = x (for every real numberx, there exists a real number y such thaty = x ). The negation of the statement¬A is∃x ∈ R,∀y ∈ R, y2 ≠ x . By proving the negation true, we can prove the statement false. Note: construct method Construct x = −1 . Note: select method Let y b2 a random element ofR . Then y ≥ 0 . So y ≠ −1 . As y is an arbitrary real number, this pro∀y ∈ R, y 2 ≠ x . 2 Since x satisfiex ∈ R , this prove∃x ∈ R,∀y ∈ R, y ≠ x . Therefore,¬A is true, aAd is false. In order to prove something false, we generally need to prove its negation true. Prove or disprove that for every real number, there is some integer greater than it: Let A represent the statement. In other words,A is∃n ∈ Z,∀x ∈ R,n > x . The negation of the statement¬A is∀n ∈ Z,∃x ∈ R,n ≤ x . By proving the negation true, we can prove the statement false. Note: select method Letn be a random element of Z . Note: construct method Letx = n . Certainly,x ∈ R , andn ≤ x . Since x satisfiex ∈ R , this prove∃x ∈ R,n ≤ x . As n is a random element ofZ , this prove∀n ∈ Z,∃x ∈ R,n ≤ x . 23/9/13 Implications An implication is a compound statement of the formP ▯ Q P impliesQ ). The hypothesis P ) implies the conclusionQ() Examples: Ifn is odd, the24 ∣ n. Implicit∀n ∈ Z . x ∈ A ∪ B ▯ x ∈ A . Implicitl∀x ∈ A ∪ B Quantifiers are separate from implications. For exampl∀x ∈ R,x = y ▯ x = x , the hypothesisx = y . This statement is equivalent t∀x ∈ R,(x = y ▯ x = x) The core technique for proving an implication is known as direct proof: 1. Assume the hypothesis. 2. From the hypothesis, deduce the conclusion. The converse of an implicatioP ▯ Q isQ ▯ P . This is very different from the original implication. When we prove a statement and its converse, we have proved tP ▯ Q . For an implication with a quantifier, the quantifier is preserved for its converse; the∀x ∈ S,P(x) ▯ Q(x) is ∀x ∈ S,Q(x) ▯ P(x) . The converse of "If Bob is a student at uWaterloo, then Bob is a student in Canada" is "If Bob is a student in Canada, Bob is a student at uWaterloo". The contrapositive of an implicatioP ▯ Q is¬Q ▯ ¬P . This is logically equivalent to the original statement; in other words, P ▯ Q ≡ ¬Q ▯ ¬P . It is occasionally easier to prove the contrapositive rather than the original statement, usually when there are binary choices in the hypothesis and conclusion. The negation of an implicatioP ▯ Q isP ∧ ¬Q . This is a statement that is true whenever the original statement is true, and false whenever the original statement is true. This can be proven using truth tables. 2 2 Prove that∀x ∈ Z,32 ∤ (a + 3)(a + 7) ▯ 2 ∣ a: This is difficult to prove since "not divisible" has few useful properties. We replace the statement with its contrapositive to simplify it. 2 2 The contrapositive i∀x ∈ Z,2 ∤ a ▯ 32 ∣ (a + 3)(a + 7) . Assume 2 ∤ a. Clearly,acan be written a2k + 1,k ∈ Z . 2 2 2 2 2 2 Clearly,(a + 3)(a 2 7) is equivale2t t(4k + 4k + 4)(4k + 4k + 8) , o16(k + k + 1)(k + k + 2) . CLearly, eithe2 ∣ k + k + 1 or2 ∣ k + k + 2 . So ∃l ∈ Z,(k + k + 1)(k + k + 2) = 2l . Clearly,16(k + k + 1)(k + k + 2) is equivalent 32l. 2 2 Clearly,32 ∣ 32l, s32 ∣ (a + 3)(a + 7) . Therefore,∀x ∈ Z,32 ∤ (a + 3)(a + 7) ▯ 2 ∣ a. The inverse of an implicatiP ▯ Q is¬P ▯ ¬Q . Like the converse, this is also very different from the original implication. Another technique for proving is proof by contradiction: 1. Assume the hypothesis is true. 2. Suppose the conclusion is false. 3. Derive a contradiction, suc1 = 0 . 4. Since the implication cannot be false and result in a contradiction, it is true. To prove A ▯ B , we can provA ▯ B and B ▯ A . Proof Technique: Induction Full name is "Principle of Mathematical Induction". Useful for proving statements of the f∀n ∈ N,P(n) , whereP(n) is a statement. Also usable for integers greater than 5, -3, or any value. It can also be used for integers less than some valP(k − 1)roving rather thanP(k + 1) in the inductive conclusion. 2 ∀n ≥ 1,1 + 3 + 5 + ⋯ + (2n − 1) = 2 Prove ∀n ≥ 1,1 + 3 + 5 + ⋯ + (2n − 1) = n : 1. Base case: verify P(1) is true. 2. Inductive hypothesis: assume that P(k) is true for some fixed integek ≥ 1 . 3. (Work towards conclusion) 4. Inductive conclusion: using the inductive assumption, prove that P(k + 1) . 5. End: therefore, P for aln ≥ 1 , by the principle of mathematical induction. We can only assume statements. Base case: P(1) is1 = 1 2, which is true. Inductive hypothesis: assume that, for some fixed k ≥ 1 ,P(k) is true. The next term is (2k − 1) + 2 . Adding this to both sides yields 1 + 3 + 5 + ⋯ + (2k − 1) + (2k + 1) = k + (2k + 1)2 . 2 2 Clearly,k + (2k + 1) = (k + 1) . So 1 + 3 + 5 + ⋯ + (2k − 1) + (2k + 1) = (k + 1) 2. Inductive conclusion: Clearly,P(k + 1) is also true. 2 Therefore, for aln ≥ 1,1 + 3 + 5 + ⋯ + (2n − 1) = n . n(n−1) Prove that ∀n ∈ N , the number of 2-element subsets of the set {1,2,…,n} is 2 : This is true fon = 1 :{1} has no 2-element subsets, and is 1(1−1) = 0 . 2 k(k−1) Assume that for some fixed k ≥ 1 ,P(k) is true. That is, count of subsets {1,2,…,k} is . 2 Note that {1,2,…,k + 1} is equivalent to{1,2,…,k} ∪ {k + 1} . Note that the two element subsets of this can be put in two groups: * those that do not contain k + 1 , which are the 2-element subsets of {1,2,…,k} . * those that do contain k + 1 , which are of the form,{a,k + 1},1 ≤ a ≤ k . By the inductive hypotheses, we know that the number of subsets belonging to the first group are k(k−1). 2 We know that the number of subsets belonging to the second group is simply k . k(k−1) So the num2er of subsets of {1,2,…,k + 1} is 2 + k . Clearly, k +k = (k+1)k, or (k+1)((k+1)−1). 2 2 2 Therefore, the number of 2-element subsets of the set {1,2,…,n} is n(n−1) for alln ≥ 1 . 2 Principle of Mathematical Induction A meta-statement at the basis of proof by induction. It is itself a true statement; an axiom. Let P(n) is a statement that depends on n ,n ∈ N . Let b ∈ Z . Let k ∈ Z,k ≥ b . IfP(b) is true, andP(k) ▯ P(k + 1) , thenP(n) is true. 25/9/13 Prove ∀n ≥ 3,n! > 2 2n−4 using induction: Base case: For n = 1 ,3! > 2 2(3)−4, which is equivalent to6 > 4 , which is true. 2k−4 Inductive hypothesis: Assume that for some fixed integer k ≥ 3 ,k! > 2 . For k + 1 , we want to check if(k + 1)! > 2 2(k+1)−4 . 2(k+1)−4 2k+2−4 Clearly,(k + 1)! > 2 is equivalent tok!(k + 1) > 2 . Clearly,k!(k + 1) > 2 2k+2−4 is equivalent tok!(k + 1) > 2 2k−4 4. Clearly,k!(k + 1) > 2 2k−4 4 is equivalent tok+1 k! > 2 2k−4 . 4 Since k + 1 ≥ 4 ,k+1 ≥ 1 , andk+1 k! ≥ k! . k+1 k+1 2k−4 Since 4 k! ≥ k! , 4 k! > 2 . Inductive conclusion: So (k + 1)! > 2 2(k+1)−4 is true ik! > 2 2k−4 . 2n−4 Therefore, ∀n ≥ 3,n! > 2 , by the principle of mathematical induction. 27/9/13 Strong Induction The induction done to this point is known as simple induction. When this is not possible, there is also strong induction, which is basically the same thing, generalized to work with more base cases. Strong induction is useful for proving statements of the f∀n ≥ 1,P(x) . 1. Base case: verify thP(1)…P(b) are true, for someb ≥ 1 . 2. Inductive Hypothesis: assume thaP(1)…P(k) are true, for somk ≥ b . 3. (Work towards conclusion) 4. Inductive conclusion: therefoP(x) is true for ax ≥ 1 , by the principle of strong induction. ;wip: principle of strong induction n−1 Given thatf is the n-th number in the Fibonacci sequenc{1,1,2,3,5,…} ), provef ≤ ( ) : n n 3 5 0 Base case: Forn = 1 ,1 ≤ ( 3 , or1 ≤ 1 , which is true. 1 Base case: Forn = 2 ,1 ≤ ( 3 , or1 ≤ 3 , which is true. k−1 Inductive hypothesis: Assume that for some integek ≥ 2 ,f ≤ ( ) . k 3 5 k For k + 1 , we want to check ifk+1 ≤ ( 3 . 5 k 5 5 k−1 Clearly,fk+1 ≤ ( 3 is equivalent tfk+ f k−1 ≤ 3 ( 3 . k−1 Clearly,fk+ f k−1 ≤ ( ) + f k−1. 3 ;wip How many cases should be verified (i.e., what is the valub?)? As a general rule, if the prooP(k + 1) requires thatk ≥ x , then x is the smallest possible value b.r Studying Divisibility Recall that n ∈ Z and m ∈ Z , m ∣ n ▯ ∃k ∈ Z,n = km Transitivity of divisibiilty (TD) Proposition: for integeas,b,c, ia ∣ band b ∣ , thena ∣ c. Proof: Let a,b, andc be arbitrary integers. Assume that a ∣ band b ∣ . This means ∃r ∈ Z,b = ra and ∃s ∈ Z,c = sb . Let k = sr , sok ∈ Z . Clearly,c = sb = s(ra) = (sr)a = ka . So ∃k ∈ Z,c = ka . Since a,b , andcare arbitrary, this is true for all integers. ;wip: read chapter 18 Divisibility of integer combinations (DIC) Proposition: for integea b, , anc , a ∣ band a ∣ c, thea ∣ (bx + cy),x ∈ Z,y ∈ Z (a divides every ILC oband )c ILC: integer linear combination, any integer of the bx + cy,x ∈ Z,y ∈ Z . Proof: Let a b c be arbitrary integers. We are trying to prove that∀x ∈ Z,∀y ∈ Z,a ∣ (bx + cy) This means ∃r ∈ Z,b = ra and ∃s ∈ Z,c = sb . Assume a ∣ band a ∣ c Letx and y be arbitrary integers. Construct k = rx + sy . Clearlybx + cy = (ra)x + (rs)y = a(rx + sy) = ka . So a ∣ (bx + cy) . Since , , , , and are arbitrary, the statement is true for all integers. a b c x y Proposition: D plusminus C: for integersa,b,c,a ∣ (b + c) and a ∣ (b − c). Proof: Leta ∈ Z,b ∈ Z,c ∈ Z . Assume a ∣ band a ∣ . Then a ∣ (bx + cy) for anyx ∈ Z,y ∈ Z , by DIC. In particulaa ∣ (b + c) or a ∣ (b − c). Bounds by divisibility (BBD) Proposition: for integera and b , ia ∣ band b ≠ 0 a ≤ b ∣ ∣ Proof: Leta and b be arbitrary integers. Assume that a ∣ b and b ≠ 0 . So ∃k ∈ Z,b = ka . Since,b ≠ 0 and a ≠ 0 b ≠ 0 . So k ≥ 1 . Clearly∣a ≤ a k = ak = b ∣ ∣ ∣ So a ≤ b . Division Algorithm Ifa and b are integers andb > 0 , then there exisst the unique integerqand r such thata = qb + r,0 ≤ r ≤ b . q is the quotientr is the remainder. 30/9/13 GCD Greatest common divisor. Let a ∈ Z,b ∈ Z such thata and b are not both 0. Let d ∈ Z,d ≥ 0 . We can write d = gcd(a,b) , provided all of the following are true: d ∣ a ∧ d ∣ b(d is a common divisor) ∀c ∈ Z , ic ∣ a ∧ c ∣ , thenc ≤ d (d is the greatest of all the common divisors). Also,0 = gcd(a,b) , rather than undefined. This is to smooth out certain operations. The GCD is always positive. gcd(8,15) = 1 gcd(−6,−15) = 3 gcd(10,0) = 10 gcd(0,0) = 0 gcd(a,0) = a ∣ ∣ gcd(a,b) = gcd(b,a) Proposition:∀x ∈ Z,gcd(n,n + 1) = 1 . Proof: We need to prove that d = 1 satisfiesd = gcd(n,n + 1) . Letd = 1 . Clearly,a ∣ n ∧ a ∣ (n + 1) , so 1 is a common divisor. Let cbe an arbitrary integer. Assume that c ∣ n and c ∣ (n + 1) . So c ∣ ((n + 1) − n) c,∣ 1 . So c = ±1 , andc ≤ d . Therefore, d = 1 satisfies the definition of the GCD, andgcd(n,n + 1) = 1 . Proposition: ∀a ∈ Z,∀b ∈ Z,gcd(a,b) = gcd(a,a + b) Proof: We need to prove gcd(a,b) is the GCD of gcd(a,a + b) . Let a and b be arbitrary integers. Let d = gcd(a,b) . So d ∣ a ∧ d ∣ b. So d ∣ (a + b) . We need to prove that d is the greatest of the common divisors. Let cbe an arbitrary integer such that c ∣ a ∧ c ∣ (a + b). So c ∣ ((a + b) − a) , andc ∣ b. So ifc ∣ a ∧ c ∣ b,c ≤ d . Therefore, d is the GCD of a and a + b . GCD with remainders (GCD-WR) Proposition: for integersa ,b, not both 0, iq and r are integers such that a = qb + r , thengcd(a,b) = gcd(b,r) . The GCD of two numbers is equal to the GCD of the dividend of their quotient and the remainder of their quotient. Proof: Let a ∈ Z,b ∈ Z , such thata and bare not both 0. Assume q ∈ Z,r ∈ Z such thata = qb + r . Let d = gcd(a,b) . We know that d ∣ a and d ∣ b. Since , . d ∣ (ax + by) d ∣ (a − qb) We know that a − qb = r , sod ∣ r. So d ∣ b and d ∣ r - d is a common divisor of band r. Let cbe an arbitrary integer such that c ∣ b ∧ c ∣ r We know that c ∣ (bx + ry) , soc ∣ (bq+ r) . We know that bq+ r = a , soc ∣ a. So ifc ∣ a ∧ c ∣ b c ≤ d . Therefore, d is the GCD of b and r . 2/10/13 Use GCD-WR to compute gcd(322,98) : Let a = 322 ,b = 98 . So q = 3 ,r = 28 . So gcd(322,98) = gcd(98,28) . This is simpler, but if we do it again it could be even simpler. Let a = 98,28 . So q = 3 ,r = 14 . So gcd(98,28) = gcd(28,14) . This is simpler, but if we do it again it could be even simpler. Let a = 28 ,b = 14 . So q = 2 , andr = 0 . So gcd(28,14) = gcd(14,0) = 14 . This is called the Euclidean algorithm. It can be used to calculate the GCD without knowing any of the factors of a or b. General algorithm: 1. Replace the larger number in the GCD with the remainder of dividing it with the other number. 2. Repeat step 1 until the remainder is 0. 3. The non-zero number is the GCD. GCD characterization theorem (GCD-CT) Prosposition: given integera,b,d , d > 0 d ∣ a ∧ d ∣ b , andd = ax + by,x ∈ Z,y ∈ Z ,d = gcd(a,b) . In other words, if a positive integer is a common divisarand b and is a linear combination of them, then it is the GCa and b. Use GCD-CT to verify 14 = gcd(322,98) : Let , . a = 322 b = 98 Let x = −3 y = 10 . Let d = 14 . Clearly,d > 0,d ∣ a,d ∣ b . Clearly,d = ax + by . So d = gcd(a,b) . This theorem does not tell us how to fixdand y , or if they even exist. Proof: Let a,b,d be arbitrary integers. Let x,y be arbitrary integers. Let d ∈ Z,d > 0 . Assume d ∣ a ∧ d ∣ b,d = ax + by . Let c ∈ Z be an arbitrary common divisor ofa and b. Then c ∣ (ax + by), by DIC. So . c ∣ d Since d ≠ 0 c ≤ d ∣ ∣, andc ≤ d , by BBD. So d = gcd(a,b) . Extended Euclidean Algorithm (EEA) Proposition: given integera and b, we can compute gcd(a,b) , and there exist at least one pair of inxeands y such that ax + by = gcd(a,b) . Proof: ;wip There are often multiple possible valuesxoand y that can result in a linear combination. EEA Table: technique for findigcd(a,b) and integersx and y such thatax + by = gcd(a,b) all at the same time. EEA works with positive inputs only. However, since gcd(a,b) = gcd( a , b )∣ , we can simply work witha∣ and b ∣and proceed with the algorithm. Thenxsign(a) and ysign(b) are the solutions to the original equation. We start by constructing a table, always with the same initial configuration: x y r q 1 0 a 0 0 1 b 0 Then, we construct the rows after them with their recursive definitions: q1= 0 q2= 0 q = ⌊ rn−2 ⌋ n rn−1 rn= r n−2 − q ⋅ r n−1 n x n x n−2 − q n x n−1 y n y n−2 − q n y n−1 We stop when r_n = 0. The value ofr in the row before this is the GCD. Note thatax n by = n n. So the last nonzero remainder has correspondinx and y values that are coefficients for a linear combination of a and b equal to it. In other words,xtand y values in that row are a certificate of correctness for the GCD. For example, findigcd(42042,1071) : x y r q 1 0 42042 0 0 1 1071 0 1 -39 273 39 -3 118 252 3 4 -157 21 1 - - 0 12 We stop here since the remainder is 0. Now we can read the vxlye, anr = gcd(42042,1071) from the next-to-last row. Sincegcd(a,b) = gcd(b,a) , we can save a few steps by swapping the two if the second value is greater, so the bigger value is always in the first row. Certificates of Correctness IfP(n) is a statement depending n,a ∈ Z , then some datD and knowledge K give a certificate of correctneP(a)f if some easy calculations wDthand aand K proveP(a) . Example:P(529) : "529 is a perfect square" Certificate of correct23 = 529 Explanation: this proves the statement with only simple operations. Example:P(1147) : "1147 is not prime" Certificate of correct37 ⋅ 31 = 1147 Explanation: this proves the statement with only simple operations. Example:P(1,379,421) :1 = gcd(379,421) Certificate of correct1 = 10 ⋅ 379 − 9 ⋅ 421 Explanation: given t1 > 0,1 ∣ 379 ∧ 1 ∣ 421, and 1 is an integer linear combination of 379 and 421, 1 is the GCD by GCD-CT. 4/10/13 How did we find the numbers used in the GCD-CT certificate of correctness above? Consider42042x + 1071y = gcd(42042,1071) = 21 . How do we finx andy ? Consider the GCD calculated with GCD-WR: 42042 = 39 ⋅ 1071 + 273 gcd(42042,1071) = gcd(1071,273) 1071 = 3 ⋅ 273 + 252 gcd(1071,273) = gcd(273,252) 273 = 1 ⋅ 252 + 21 gcd(273,252) = gcd(252,21) 252 = 12 ⋅ 21 + 0 gcd(252,21) = gcd(21,0) = 21 Write the last value as a linear combination of the previ21 = 273 − 1 ⋅ 252 . Rewrite term21 = 273 − 1 ⋅ (1071 − 3 ⋅ 273). Expand and simplify:1 = 4 ⋅ 273 − 1071 . Rewrite term:21 = 4cdot(42042 − 39 ⋅ 1071) − 1071 . Expand and simplify: ⋅ 42042 − 157 ⋅ 1071 . Clearly, = 4,y = −157 . Clearly, ⋅ 42042 − 157 ⋅ 1071 = 21 , and 7/10/13 Summary Consider∀x,P(x) ▯ Q(x) . This is not a simple implication due to the quantifier. However, it still acts like an implication. The hypothesis isP(x) . The conclusion isQ(x) . The converse is∀x,Q(x) ▯ P(x) . The contrapositive i∀x,¬Q(x) ▯ ¬P(x) . The negation is¬(∀x,P(x) ▯ Q(x)) , or in simplified f∃x,P ∧ ¬Q(x) . x < y < z is equivalent x < y ∧ y < z . So the negationx ≥ y ∨ y ≥ z . A statement of the for(P ∧ ¬Q) ▯ ¬R is generally proven using the contraposiR ▯e ( (P ▯ Q) , assumeR and P , prove Q ), or by contradiction (sup(P ∧ ¬Q) and R, then reach an impossible condition). n Prove via induction that = 1 − n for integern ≥ 1 : i=1 2 Base case: clearly,= 1 − 1. 2 2 k 1 Inductive hypothesis: k ≥ 1 . Assume ∑ = 1 − 2k. 1 i=1 ClearlyLHS k+1 = LHS +k k+1 2 1 By the inductive hypothesRHS k+1 = RHS + k 2k+1. So RHS = 1 − 1 + 1 . k+1 2k 2+1 So RHS k+1 = 1 − 2 k, andRHS k+1 = 1 − k+1. 2 k 2 k+1 1 1 Inductive conclusion: Clearly, = 1 − 2 , then = 1 − 2k+1. n i=1 i=1 Therefore,∑ = 1 − 1, by the POMI. i=1 2n 9/10/13 GCD-CT says that if a certificate of a GCD exists, the GCD exists. EEA says that if a GCD exists, a certificate of its correctness exists. So for any GCD, we can have a certificate verifying its correctness. EEA is the converse of GCD-CT. Coprimality Two integersa and bare coprime ifgcd(a,b) = 1 - if they have no common factors other than 1 and -1. For example, 4 and 9 are coprime. 11/10/13 Coprimeness and Divisibility (CAD) Proposition: for any integera,b,d , id ∣ ab and gcd(d,a) = 1 , thena ∣ b. Proof: Leta,b,d be arbitrary integers. Assume d ∣ ab and gcd(d,a) = 1 . We want to prove d ∣ b. By EEA,∃x,y ∈ Z,dx + ay = 1 . Clearly, this is equivaleb(dx + ay) = b . Clearly, this is equivalentd(bx) + (ab)y = b . Clearly,d ∣ d, andd ∣ ab. By DIC,d divides every integer linear combination ofd and ab. So d ∣ (d(bx) + (ab)y) . So d ∣ b. Proof by elimination To prove a statement of the form P ∨ Q , we assume ¬Q and from that prove Q . This is based on the observation thatP ∨ Q ≡ ¬(¬P) ∨ Q ≡ ¬P ▯ Q . Primality An integer p > 1 is prime if an only if its only positive divisors are p .nd Negative numbers, 0, and 1 cannot be prime. Lemma: given integers p,a , ip is prime and p ∤ a, thengcd(p,a) = 1 . In other words, a prime that does not divide a number is coprime to it. Proof: Assume p is prime and p ∤ a. Clearly, the divisors pfare −p,−1,1,p . Clearly, the divisors afinclude -1 and 1. Since p ∤ a,a ≠ p . So the only possible common divisors are -1 and 1. So gcd(p,a) = 1 . Primes and Divisibility (PAD) Commonly known as Euclid's Lemma. Corollary: given integersp,a,b , ip is prime and p ∣ ab, thenp ∣ a ∨ p ∣ b. Letp,a,b be arbitrary integers. Proof by elimination. Assume p is prime and p ∣ ab. Assume p ∤ a. By the previous lemma, since p is prime and p ∤ a,gcd(p,a) = 1 . By CAD, since p ∣ aband gcd(p,a) = 1 ,p ∣ b. GCD of One (GCD OO) Proposition: given integersa,b , if there are integx,y such that ax + by = 1 , thengcd(a,b) = 1 . Proof: Clearly,1 > 0,1 ∣ a,1 ∣ b . By GCD-CT, ax + by = 1 implies gcd(a,b) = 1 . By EEA, the proposition's converse is also true. So we can write the following: Proposition: given integers a,b, gcd(a,b) = 1 if and only if there are integerx,y such that ax + by = 1 . Division by the GCD (DB GCD) a b Proposition: given integers a,b, igcd(a,b) = d,d ≠ 0 , thengcd( ,d) d 1 Proof: By EEAa there bre integersx,y asuch tbat ax d by = d . Since d and d are integers,d x + d y = d . So a x + b y = 1 . d d By GCD-OO, gcd( ,d) d 1 . Linear Diophantine Equations (LDE) A linear equation in the style of Diophantus, a Greek mathemetician who invented a theory of the integers. They are equations having integer solutions only. 16/10/13 A linear Diophantine equation in two variables is any equation of the form ax + by = c , witha,b,c ∈ Z , and we seek x,y ∈ Z . In other words, we seek only integer solutions. 2x + 3y = 4 - solutions includex = 2,y = 0 and x = −1,y = 2 . 6x + 9y = 10 - no solutions These equations will have either infinitely many solutions, or no solutions. Linear Diophantine equation theorem, part 1 (LDET 1) Proposition: given integers a,b,c ∈ Z ,d = gcd(a,b) , the linear Diophantine equationax + by = c has solutions if and only id ∣ c. Proof: We want to show that ax + by = c having solutions in Z ▯ d ∣ c. First we will prove thaax + by = c having solutions in Z ▯ d ∣ c. Assume ax + by = c has solutions inZ . So ∃x,y ∈ Z,ax + by = c (thex and y here are no longer variables, and are specific integers). We know that d = gcd(a,b) . So d ∣ a and d ∣ b. By DIC, d ∣ (au + bv),u,v ∈ Z . So d ∣ (ax + by) , and sod ∣ c. Now we will prove the converse, that d ∣ c ▯ ax + by = c has solutions inZ . Assume d ∣ c. So ∃k ∈ Z,c = kd . By EEA, ∃x,y ∈ Z,d = ax + by . So kd = a(kx) + b(ky) = c . So kx and ky are integer solutions to the equation. So the equation must have solutions in Z . Since the implication and its converse are trueax + by = c having solutions in Z ▯ d ∣ c. The proof in the backwards direction shows us how to find at least one solution to the equation. Find one solution to the LDE 21x + 15y = 12 : Clearly,a = 21,b = 15,c = 12,d = gcd(21,15) = 3 . Since d ∣ c, there are solutions to the equation. Using EEA, we find that d = −2a + 3b . We know that c = kd,k ∈ Z . Specifically12 = 4 ⋅ 3 , sok = 4 . Clearly, k)d = −2ka + (3k)b = c . So 12 = (−2 ⋅ 4)a + (3 ⋅ 4)b = −8a + 12b . So x = −8,y = 12 is a solution to the LDE. Linear Diophantine equation theorem, part 2 (LDET 2) Proposition: given integersa,b,c ,ab ≠ 0 ,d = gcd(a,b) , if the LDax + by = c and x 0y 0 is one particular integer solution, then the complete integer solution is x = x +0 bk,y = y −0 a k,k ∈ Z . d d b a So ax + by = c ▯ x = x +0 d n,y = y −0 d . So the solutions to an LDE, if they exist, are integer multiples of ,− a at an offset of given solutionx ,y . gcd(a,b) gcd(a,b) 0 0 We will fix one particular solution x 0y . 0 LetS be {(x,y) ∈ Z ax + by = c} . LetT be { (x,y) x = x + b k,y = y − a k,k ∈ Z } . ∣ 0 d 0 d We want to prove S = T , so we will proveS ⊆ T and T ⊆ S . First we will provT ⊆ S . Let(x,y) be an arbitrary element ofT . So ∃k ∈ Z,x = x + b k,y = y − a k. 0 d 0 d We know that ax 0 bx = 0 is a given. b a Clearly,ax + by = a x + 0 d k + b y − 0 d k) . ab ba So ax + by = ax + 0 d k + by 0 d k = ax +0by = c0 . Since ax + by = c ,(x,y) ∈ S . Since (x,y) is arbitraryT ⊆ S . Now we will prove S ⊆ T . Let(x,y) be an arbitrary element ofS . So ∃x,y,∈ Z,ax + by = c . We know that ax 0 bx = 0 is a given. Clearly,(ax + by) − (ax + bx ) = c − c , soa(x − x ) + b(y − y ) = 0 Clearly,d ∣ a ∧ d ∣ , so 0 0 0 0 ∃k,l ∈ Z,a = kd,b = ld . So k = a ,l = b . d d We know that ab ≠ 0 is a given. ;wip: do we still need this given the assumption below? Assumeb ≠ 0 . ;wip: we make this assumption to simplify things, but should provide a full proof later Clearly, kd(x − x ) + ld(y − y ) = 0 = k(x − x ) + l(y − y ) . 0 0 0 0 So k(x − x )0= −l(y − y ) = 0(y − y) 0 . So l ∣ k(x − x 0 . a b By the DB-GCD theorem, gcd(k,l) = gcd ( d , d) = 1 . Since l ∣ k(x − x0) and gcd(k,l) = 1 ,l ∣ (x − x 0 , by the CAD theorem. So ∃n ∈ Z,x − x = l0 So x = x +0ln , andx = x +0 b n. d We need to use another technique here in order to ensure we can use the same value of n . Since k(x − x 0 + l(y − y ) 0 0 ,l(y − y 0 = −k(x − x ) = 0(x − x) 0 . Since x − x 0 ln ,l(y − y 0 = kln . Since we assumed b ≠ 0 ,y − y 0 kn . ;wip: this may not be a good assumption Clearlyl ≠ 0 sinceb ≠ 0 . So y = y − kn , andy = y + an . 0 0 d b a Since ∃n ∈ Z,x = x + 0 d n,y = y +0 d n,(x,y) ∈ T . So S ⊆ T . Since T ⊆ S ∧ S ⊆ T ,S = T 18/10/13 Find the complete integer solutions to14x − 10y = 26 : Clearly,gcd(14,10) = 2 , and2 ∣ 26, so there are infinite integer solutions, by LDET1. Using EEA, we determine that gcd(14,10) = 2 = 14 ⋅ −2 − 10 ⋅ −3 , withx = −2,y = −3 . 26 Clearly,14 ⋅ −2 − 10 ⋅ −3 = 2 can be multiplied by 2 = 13 to obtain14 ⋅ −26 − 10 ⋅ −39 = 26 . So x = −26,y = −39 . By LDET 2, x = −26 + −10 n = −26 − 5n,y = −39 − 14 = −39 − 7n,n ∈ Z . 2 2 In general, we can solve any LDE of the formax + by = c that has solutions simply by using EEA to finx and y for ax + by = gcd(a,b) , and multiplying both sides of the equation by c . gcd(a,b) This is possible sincgcd(a,b) ∣ c, assuming the LDE has solutions (by LDET1). For the above, find the unique positive solutiox > 0,y > 0 ) which minimizes x + y : We want to find x,y such that x > 0 ∧ y > 0 . Assume x > 0,y > 0 . 26 Clearlyx > 0 ▯ −26 − 5n > 0 ▯ n < − 5 . Clearlyy > 0 ▯ −39 − 7n > 0 ▯ n < − 39. 7 Sincen < − 25 ∧ n < − 79,n < min(− 25 ,− 79)⌋ , sn < −6 . Sincex and y increase asn decreases, the smallest value ox and y results from the largest value on. Forn = 6 ,x = −26 − 5 ⋅ −6 = 4 and y = −39 − 7 ⋅ −6 = 3 . By the way, iff means if and only if ▯ ). 21/10/13 Congruence Given a,b,m ∈ Z ,a ≡ b (mod m) -a is congruent to b modulo m - if and only m ∣ (a − b) . Ifm ∤ (a − b) , thena ≢ b (mod m) -a is not congruent tob modulo m . When proving things involving congruence, we often use the definition. Congruent iff Same Remainder (CISR) Proposition: givenm ∈ N ,∀a,b ∈ Z,a ≡ b (mod m) if and only afand b have the same remainder when divided by m . In other words,rem(a,m) = rem(b,m) ▯ a ≡ b (mod m) . ;wip: prove it - proof in course notes Congruence is an Equivalence Relation (CER) Given m ∈ N,∀a,b,c ∈ Z : a ≡ a (mod m) : reflexive property a ≡ b (mod m) ▯ b ≡ a (mod m) : symmetric property a ≡ b (mod m) ∧ b ≡ c (mod m) ▯ a ≡ c (mod m) : transitive property The first two are trivially proved. The last one is proved below: Assume a ≡ b (mod m) and b ≡ c (mod m) . So m ∣ a − b and m ∣ b − c . By DIC,m divides every integer linear combination oa − b and b − c. In particulam ∣ (a − b) + (b − c) , som ∣ a − c . So a ≡ c (mod m) . Properties of Congruence (PC) Given m ∈ N,a,a ,b,b ∈ Z′ , ia ≡ a (mod m) and b ≡ b (mod m) , then: ′ ′ a + b ≡ a + b (mod m) a − b ≡ a − b (mod m) ab ≡ a b (mod m) Proof: Proof of first point. Assume a ≡ a (mod m) and b ≡ b (mod m) . ′ ′ So m ∣ a − a and′m ∣ b − b ′ ′ ′ By DIC,m ∣ (a − a ) + (b − b ) , sm ∣ (a + b) − (a + b ) . So a + b ≡ a + b (mod m) . The second point is proved similarly. The third point is proved slightly differently. ′ b ≡ (mod m) ′ ′ Assume a ≡ a (mod m) and b ≡ b (mod m) . We want to prove m ∣ ab − a b′ ′. ′ ′ ′ ′ ′ ′ ′ ′ ′ Clearly,ab − a b = ab − ab + ab − ′ b = a(b − b )′+ b (′ − a ) . Since m ∣ a − a ′ and m ∣ b − b m , a(b − b ) + b (a − a ) ′ , by DIC. So m ∣ ab − a b′ ′, and ab ≡ a b (mod m) 2 2 ′ ′ Special case: iu ≡ v (mod m) , thenu ≡ v (mod m) . Here,a = u,a = u and b = v,b = v . We can apply this again: ifa ≡ c (mod m) , thena ≡ c (mod m) . Here,a = a ,a = a and b = c ,b ,c n n By induction, we can prove that a ≡ c (mod m) . Special case: ia 1 b (m1d m) ∧ … ∧ a ≡ b (mod m)2 2 , thena1+ … + a ≡ b nmod m1 + … + b n . Application: remainder when divided by 9 Clearly,10 ≡ 1 (mod 9) . Clearly,10 ≡ 1 (mod 9) . Consider k = 3141592 . What is the remainder when divided by 9? Clearly,k = 3 ⋅ 10 + 1 ⋅ 10 + 4 ⋅ 10 + 1 ⋅ 10 + 5 ⋅10 + 9 ⋅10 + 2 ⋅10 1 0 . Clearly,10 ≡ 1 (mod 9) and 3 ≡ 3 (mod 9),1 ≡ 1 (mod 9),4 ≡ 4 (mod 9),1 ≡ 1 (mod 9),5 ≡ 5 (mod 9),9 ≡ 9, (mod 9)2 ≡ 2 (mod 9) . So each term of the sum is congruent to the digit: 3 ⋅ 10 ≡ 3 (mod 9),2 ⋅10 ≡ 2 (mod 9) . Clearly,k ≡ 3 + 1 + 4 + 1 + 5 + 9 + 2 (mod 9) , sok ≡ 25 (mod 9) . Repeating, we get k ≡ 2 + 5 (mod 9) , sok ≡ 7 (mod 9) . Since 0 ≤ 7 ≤ 9 , 7 is the remainder when 3141592 is divided by 9. So to find the remainder of a number divided by 9, we can ;wip Congruences and Division (CD) Note that ac ≡ bc (mod m),c ≠ 0 does not imply a ≡ b (mod m) . However, if c is coprime to m (gcd(c,m) = 1 ), thena ≡ b (mod m) . In other words, given m ∈ N,a,b,c ∈ Z,c ≠ 0 , ac ≡ bc (mod m) and gcd(c,m) = 1 , thena ≡ b (mod m) . Proof: Assume ac ≡ bc (mod m) and gcd(c,m) = 1 . So m ∣ ac − bc and m ∣ c(a − b) . Since gcd(m,c) m ∣ a − b , by CAD. So a ≡ b (mod m) . 23/10/13 Linear Congruence A linear congruence is a mathematical form. It takes the general form of the following: Given a fixed a,c,m ∈ Z,m > 0,ax ≡ c (mod m) . Consider 4x ≡ 2 (mod 6) . Possible solutions are−1,2,5,8,11 . Note that the solutions differ by 3. Consider 4x ≡ 3 (mod 6) . There are no solutions. Solving x is a solution if and only iax ≡ x (mod m) , orm ∣ ax − c . 1 1 1 So x 1 is a solution if and only −m ∣ ax − 1 , or∃k ∈ Z,ax − c1= −mk . So x 1 is a solution if and only ∃k ∈ Z,ax + m1 = c . This is an LDE. So the linear congruence has solutions if and only if the related linear diophantine equation has solutions. ax ≡ c (mod m) is closely related toax + my = c . Ifx 0y is a particular solution tax + my = c , then the complete solution is 0 m a x = x 0 d n,y = y 0 d n,n ∈ Z,d = gcd(a,m) . Solve4x ≡ 2 (mod 6) : The corresponding LDE is4x + 6y = 2 . By inspection (though we could also use EEA), we find that one possible solx = −1,y = 1 . 6 By LDET2, x = −1 + 2 n,n ∈ Z . In both the linear congruence and the LxErepresents the same thing. 6 So the com
More Less
Unlock Document

Only pages 1,2,3,4 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit