MATH 13 -- PREVIOUS WEEKS

WEEK 7          
F: Outline of a rigorous proof by induction that the last remainder r_k coming from the Euclid's algorithm is a common divisor of a,b and that it is expressible in the form ax+by for suitable integers x,y. The criterion on the existence of a solution of a Diophantine equation of the form ax+by=c, and the use of Euclid's algorithm to find one solution. Theorem: if gcd(q,a)=1 and q|ab then q|b. Recommended practice problems.  
W: Fast proof of the fact that if a,b are congruent mod n and c,d are congruent mod n then ac,bd are congruent mod n. Greatest common divisor. Euclid's algorithm. Calculating the greatest common divisor g.c.d.(a,b). Finding coefficients x,y such that g.c.d.(a,b)=ax+by. Read Section 3.2 from the book. Recommended practice problems.      
M: Holiday 
 
WEEK 6   
F: Completion of the calculation from Wed. Proofs of Thm 2 and Thm 3. 
W: Thm 2: a is congruent to b module n iff n divides (a-b); Thm 3: Basic formulas of modular arithmetic. Examples how to recognize whether two numbers are congruent mod n. Using Thm 3 to calculate remainders of large numbers: showing that 6284×28531+30255 is divisible by 29. Recommended practice problems.      
M: The division algorithm: Proof. Congruence modulo n.      
 
WEEK 5     
F: An example of the ``smallest counterexample argument": another proof of the fact that every integer larger than 1 is divisible by a prime. The division algorithm. We almost finished the proof of the ``existence" part. Read Section 3.1 from the book. Recommended practice problems. 
W: Midterm 
M: Review for midterm  
 
WEEK 4       
F: Completion of the example on strong induction from Wednesday. Comparison of this argument with the argument from the discussion that every integer larger than 1 is a prime or a product of primes. The "smallest counterexample" argument and comparison of this argument with strong induction. Running the proof that every integer larger than 1 is divisible by a prime using the ``smallest couterexample" method. Well-ordering of nonnegative integers: Every nonempty subset of nonnegative integers has a smallest element. We discussed this and gave a heuristic argument, but no rigorous proof.  Recommended practice problems. 
W: More examples on mathematical induction: a-b divides an-bn, 2n>n3 whenever n>9. Strong induction. Example on strong induction: every integer larger than 1 is divisible by a prime. Read section 5.4 from the book. Recommended practice problems.    
M: Examples on mathematical inducion: 1+2+...+n = n(n+1)/2; 12+22+...+n2 = n(n+1)(2n+1)/6; 13n-6n is divisible by 7. Read Section 5.2 from the book. Recommended practice problems     

WEEK 3      
F: Discussion of the proof on infinitely many primes -- completion. Mathematical induction: The method. 
W:  Proposition: There are infinitely many primes. We practiced how to write this and statements about primes
and divisibility using quantifiers. We then started proving this proposition by contradiction, assuming there are only finite many primes. We let q be the product of all of them plus 1, and showed q must be a composite number. We will continue on Friday.   Read section 2.3 from the book to the end.  Recommended practice problems 

WEEK 2 
F:  Quantifiers: general strategy to prove/disprove quantified statements ``for all x,
P(x)" and ``there exists x such that P(x)" , hidden quantifiers, negation of quantifiers, double quantifiers.        
 
WEEK 1        
F: Methods of proof: Direct proof, Indirect proof -- proving the contraposition, proof by contradiction, and proof by cases. Examples (1) 7x+9 is even iff x is odd (2) sum of two consecutive integers is odd, (3) product of two consecutive integers is even, and (4) x is odd iff x2-5 is divisible by 4. Read Section 2.2 from the book to the end. Recommended practice problems        
Th: Contraposition and converse. Examples. Terms "if-then" and "if and only if", briefly "iff". Negating implication and equivalence. Examples. Tautology and contradiction. Recommended practice problems      
W: Detailed discussion of implication with examples (i) if you come to class early then you find a free chair (b) if x>1 then x^3+1>1. Equivalence/biconditional. De Morgan laws.  Read Section 2.2 from the book, pages 20-22. Recommended practice problems      
Tu: Propositions/Sentences. Logical connectives. Truth tables and explanations for AND, OR, NOT and IMPLICATION/Conditional. Examples of statements formulated in human language and translated into rigorous mathematical language: (a) ? (b) Both x,y are smaller than 3 (c) x is smaller than 3 but larger than 2 (d) at least one of x,y is smaller than 3 (e) x is not between 2 and 3 (f) x,y are not both smaller than 3 (g) neither of x,y is smaller than 3.  Read Section 2.1 from the book.    
M: Course overview. Definitions of even, odd number and prime. Easy arguments concerning integers: sum of two even/odd integers is even. Sum of two integers may not be even; the expression n^2+n+41 may not be prime for odd n; there are integers m,n such that 7m+5n=4 but there are no integers x,y such that 6x+8y=15.  

HOME      MATH 13