Math 5020

Fundamentals of Mathematics for Teachers

Description: Number theory and combinatorics are branches of mathematics in which challenging problems can be explored that require a background with which most students are familiar. This course deals with topics in these two fundamental mathematical fields, including modular arithmetic, linear and quadratic diophantine equations, continued fractions, permutations and combinations, distributions and partitions, recurrence relations and generating functions. It is one of two required courses for the Mathematics for Teachers program. An emphasis in this course is placed on writing and explaining mathematics clearly.

Prerequisite: Permission of the instructor is required for students who are not in the Graduate Programme in Mathematics and Statistics.

Professor: Mike Zabrocki
Office: TEL 2028
Hours: Thursday 4-5:30pm
phone: 416-736-2100 x33980
e-mail: zabrocki at mathstat dot and the usual ending
Class meets Thursday 6-9pm in Ross S537
Text : Number Theory by George Andrews

Grades for the course will be based on the following criteria:

Class presentation
Un-exams (4 x)
Forum exercises Fall 15%+Winter 15%
Class participation (incl attendance) Fall 10%+Winter 10%


(Oct 4, 2011) list of topics for presentations
(Oct 4, 2011) a few words about telescoping sums
(Oct 4, 2011) The course Moodle and Forum
(Oct 22, 2011) Video from class Oct 20, 2011
(Nov 3, 2011) Widget and doodle matching exercise
(Nov 17, 2011) Widgets and doodles without matching - did in class Nov 10
(Nov 17, 2011) Coefficients in generating function exercise - did half in class Nov 17
(Nov 17, 2011) First unexam due Nov 29 in class
(Dec 2, 2011) a table of generating functions where we provide the proof
(Dec 2, 2011) an exercise about building a sequence from the number of objects in a set that depends on n.
(Jan 12, 2012) some exercises on number theory and combinatorics.
(Jan 19, 2012) find the generating function from the recursion..
(Jan 19, 2012) exercises to prove stuff using generating functions.
(Feb 7, 2012) applying generating functions to combinatorics problems.
(March 1, 2012) taking coefficients in generating functions.
(March 1, 2012) some more word problems in number theory.
(March 1, 2012) matching partitions and generating functions.
(March 1, 2011) Second unexam Was due Feb 23


Sept 22
Induction, Telescoping sums, Theorem 2-1 and 2-2 (all together)
HW do some induction problems, telescoping sums too
Sept 29
Present Theorems, cover the rest of section 2
HW Find all solutions to $173 x - 255 y = 39$
Oct 6
Addition and multiplication principle, Wilson's Theorem, mod n
First forum assignment - emailed to you Oct 9
Oct 20
distributions, Velisa presented, generating functions

Oct 27
computers, card shuffling, $\phi(n)$, Frank showed solving congruence equations

Nov 3
more $\phi(n)$, Darshana showed CRT, widgets and doodles exercise
Widget and doodle matching exercise
Nov 10
$\sum_{d|n} \mu(d) = 1$ if $n=1$ or $0$ otherwise, $\sum_{d|n} a_d = b_n$ iff $\sum_{d|n} \mu(n/d) b_d = a_n$
Real widget and doodle exercise
Nov 17
the multiplication/addition principle of generating functions, multiplicative functions
unexam #1, coeff gf exercise
Nov 22
solutions to polynomial equations, Jeff presenting primitive roots

Nov 24
RSA and table of generating functions

Nov 29
Knapsack and more generating functions
unexam #1 due
Dec 1
g.f.s, first step in Chebychev's theorem, OLEIS exercise

Jan 5
More on Chebychev's theorem, Grace presenting Ch 9, Diffie-Hellman

Jan 12
number theory and counting problems, Chebychev's theorem lite

Jan 19
number theory/combinatorics problems, generating functions from recursions

Jan 26
number theory/combinatorics problems, generating functions and identities

Feb 2
number theory/combinatorics problems and generating functions, Grace presented pseudo-primality testing

Feb 9
quadratic reciprocity, combinatorics and generating functions, Darshana presenting factorization algorithms

Feb 16
generating functions and Jacobi symbol problems

Feb 16
generating functions and Jacobi symbol problems, Sandra presented sum of 4 square, Velisa presented digital signatures

Mar 1
coefficient in gf. exercises and Jacobi symbol problems and introduction to partitions

Mar 8

Mar 15

Mar 22

Mar 29


(September 22, 2011) I asked you to do 3 problems by induction as practice for homework. The ones that are sums you should also do using telescoping sums. I wrote a few notes on telescoping sums for my proofs class so I posted it here too.

(September 29, 2011) I asked you to use the theorems that we covered to find all solutions to the equation $ 173 x - 255 y = 39~. $

(October 4, 2011) I finally got the web page up and edited. I have posted the topic list and a few people made their preferences known at the last class (Velisa/Sec 3-2/Oct 24, Darshana/Sec 5-3/Nov ?, Velisa/Digital Signatures/Feb ?, Jeff/partitions in a rectangle/March ?). I want you all to do a presentation on one topic from the book and one that is not in the book. These will be two types of presentations, one that is quite structured and one that is less so. When you pick your topic, keep in mind that the presentations are roughly 20 minutes or less (more and you need to convince me why you need more time). The list I have is no exclusive, there are other possibilities and I have at the bottom of the page 'Suggest a topic.'

