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