MATH 311: Elementary Number Theory

Final Exam: Solutions

Final Grades are on Moodle.

__ Midterm Exam: Solutions__

Study Materials: Midterm Review Sheet, The Practice Exam and Solutions.

**Lecturer:** Thomas A. Hulse (you can call me "Tom")

**Location:** Monday 11:30, Tuesday 1:30, Thursday 12:30 in Jeffery 225

**Office:** Jeffery Hall 512 ph.: x3-6299

**Office Hours**: Mondays 5-6 and Wednesdays from 4-5 in Jeffery 202, or by appointment.

**e-mail:** hulse@mast.queensu.ca

**Book:** *A Concise Introduction to the Theory of Numbers* by Alan Baker (ISBN-10: 0521286549). This is available in the bookstore.

**Course Information: ** It is required that you read and understand the course syllabus.

**Homework: **Watch this page for homework assignments and solutions.

**Introduction: ** *''No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone
will do so for many years.",* - G.H. Hardy, 1940. Five years before Hiroshima and 33 years before the invention of public key cryptography.

Despite the unintended irony of Hardy's words, it is not especially easy to imagine how the concepts and ideas introduced in this class could ever be of much "use" to anyone, for good or for ill. Generally, number theorists tend to engage in number theory because its fun, interesting, and at times beautiful. While other branches of mathematics certainly have their charms, the first barrier to entry when it comes to studying the natural numbers is a relatively low one, and pulling unintuitive truths out of the things you once played with in kindergarten can, at times, feel like alchemy.

This course will introduce you to some of the underlying concepts of a few areas of modern number theory, making use of some tools you should already have some familiarity with like ring theory and modular arithmetic, and intends to serve as a fruitful playground for the methods of mathematical proof.

It is unlikely but admittedly unknown that what is studied here will create or solve the challenges of tomorrow. Regardless, number theory is a great treasure of the mind and a triumph of collective creativity over passive ignorance. By engaging with it you are also experiencing it and in so doing are keeping the torch of human civilization burning.

So good on you! Try not to hurt anybody.

**The Course So Far:**

Day | Description | Notes | Practice Problems |

Week One |
|||

M 9/8 | Course Introduction. The Division Algorithm | Notes 1 | Chapter 1: Problems (v) and (viii). |

T 9/9 | Euclidean Algorithm, Primes Unique Factorization | Notes 2 | Assignment 0 Due Chapter 1: Problems (i),(ii), and (iv) |

Th 9/11 | Properties of Primes, Floor Function | Notes 3 | Chapter 1: Problem (vi) |

Week Two |
|||

M 9/15 | Multiplicative Functions, Euler's Phi Function | Notes 4 | Chapter 2: Read and try to understand the rest of section 2.3. |

T 9/16 | Mobius Inversion | Notes 5 | Chapter 2: Problem (iii) |

Th 9/18 | More Mobius Inversion and Divisor Functions | Notes 6 | Chapter 2: Problems (i) and (vi) |

Week Three |
|||

M 9/22 | Bounds and Average Orders | Notes 7 | Chapter 2: Problem (ix) |

T 9/23 | Finishing Average Orders | Notes 8 | Read 2.7 and/or the lecture notes on Perfect Numbers, just for your personal edification. |

Th 9/25 | Riemann Zeta Function | Notes 9 | Assignment 1 Due Solutions |

Week Four |
|||

M 9/29 | Congruence and Chinese Remainder Theorem | Notes 10 | Chapter 3: Try Problem (vii) This will be easier when you learn about primitive roots. |

T 9/30 | Proof of Chinese Remainder Theorem, Fermat's Little Theorem, Euler's Theorem | Notes 11 | Chapter 3: (i), (ii) |

Th 10/2 | Alternative Proof of the Multiplicativity of φ(n), Wilson's Theorem | Notes 12 | Have a good weekend. |

Week Five |
|||

M 10/6 | When -1 is a square (mod p) and Lagrange's Theorem | Notes 13 | Chapter 3: (iv) |

T 10/7 | Order and Primitive Roots | Notes 14 | Chapter 3: (iii) |

Th 10/9 | Primitive Root Theorem and Indices | Notes 15 (Includes Proof of Primitive Root Theorem) The Index of Negative One |
Assignment 2 Due Solutions Chapter 3: Try Problem (vii) again. |

Week Six |
|||

M 10/13 | Thanksgiving Day, No Class | ||

T 10/14 | Quadratic Residues and The Legendre Symbol | Notes 16 Facts we Will Prove About the Legendre Symbol |
Chapter 4: (i),(ii),(iii),(vi),(viii) |

Th 10/16 | Jacobi Symbol, Euler's Criterion | Again, Notes 16 Facts we Will Prove About the Legendre Symbol |
Chapter 4: (v) |

Week Seven |
|||

M 10/20 | Finished Euler's Criterion, Gauss's Lemma | Notes 17 | Not today. |

T 10/21 | Finish Gauss' Lemma, Start Proof of Quadratic Reciprocity | Notes 18 | Not today. |

Th 10/23 | Finish Proof of Quadratic Reciprocity, Quadratic Residues for odd prime powers | Notes 19 | Assignment 3 Due Solutions |

Week Eight |
|||

M 10/27 | Quadratic Residues for odd n, Binary Quadratic Forms | Notes 20 | None Yet |

T 10/28 | Equivalent Forms and Proper Representation | Notes 21 | Midterm Exam Tonight |

Th 10/30 | Reduced Quadratic Forms, Class Number | Pages 56, 60, 61 of Notes 22 |
Chapter 5: (i),(vi) |

Week Nine |
|||

M 11/3 | How to Reduce Quadratic Forms, Bounding Below | Page 56-58 of Notes 22 |
Chapter 5: (vii) |

T 11/4 | Uniqueness of Reduced Form, Properly Represented n | Page 58-59 and 61 of Notes 22 |
Chapter 5: (ii) |

Th 11/6 | Proper Representation Theorem, Sum of Two Squares | Sections 5.3 and 5.4 of Notes 23 |
Chapter 5: (ii), (iv), (v), (vii) |

Week Ten |
|||

M 11/10 | Sum of Squares | Sections 5.4 and 5.5 of Notes 23 |
None today. |

T 11/11 | Pigeonhole Principle and Dirichlet's Theorem | Notes 24 | None today. |

Th 11/13 | Dirichlet's Theorem Corollary, Continued Fractions | Notes 25 | Assignment 4 Due Solutions |

Week Eleven |
|||

M 11/17 | Continued Fraction of Irrational Numbers | Notes 26 | Chapter 6: (ii) and (iii) |

T 11/18 | Recursive Lemma [Ugh.] | Notes 27 | Chapter 6: (i) |

Th 11/20 | Quadratic Irrationals and Eventually Periodic Continued Fractions | Notes 28 | Done. |

Week Twelve |
|||

M 11/24 | Pell's Equation | Notes 29 | Two Days Left! |

T 11/25 | Algebraic and Transcendental Numbers, Fermat's Last Theorem | Notes 30 | A Short Proof of the Simple Continued Fraction Expansion of e by Henry Cohn |

Th 11/27 | Fermat's Last Theorem and Elliptic Curves | Notes 31 | Assignment 5 Due Solutions |

Here's a picture of me wearing only one shoe and standing in front of the Oscar Mayer Weinermobile:

And here's a link to a video of my Linear Algebra Class being disrupted.

** **