## 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: 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 10% Un-exams (4 x) 5%+10%+10%+15% Forum exercises Fall 15%+Winter 15% Class participation (incl attendance) Fall 10%+Winter 10%

## Handouts

(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

## Schedule

 Date Topic Notes 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

## Announcements

(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.

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 range demonstrates a mastery of all concepts in the course by answering assignment questions B range demonstrates a mastery of most concepts, but fails to complete all assignments at a sufficiently high level of mastery C range is 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.