Math 3H03 - Number Theory
(Winter 2020)

MATH 3H03 is an introduction to the area of number theory. Some of the topics covered in this course are divisibility, prime numbers, congruences, Euler's functions, the group of units, quadratic residues, and Fermat's Last Theorem. The main objectives of this course are

• to learn the basic terminology and results concerning elementary number theory
• to learn and improve your proof writing skills, and
• to collaborate with your some of your classmates on a project related to number theory.

The prerequisite for this course is credit in at least 12 units of Mathematics or Statistics Level II or above.

News Homework Project Handouts Grading Scheme Schedule Policies

Course Information

Instructor: Adam Van Tuyl

Office: Hamilton Hall 419
Office Hours: Wedensday and Thursday 11:30-12:30
Email: vantuyl@math.mcmaster.ca

Place and Time:

Class: Monday, Wednesday, Thursday 10:30-11:20 in Hamilton Hall 302

Textbook:

Elementary Number Theory by Gareth A. Jones and J. Mary Jones.

Copies can be found in the bookstore.

News (Last Updated: April 12, 2020)

Changes due to COVID-19. As you are well aware, as of March 13, 2020, there will no longer be in-class lectures or tests. Here is the official letter outlining the changes to the remaining part of the course: Changes to Math 3H03 In ADDITION to the revised marking schemes in letter above, I will add one more marking scheme: NEW SCHEME 30% Homework (best 7 out of 8) 20% Poster 50% Best of Midterm 1 and 2. I will then take the best of all schemes that apply to you. In fact, you have enough information to calculate a lower bound on your mark. Here's how to do it: Let H1,..,H7 be the number of marks you receive on Homework 1-7. For example, homework 1 was out of 10, so H1 is a number between 0 and 10. Then compute (30/7)*(H1/10+H2/10+H3/10+H4/10+H5/12+H6/10+H7/10). This gives your homework mark out of 30. I sent you your poster mark P out of 100. Turn it into a mark out of 20 by P/100*20. This is your poster mark out of 20. Take your mark T out of 100 for your midterm 1. Turn it into a mark out of 50 by computing T/100*50. This your midterm mark out of 50. Add the three numbers up, and this gives your current mark. This is the grade that you would get if you decide to do nothing else in the course. For some of you, you may be happy with this mark, so you don't need to do anything else for the course. For others, this allows you to put all the weight on the second midterm. The plan is to cover most of the remaining material of Chapters 6 and 7 in the textbook. Lectures will be recorded during regular class time via Echo 360, and then posted to Avenue-to-Learn. (So, all lectures should be available soon after regular class time). Midterm 2 will be moved to April 1 and will be done via Crowdmark. All classes after April 1 and the final will be cancelled. For more general questions regarding courses, an FAQ has been set up by Registrar's Office.

Below is a summary of what we did in class, plus any relevant news and/or information. You can also access the

• Class Lectures

Our TA (Lindsay White) has set up a dropbox folder with some useful information (including solutions to homework):

• Math 3H03 Dropbox Folder (includes homework solutions!)

Here is a break down of what happened in each class.

