Debbie Leung
Email: wcleung(at)uwaterloo(dot)ca
Sean Carrell
Email: srcarrell(at)uwaterloo(dot)ca
MWF 8:30-9:20am, MC 4021
Starting Jan 4: Mondays 4:30-5:20pm, MC 4059
Mondays 9:30-11:00am (to be confirmed), MC 4036
Special arrangement for reading week and final exam
Mondays and Tuesdays MC 4066: M 12:30-2:30, T 9:30-1:30, 3:30-5:30. Exact schedule posted on its door
Sean Carrell's specific hours: Tuesday 9:30-11:30am
Drop off BEFORE 8:30am Weds in Box #5 (opposite to MC 4067) slots #4 (A-L) and #5 (M-Z). Late or misplaced HW will not be graded.
Additional requirements that ensure properly marking:
(1) Circle your last name. Include full name, UID, instructor's last name, course name Ma135, section number 001. Consider using the templates: File 1 and File 2.
(2) Present the questions and answers in order, staple (do not use clips) the pages together, securing particularly the first and the last pages.
Returned in class or in the tutorial. Else, pick up during instructor or TA office hours.
Misgrading or questions concerning the HW: report to Sean Carrell in his tutorial centre hours or come by instructor office hour.
Posted Mar 28, 5:20pm
On the uniqueness of factorization of f in C[x] (covered in Mar 29 lecture). Will see any f of degree n has a factorizationf(x) = a (x-c1) (x-c2) ... (x-cn) for some a, c1, ..., cn in C.
To show uniqueness of a, c1, c2, etc (i.e., 2 factorizations of the type above will have the same a, c1, c2, etc): note that a is the leading coefficent, and cannot differ in the two different factorizations. Likewise, if (x-c) occurs in the first factorization and not the second, then, from the first factorization, we see f(c) = 0, and from the second, we see f(c) nonzero, a contradiction. Finally, if (x-c) occurs n1 times in the first factorization and n2 times in the second factorization, and n1 < n2, then, consider f(x) divided by (x-c)^n1. This quotient q(x) is unique by the division algorithm. But x-c only appears in the quotient coming from the second factorization, once again, q(c) nonzero and q(c) = 0 which is a contradiction.
Posted Mar 19, 10:20am
The proof of the Fundamental Theorem of algebra is a bit abstract, and Section 8.8 in the textbook may not be very easy to read. Here are the lecture notes p1 and p2 for the proof. It also helps to see an example. We write z-to-the-power-n as z^n. Consider, say, f(z) = 8 z^8 + 3i z^5 + (16+40i) z + 20. (a0 = 20). We are considering g(z) = z^8 + (3i/8) z^5 + (2+5i)*z + 2.5. First, see the loop for r = 1 (when ploting g(r cis "theta")). For small r (r=0.1 is small enough here), see how the loop is circling around g(z) = 2.5 + 0 i. In this example, if we shrink the loop from r=1 to r=0.1, the original has already escaped. It happened approx when r = 0.465, theta = 0.62 pi. See the loop when it escapes. We don't need very large r here to enclose the origin, but if you're curious, this can also be visualize.
Posted Mar 10, 1:24pm
I've prepared some notes on RSA encryption and decryption and signature, since parts of the textbook are not exactly clear. In particualr, there is a quick guideline on which key is to be used and an explanation for the textbook concerning signature.
Posted Mar 7, 10:28pm
A New York Times article that happens to discuss tomorrow's lecture
Posted Mar 1, 3:38pm
Various things promised in the lecture: (1) The inductive proof that n-choose-r is an integer for all n>=0 and 0<=r<=n is actually in Sec 4.3 of the textbook. (2) Click here for an interesting PI public lecture concerning probabilities.
Posted Feb 8, 1:48am
There are changes to the midterm return procedure. In order to ensure grading consistency over all 5 sections, the course coordinator required that grading for all 5 sections be centralized. Therefore, I cannot expediate the grading and return the midterm on Wed. It is likely to be returned in class 9:10am on Friday. Questions/grading issues should be brought to my office hour Monday Feb 22nd.
Posted Feb 3, 9:29pm
Some of you ask what questions in the textbook are good practice questions. First note that answer keys are provided for odd number questions in the back of the book. For Chapter 2: p50-51 have many routine questions. Sample 1-2 questions from each group can be useful. Q67-68, Q73-75, Q81, Q94, Q99-102 are also useful. For Chapter 3: you can sample from Q1-11, Q22-26 (don't bother finding the quotient sets), Q27-48. Q60 is very nice (helps to use CRT, but you can also go without).
Posted Feb 3, 12:13pm
Concerning midterm:
(1) Time: Feb 8, Monday 7-9pm. Show up 10 mins before.
(2) Place: Last names A-J MC 2034, K-Q 2035, R-Z 2038.
(3) Bring: Watcard, pink-tied calculator.
(4) Study: Sec 2.1-3.5.
(5) Extra office hour: Feb 7, Sunday, 1-2pm, MC 4036.
(6) ******* Pickup Feb 10th, Wed, 9:15am in MC 4021 (classroom) *******
We will call names by alphabetical order and we will not return to names already called. Please be on time. At 10 sec per name, we will finish in 13 mins, before 9:28am.(7) Issues on marking: handled on Feb 10th in MC 4036 (my office) between 9:30-10:30am and 2:00-2:30pm.
(8) The lecture on Feb 12th will be given by instructor Franklin. She will NOT handle your midterms.
(9) Any further issue related to the midterm will be handled starting Feb 22nd.
Posted Feb 3, 11:53am
Answer to an old puzzler, on the number of zeros to the right of 100! can be found here
Posted Jan 27, 9:30am
A correction to the notes handed out today. In item (3), the definition of reflexive, symmetric, and transitive should have \forall ... \in S instead of \forall ... \in R. The corrected notesis here.
Posted Jan 24, 5:30pm
If you want to learn more about number theory, here're some book names.
Posted Jan 18, 1:42pm
Problems with Assignment 1:
A few made the wrong inference [If c|(a+b) then c|a and c|b] (fails on say, a=b=1, c=2). This is the converse of the correct inference [particular case of Prop 2.11 (ii)] that if c|a and c|b, then, c|a+b. Again, even if statement 1 implies statement 2, statement 2 need not implies statement 1.
Some made the wrong inference [If c|2a then c|a] (fails on, say, c=2, a=1). Again, it is the converse [If c|a then c|2a] that is true (Prop 2.11 (i)).
Posted Jan 17, 4:22pm
Two puzzlers given in class and their solutions
Posted Jan 14, 9:47pm
Assignment 2 as posted in UWACE, due Jan 20 8:30am
Posted Jan 14, 9:44pm
Solution to assignment 1 as posted in UWACE
Posted Jan 10, 5:12pm
Slightly rewritten proof for Prop.2.29 which is a reading assignment for week 2.
Posted Jan 10, 5:11pm
Progress section added to this homepage.
Posted Jan 3, 9:52pm
Supplementary reading: notes on statements and notes on quantifiers.
Posted Jan 3, 9:47pm
Assignment 1 as posted in UWACE, due Jan 13 8:30am
Posted Jan 3, 1:04am
Crucial info here (called course syllabus in UWACE)
Week 12
Will see UFT for C[x], R[x], and the rational root theorem.Week 11
Covered Section 9.1 -- Fields, polynomials with coefficients from a field, div alg, remainder theorem, factor theorem, reducible and irreducible polynomials.
Weeks 9-10
Covered entire Chapter 8.
Week 8
Covered entire Chapter 7.
Week 7
Covered Sec 4.2 on POSI' and recursive sequences that may involve multiple base cases in an inductive proof. Covered Sec 4.3 on n!, n-choose-r, properties of the binomial coefficients and the binomial theorem, followed by many examples. Covered Sec 5.1-5.2 on the rational numbers and real numbers.
Week 6
Covered Sec 3.6-3.7, generalized Chinese Remainder Theorem and the generalized version of Prop 3.64, and various examples. The Euler-phi function was introduced, the Euler-Fermat theorem proven, and the Euler-phi derived for any natural number. Covered Sec 4.1 on POMI and POSI.
Week 5
Covered linear congruences in 1 variable, systems of linear congruences in multiple variables, nonlinear congruences, all in a single modulus. Some advanced issues on nonlinear congruences distributed as handouts.
Covered Chinese Remainder Theorem and Prop 3.64.
Week 4
Finished Prop 3.13 (cancellation rule for multiplicative factors)
Covered Sec 3.4 on (a) partitions of a set, (b) a general relation on a set, (c) equivalence relations (special relations that are reflexive, symmetric, and transitive), (d) see that a partition induces an equivalence relation and vice versa. Handout was given in class.
Covered Z-mod-m and arithmetic on it.
For m prime, we covered "3 good things" that happen, and used them to prove Fermat's little Theorem (+Cor 3.43).
Week 3
Covered in classes: Section 2.5, reorganized as in the handout. Started Section 3.1. including: (1) Def of congruences, Prop. 3.11 (3 basic properties) and Prop. 3.14 (alternative characterization in terms of the remainder in DA). (2) Arithmetic: Prop 3.12 (how to +,-,x).
Need to finish off (2) Arithmetic: Prop 3.13 (how to "divide").
Exercise and/or reading assignments: proofs of Props. 2.57, 2.58. 2.59, 3.11(ii), 3.12.
Week 2
Covered in classes: iff statements, Props 2.27, 2.28, 2.29, entire LDE Theorem 2.31 with proof, a detail comparison of solutions of similar LDE's, and geometric intepretations. Integers in different bases, converting from one basis to another. Uniqueness of representation only stated verbally in class.
Reading assignments: proof of Prop 2.27 in the textbook, proof of Prop 2.29 in this webpage, proof of uniquness of representation of integers in any basis, addition and multiplication in other bases in the textbook. Students are highly encouraged to try more LDE examples, especially those in the past midterms (obtainable from the MathSoc exam bank) since they come with solutions.
Puzzlers and solutions were just posted.
Week 1
Covered definition of divisibility, Prop 2.11 (i)-(iv), Prop 2.21, Div Alg (DA) (2.12), Euclidean Alg (EA) (2.22), gcd char thm (2.24), and EEA (2.25).
Reading assignments: notes on statements and quantifiers, proof of 2.11(iii) from handout in class, proof of uniqueness of q,r in DA in textbook, and detail proof of correctness of EEA in textbook. Also, student should read examples in the textbook.
Various exercise questions were also stated in class.
Help Email a question, will try to answer same day if received before 10pm.