(October 4, 2011) We need to schedule a time to make up some missing classes. I've got the department to set up a class "Moodle" which has a discussion board (a "class forum"). I am hoping this will be helpful to schedule make-up classes. I will also soon be giving you assignments where you post your solutions on the forum. If you have any trouble logging in let me know and I will put you in touch with the people who set up the accounts.

(October 9, 2011) Starting this year the faculty of graduate studies has new policies about grading. They have implemented a point scale of 90-100 = A+, 85-89 = A, etc.. This is BRAND new, before this year there wasn't a percentage grading scale. This is a graduate course, you should be aware that grades are not important except as a measure of whether you are succeeding or not succeeding in a course. A/B = succeeding, C or lower = not succeeding (to me, assigning a much finer grade than that is a rather pointless exercise). If you are getting in the A range you are doing very well. If you are getting in the B range you are doing good but you can improve. If you are getting a C you are NOT doing OK and you will be removed from the program if you get more than one C in your courses. If you are getting lower than a C then there is a serious problem and you should not be in the program (it is regulation that you will be removed). At one point I wrote about the grading scheme for graduate programs on the M.A. for teachers blog. I will follow that scheme and not the numerical equivalents.

There are 7 people in this class and I don't have any worries that things take a dramatic swing in this class. I find it unlikely that we will have any C's or lower in this course. That being said, I need to clarify what is expected of you to get an A- or higher in this course:
A rangedemonstrates a mastery of all concepts in the course by answering assignment questions
B rangedemonstrates a mastery of most concepts, but fails to complete all assignments at a sufficiently high level of mastery
C rangeis not completing several assignments and fails to demonstrate mastery of the material
I will scale all numerical grades that I give you on assignments at the end of the course so that grades fall into these 3 categories (regardless of some percentage levels). The + or - will indicate whether you have succeeded better or worse within this range.

(October 9, 2011) This was the message sent by email:
Instructions for this assignment:
1) post your question as well as your answer. A reader should be able to start at the beginning of the solution, know what question you are writing about and at the end know what the answer is and why it is true and have no doubt about if you are correct or not.
2) In each of these questions I am looking for a numerical answer or a formula and an explanation of why your answer is correct. The number/formula/final answer is much less important than your explanation.
3) make any assumptions about definitions clear. E.g. if it is not clear if you should include the empty set as a possibility, explain which one you choose ("I will assume the empty set is/is not the smallest case because ...")
4) Explain yourself as completely as possible, but try to make your solution as short and compact as possible. There are a minimum number of details that you need to put in, if your solution is too long-winded no one will want to read it (and I will have to!). Each sentence you write ask yourself the question "why?" and make sure that what you write answers that question.
5) Use clear and complete sentences. Avoid abbreviations and symbols to represent your explanations. If you must use symbols or diagrams, explain them clearly and completely.
6) Post your solutions on the class Moodle. I will read them and comment on them line by line. If there is any part of your explanation that I find unclear I will ask you to correct your solution. When you do correct your post, DO NOT edit the old post, instead create a new post, copy and paste your original text and edit the new copy.
7) Keep editing until I signal "ok!" and you have hit what I am looking for. An excellent solution is short, clear, to the point, and includes all details necessary that it is impossible that can argue if your explanation is correct or not. Some questions are complex and it is difficult to give an "excellent" solution, but I will insist on what you write being correct, clear and complete.
FYI, I find that sometimes people find this sort of assignment adversarial. It is not intended to be that. I am your adversary only in the sense that I am looking for any part of your explanation which might be unclear or incorrect. I am also here to help you get through it.

(November 4, 2011) Please finish your forum posting this week. Next week you get another one.

(November 4, 2011) Last night we had half the class so I thought I would throw up a few notes about what we did and why. The what we covered in class is a lot less important than why. We were doing complex arguments with the addition and multiplication principles and we ended with an exercise about abstract uses of these principles. I started with a few arguments that I didn't get to the week before.
If $n>0$ and $a$ is an integer such that $gcd(a,n) = 1$, then $a^{\phi(n)} \equiv 1~(mod~n)$ (proof in the book).
If $k$ is the smallest positive integer such that $a^k \equiv 1~(mod~n)$, then $k | \phi(n)$ (a fact we observed with data about card shuffling). This may not be in the book, in fact it is a stronger statement than problem 18 in section 5-2 where they ask to show that $k \leq \phi(n)$.
Darshana showed the Chinese Remainder Theorem, but then we did some examples and found that for straight up calculations the CRT is probably the most difficult way to find the answer.
I used the Chinese Remainder Theorem to show that \[ \phi(n m ) = \phi(n) \phi(m) \] if $gcd(n,m) = 1$. This was a very short time after I said that I don't like the CRT to use to do actual calculations (hey, but it seems to be useful).
Then we figured out why $\sum_{d|n} \phi(d) = n$. This is in the book, but it is hard to follow. We just did it on the example of $n=30$ which roughly shows how the book shows this fact in general.
Then it was nearly time to leave but I said "before you go..." and handed out a worksheet. We stayed more than a half hour to finish it.

(November 4, 2011) For the three of you that weren't there last night, we did the worksheet and we talked it through (I was there to confirm or deny answers). Give it a shot and ask me or your classmates if you have questions.