• Week 1
  • Lecture 1 (Jan. 6) In today's class I went over the course outline, and I described a number of results in elementary number theory we want to prove by the end of the course. This includes some simple cases of Fermat's Last Theorem and Lagrange's Sums of Four Squares Theorem.
  • Lecture 2 (Jan. 8) I introduced the Division Algorithm (Section 1.1), and we talked about the basic properties of division. Suggested Problems: Exercise 1.3.
  • Lecture 3 (Jan. 9) We discussed greatest common divisors, least common multiplies, Euclid's Algorithm, and Bezout's Identity (Sections (1.1-1.3). Suggested Problems: Exercise 1.5, 1.7, 1.13, 1.14.
• Week 2
  • Lecture 4 (Jan 13) We covered Section 1.4 by explaining how to solve all linear diophantine equations. Suggested Problems: Exercise 1.15, 1.16.
  • Lecture 5 (Jan 15) We wrapped up Chapter 1. I went back and proved the division algorithm from Section 1.1. I also spent some time discussing how to write proofs. Suggested Problems: Exercise 1.17, 1.25
  • Lecture 6 (Jan 16) The beginning of the class was spent on talking about the poster project. Everyone had a chance to talk with their groups. I also started Chapter 2 on primes. Suggested Problems: Exercise 2.2, 2.3.
• Week 3
  • Lecture 7 (Jan 20) We finished up the proof of the Fundamental Theorem of Arithmetic. We also started Section 2.2 on the distribution of primes. In particular, we did Euclid's theorem, and we talked about Dirichlet's Theorem, and proved some special cases. Suggested Problems: Exercise 2.6, 2.7
    As an interesting aside, here is a visualization of prime factorization
  • Lecture 8 (Jan 22) Today we looked at Section 2.2 on the distributions of primes. We talked about bounds on the n-th prime, the Prime Number Theorem, and primes in arithmetic sequences. Suggested Problems: Exercise 2.24.
  • Lecture 9 (Jan 23) We discussed Fermat and Mersenne primes, special types of prime numbers. Suggested Problems: Exercise 2.22, 2.23.
• Week 4
  • Lecture 10 (Jan 27) I went over Section 2.4 on primality testing. I proved a number of division "tricks" (e.g. division by 3), and I discussed Wilson's Theorem and seive methods. Suggested Problems: Exercise 2.11, 2.12, 2.14
  • Lecture 11 (Jan 29) We started Chapter 3 on modular arithmetic. I introduced the basic definition, and described a number of properties of congrueneces. Suggested Problems: Exercise 3.1
  • Lecture 12 (Jan 30) I finished Section 3.1 by first introducing a complete set of residues modulo n. I then explained how we can use congruences to sometimes show that an integer polynomial has no integer solutions. Suggested Problems: Exercise 3.2, 3.4, 3.20
• Week 5
  • Lecture 13 (Feb 3) We started our discussion of Section 3.2 by describing how to find all the solutions to a linear congruence equation. Suggested Problems: Exercise 3.5, 3.7.
  • Lecture 14 (Feb 5) Today I stated and proved the Chinese Remainder Theorem (Section 3.3). You should be able use the CRT to solve systems of linear congruences. Suggested Problems: Exercise 3.8, 3.9, 3.10, 3.11.
  • Lecture 15 (Feb 6) We looked at Section 3.5 at a generalization of the Chinese Remainder Theorem. In particular, I went over the proof of Theorem 3.12 in detail. (We will skip Section 3.4). Suggested Problems: Exercise 3.14, 3.15, 3.16, 3.18.
• Week 6
  • Lecture 16 (Feb 10) Today we went over Section 4.1. In particular, I proved Fermat's Little Theorem and Wilson's Theorem. Suggested Problems: Exercise Exercise 4.1, 4.2, 4.21.
  • Lecture 17 (Feb 12) Today was the first midterm. The midterms have been graded, and the solutions can be found in the Dropbox. When calculating your mark, I used the following procedure: I turned your mark out of 25 into a number $0 \leq x \leq 1$. Your mark is then $(\frac{x^c + x}{2}) \times 100$ where $c = 1/2$ or $c = 1/2.2$. The $c$ was $1/2$ if you had the full 50 minutes, and the $c$ was $1/2.2$ if you did not get the full 50 minutes for your midterm. In both cases, your mark will be higher than simply $x \times 100$.
  • Lecture 18 (Feb 13) Today we went over Section 4.2 on Carmichael numbers and pseudo-primes. Suggested Problems: Exercise 4.4, 4.5, 4.6, 4.12, 4.13.
• Week 7
  • Lecture 19 (Feb 24) Welcome back from the break! Today we went over Section 4.3. In particular, I described Hensel's Lemma which is being used in the background (see my lecture notes!). Suggested Problems: Exercise 4.15 and 4.16.
  • Lecture 20 (Feb 26) For the next three lectures, we will look at Chapter 11. Today, I covered the material of Sections 11.1-11.5 on primitive Pythagorean triples. Suggested Problems: Exercise 11.1, 11.2, 11.3, 11.4, 11.5.
  • Lecture 21 (Feb 27) Today I discussed Fermat's Last Theorem, and we went over the proof for the case n=4. See Section 11.7. Suggested Problems: Exercise 11.9 (I mentioned this result in class, but did not prove it.)
• Week 8
  • Lecture 22 (March 2) In today's class, I gave an overview of how Fermat's Last Theorem was proved. This lecture was more expository. It was based upon the following article: A Marvelous Proof, by F. Gouvea.
  • Lecture 23 (March 4) We started Chapter 5 today. We learned about units and inverses, and which elements in Z_n are inverses. I also described groups, and we were introduced to the group of units modulo n (see Section 5.1). Suggested Problems: Exercise 5.1.
  • Lecture 24 (March 5) Today we covered Section 5.2 on Euler's function. Two important results are Theorem 5.3 (Euler's Theorem) and Corollary 5.7 (a formula to compute Euler's function). Suggest Problems: Exercise 5.3, 5.4, 5.7, 5.13, 5.20, 5.21.
• Week 9
  • Lecture 25 (March 9) We wrapped up some of the material in Section 5.2, including Theorem 5.8. I also explained RSA cryptography (see page 95 of the text). Suggested Problems: Exercise 5.19.
  • Lecture 26 (March 11) Today was the poster session.
  • Lecture 27 (March 12) In class, I gave a worksheet on RSA cryptography. You can see the worksheet, and solutions here: RSA Worksheet.
• Week 10 (Note that I recorded all the remaining lectures on March 19)
  • (March 16) No class as we switch to online classes.
  • Lecture 28 (March 18) [Echo360 lecture available in Avenue-to-Learn] In this lecture, I introduced the theme of Chapter 6, which is to study the structure of the group U_n. I defined the order of an element of a group, and I explained what a cyclic group is. I also introduce primitive roots mod n, and described the primite root test. I covered Sections 6.1 and 6.2. Suggested Problems: Exercise 6.1, 6.2, 6.4, 6.5, 6.6.
  • Lecture 29 (March 19) [Echo360 lecture available in Avenue-to-Learn] In this lecture, I summarized the content of Sections 6.2-6.5. In particular, I sketched out the main steps of Theorem 6.11, which characterizes all the n such that U_n is cyclic. Suggested Problems: Exercise 6.8, 6.9, 6.10, 6.11, 6.14, 6.22.
  • Lecture 30 (March 19) [Echo360 lecture available in Avenue-to-Learn] In this lecture, I introduce the notion of quadratic residues. This material is based on Sections 7.1-7.3. I introduced the Legendre Symbol, and I proved Euler's Criterion to compute the Legendre Symbol. Suggested Problems: Exercise 7.1, 7.2, 7.3, 7.6, 7.7, 7.8.
  • Lecture 31 (March 19) [Echo360 lecture available in Avenue-to-Learn] In this lecture I finished up Section 7.3. We started with some consequences of the Legendre Symbol, including a proof that there is an infinite number of primes of the forms 4q+1 (see Corollary 7.8). I also proved Gauss's Lemma (see Theorem 7.9). Suggested Problems: Exercise 7.9, 7.10.
  • Lecture 32 (March 19) [Echo360 lecture available in Avenue-to-Learn] In this lecture, I introduced the Law of Quadratic Reciprocity. I followed the proof of Sey Y. Kim (a McMaster Alumni!) whose paper you can find here: An Elementary Proof othe Quadratic Reciprocity Law. In my Echo360 lecture, I did not work out all the details, but you can find all the details in the google album. Suggested Problems: Exercise 7.11, 7.12, 7.23, 7.25.
  • Lecture 33 (March 19) [Echo360 lecture available in Avenue-to-Learn] In this last lecture, I wrapped up Sections 7.5 and 7.6. I also gave a quick overview of Chapter 10 on Lagrange's Four Square Theorem. This is the last lecture of new material.
• Week 11
  • During this week, you should watch all the lectures up to Lecture 32, complete Homework 8, and start reviewing for midterm 2, which will be on April 1.

Return to TOP

Homework

There will be nine eight homework assignments (your lowest mark will be dropped). Assignments are posted below. Assignments will be submitted via Crowdmark. You will receive an email to your McMaster account that you will use to upload your assignment. All assignments due by 11:59PM on the due date.

• Assignment 0 (Due: Jan. 10)
• Assignment 1 (Due: Jan 17)
• Assignment 2 (Due: Jan 24)
• Assignment 3 (Due: Jan 31)
• Assignment 4 (Due: Feb 7)
• Midterm I Review Sheet (Feb. 12)
• Assignment 5 (Due: Feb 28)
• Assignment 6 (Due: March 6)
• Assignment 7 (Due: March 13)
• Assignment 8 (Due: March 27)
• Assignment 9 (Assignment 9 is cancelled)
• Midterm II Review Sheet (April 1)

For more information on writing proofs, the following notes may help:

• Guide to writing proofs
  A handout on writing proofs I wrote for algebra in 2010.
• Some remarks on writing mathematical proofs
  A nice short guide to writing mathematics by John M. Lee.

Return to TOP

Project: Creating a Poster

As part of this course, in a group of 2 to 4 students, you will create a poster on a topic in number. At the end of the semester, your group will also provide a short presentation about your poster.

Please use the following

• Poster Project Form to submit your poster topic and group (before Jan. 24).

Here is some of the key information:

• Project Information (summary of the assignment)
• Grading Rubric (how the posters will be graded)

Here are some links to help you find some topics:

• Biographies of Mathematicians Over 1000 mathematicians listed.
• Open Problem Garden A list of open problems in number theory (and other areas).
• Number theory algorithms A large number of algorithms for computations in number theory.
• Number Theory Articles A collection of accessible articles in number theory as selected by the MAA.

Here are some resources that will help you create and design a poster:

• Resources for Giving Talks and Poster Presentations A website written by A.J. Hildebrand that includes many useful links. It also includes a quick introduction to LaTeX.
• Poster Resources A website at Bates College; it contains some information about PowerPoint.
• Examples of Posters A webpage that contains a number of good examples of a mathematical posters.

Here are some links that will help you get started with LaTeX:

• Introduction to LaTeX If you want to install LaTeX on your own computer, this is probably the place to start.
• Overleaf If you don't want to install LaTeX on your own computer, you can use a cloudversion. You can get an account for free.
• LaTeX in 30 minutes Overleaf's half-hour tutorial to LaTeX.
• Posters in LaTeX Overleaf's introduction to posters in LaTeX.

Here is a nice video that gives you tips on giving a good presentation:

• Poster Presentation Tips

Return to TOP

Handouts

All class handouts are available as PDF files.

Course Information
Course handout from first day of class

Project Information
Handout describing the project

Midterm 1 Review Sheet
Handout describing first midterm.

Midterm 2 Review Sheet
Handout describing second midterm.

Return to TOP

Grading Scheme

The grading scheme is now described in the letter Math 3H03 Course Changes

I will calculate your mark using two different weightings. Your final mark will be the higher of the two weights.

Weighting 1
20% = 9 Assignments (best 8 used)
10% = Project
30% = Midterms (2 x 15%)
40% = Final Exam

Weighting 2
20% = 9 Assignments (best 8 used)
10% = Project
15% = Maximum of Midterm 1 and 2
55% = Final Exam

Return to TOP

Important Dates

Jan. 6, 2020
Second semester classes begin

Feb. 12, 2020
Midterm 1

Feb. 17-21, 2020
Winter break (no classes)

Mar. 4, 2020
Posters dues for printing

Mar. 11, 2020
Poster Presentations

Mar. 13, 2020
Last day for cancelling courses without failure by default

Mar. 18, 2020April 1, 2020
Midterm 2

Apr. 7, 2020
Second semester classes end

Apr. 13-28, 2020
Final Exams

Return to TOP

Class Polices

1. Policy on Academic Ethics. You are expected to exhibit honesty and use ethical behaviour in all aspects of the learning process. Academic credentials you earn are rooted in principles of honesty and academic integrity.

Academic dishonesty is to knowingly act or fail to act in a way that results or could result in unearned academic credit or advantage. This behaviour can result in serious consequences, e.g. the grade of zero on an assignment, loss of credit with a notation on the transcript (notation reads: Grade of F assigned for academic dishonesty), and/or suspension or expulsion from the university.

It is your responsibility to understand what constitutes academic dishonesty. For information on the various types of academic dishonesty please refer to the Academic Integrity Policy, located at: http://www.mcmaster.ca/academicintegrity/

The following illustrates only three forms of academic dishonesty:

• plagiarism, e.g. the submission of work that is not one's own or for which other credit has been obtained.
• improper collaboration in group work,
• copying or using unauthorized aids in tests and examinations.

2. Academic Accommodation of Students with Disabilities. Students with disabilities who require academic accommodation must contact Student Accessibility Services (SAS) to make arrangements with a Program Coordinator. Student Accessibility Services can be contacted by phone 905-525-9140 ext. 28652 or e-mail sas@mcmaster.ca. For further information, consult McMaster University's Academic Accommodation of Students with Disabilities policy.

3. Requests for Relief for Missed Academic Term Work. If you have missed work, it is your responsibility to take action. If you are absent from the university for medical and non-medical (personal) situations, lasting fewer than 3 days, you may report your absence, once per term, without documentation, using the McMaster Student Absence Form (MSAF). See Requests for Relief for Missed Academic Term Work

Absences for a longer duration or for other reasons must be reported to your Faculty/Program office, with documentation, and relief from term work may not necessarily be granted. In Math 3GR3, the percentages of the missed work will be transferred to the final examination. Please note that the MSAF may not be used for term work worth 25% or more, nor can it be used for the final examination.

4. Academic Accommodation for Religious, Indigenous or Spiritual Observances (RISO). Students requiring academic accommodation based on religious, indigenous or spiritual observances should follow the procedures set out in the RISO policy. Students requiring a RISO accommodation should submit their request to their Faculty Office normally within 10 working days of the beginning of term in which they anticipate a need for accommodation or to the Registrar's Office prior to their examinations. Students should also contact their instructors as soon as possible to make alternative arrangements for classes, assignments, and tests.

5. Important Message. The instructor and university reserve the right to modify elements of the course during the term. The University reserves the right to change the dates and deadlines for any or all courses in extreme circumstances (e.g., severe weather, labour disruptions, etc.). Changes will be communicated through regular McMaster communication channels, such as McMaster Daily News, A2L and/or McMaster email. If either type of modification becomes necessary, reasonable notice and communication with the students will be given with explanation and the opportunity to comment on changes. It is the responsibility of the student to check their McMaster email and course websites weekly during the term and to note any changes.

6. On-line Statement for Courses Requiring Online Access or Work. In this course we will be using Crowdmark. Students should be aware that, when they access the electronic components of this course, private information such as first and last names, user names for the McMaster e-mail accounts, and program affiliation may become apparent to all other students in the same course. The available information is dependent on the technology used. Continuation in this course will be deemed consent to this disclosure. If you have any questions or concerns about such disclosure please discuss this with the course instructor.

Return to TOP