# MA2316: Introduction to Number Theory

## Hilary term, 2013

Lecturer: Masha Vlasenko

The goal of this course is to introduce the basic concepts of number theory, both analytic and algebraic. We begin with the classical questions such as factorisation, distribution of primes and finding integer solutions to algebraic equations. The second part of the course deals with analytic methods. We will study Riemann zeta function, discuss Riemann hypothesis and prove the theorem on primes in arithmetic progressions. If time admits we will introduce algebraic field extensions and basics of Galois theory, and see that the theorem on primes in arithmetic progressions follows from Chebotarev's density theorem.

The course will be accompanied by weekly tutorials in the form of problem-solving sessions. We will learn how to use computers to do number theory. To follow the computational part of the course please install PARI/GP calculator (or learn how to run it in the computer lab) and have the reference card of PARI functions in hand. Tutorials take place on Thursdays at 2 pm in Syn2. For those who can not attend on Thursdays there is an additional class, which is at the moment on Fridays at 4pm in EELT2.
Prerequisites: basics of analysis, linear algebra and group theory (MA1124,MA1212, MA1214). Knowledge of fields, rings and modules (MA2215) and complex analysis (MA2325) is not necessary but will help to understand selected topics.

Literature
[1] I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, Fifth Edition
[2] J.-P. Serre, A Course in Arithmetic
[3] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory
[4] S. Lang, Algebra

Our major textbook is [1]. This book, although 20 years old, is renowned for its interesting, and sometimes challenging, problems. Please see Montgomery's home page for the lists of typos and errors in the book. Note that there are multiple lists because the book has been reprinted several times.

Comments on the exam paper <here>.

Topics of lectures and relevant material
1. Introduction: Diophantine equations, Pythagorean triples, Fermat's Last Theorem and the Birch and Swinnerton-Dyer Conjecture. <pdf>
2. Divisibility and the Euclidean algorithm. <pdf>
• Tutorial 2, January 25th: §1.2 in [1], questions 1,2 and 3 (using computer, in 3 find all solutions), 4b, 5, 7, 15, 25, 27, 47*, 53* and the following question. Using PARI/GP apply the Euclidean algorithm to find a greatest common divisor h(x) of the polynomials f(x)=x^5-4*x^3+3*x^2-x+1 and g(x)=x^8+5*x^4-6. Represent it in the form h(x)=h1(x)*f(x)+h2(x)*g(x). Do there exist polynomials h1(x) and h2(x) such that x^2013-1=h1(x)*f(x)+h2(x)*g(x)?
<solutions> Reporters: Erle Holgersen, Claire MacSharry, Cliona Rogan, Ray Allen, Lauren Watson
• Extracurricular assignment: read §1.3 in [3] up to Corollary 1, solve 54** after §1.2 in [1]
3. Primes, uniqueness of factorisation and integers in quadratic fields. <pdf> <pdf> <pdf><pdf>
• Tutorial 3, January 31st & February 1st: §1.3 in [1], questions 2, 10, 11, 16, 17, 26, 27, 30, 31, 42, 44, 48*. For question 48 look at the wikipedia entry on Fermat numbers.
<solutions> Reporters: Bonnie Flattery, Michael Meenagh, Cian O'Byrne, Caoimhe Rooney
NEWS: on January 25th 2013 the next Mersenne prime p=2^57885161-1 was discovered. It is the largest known prime at the moment. Notice that the number 57885161 is itself a prime as it should be according to question 44 in the homework.
• See §9.2-9.4 of [1] for the basics on algebraic numbers.
• Tutorial 4, February 7th & 8th: from [1] §9.2 questions 1,2,3, §9.4 question 3, §9.5 questions 4,5,6, §9.6 question 1, §9.7 questions 2,3,4.
<solutions> Reporters: Jacob Miller, Karl Downey, Graeme Meyler, Conn McCarty, Eric Hattaway
<handout>
• Playing with number fields in PARI/GP: <handout>
• Tutorial 5, February 14th & 15th: experiments in PARI with units and class numbers in quadratic fields. Exercises 1-4 in the above handout. Here it is in <latex>, just in case.
<experiments> <solutions> Reporters: Garrett Thomas, Aran Nolan
Remarks: in question 2 "n odd" and "n even" are interchanged in the formula for B_n; in 4a) it is concluded that 2,3 are primes before it is checked that there are no elements of norm -2 and -3; the proof that c^2-15*d^2=-3 has no solutions is incorrect, but reducing it modulo 5 works.
<handout>
• wikipedia entry on Gauss' class number problem, check the paper by Dorian Goldfeld in the list of references
4. Congruences I: Fermat's Little Theorem and Euler's generalisation <pdf>, the Chinese Remainder Theorem <pdf>, prime power moduli<pdf>.
• Tutorial 6, February 21st: §2.1 in [1], questions 5,8,9,18,19,20,24,25,29,30,43,45*,49*,50*,55*.
<solutions> Reporters: Benen Harrington, Corey Switzer, Celia Ho, Lorna Ginnety, Alice Lennon
• Study week challenge. Solved by: Padraig Condon, Hui Teng Chew.
• Tutorial 7, March 7th: from [1] §2.3, questions 8,14,17,32,39,42*; §2.6, questions 1,2,3,4.
<solutions> Remark: §2.3 question 32 not all solutions are found)
<corrections to §2.3 question 32>
Reporters: Niamh Bermingham-McDonogh, Aideen Moulton, Harry O'Reilly, Donal Egan, Thomas Bourke
• Read about public-key cryptography in [1],§2.5 or somewhere else.
5. Congruences II: primitive roots <pdf> <pdf>
• Tutorial 8, March 14th: from [1] §2.8, questions 1,2,3,9,10,11,18,22; show that the cyclic group of order N has phi(N) generators.
<solutions> Reporters: Mark Quinn-Nealon, Sean O'Malley
Remark: there is no need to use quadratic residues in question 22, since for every primitive root g, g^((p-1)/2) = -1 mod p as it was proved in one of the previous questions. Moreover, we didn't study quadratic residues yet, and the proof that (a/p) = a^((p-1)/2) which I am going to show in class uses Wilson's congruence itself.
6. Congruences III: Legendre symbols and the Quadratic Reciprocity Law.<pdf>
• Tutorial 9, March 22nd: from [1] §3.1, questions 11,12, 20*, §3.2, questions 1,2,3,4; §3.3, questions 3,5; prove that the congruence a x^2 + b x + c = 0 (mod p) with (a,p)=1 has two solutions, one solution and zero solutions when the Legendre symbol (D/p)=1,0,-1 respectively, where D=b^2-4ac; do there exist solutions to the congruence x^2+x+1=0 (mod 637)?
<solutions> Reporters: Max LaVictoire, John Madden, Kimara Lynch, Ewan Dalby, Keith Glennon
• Challenge: fill in the details of the proof on the Quadratic Reciprocity Law from the lecture (both parts (i) and (ii), written clearly). This is for 20% (the whole continuous assessment mark) to the first person submitted (only if correct), 5% to the second, and 2% for everyone else.
7. Analytic methods I: Riemann's zeta function.<pdf>
8. Analytic methods II: Dirichlet's characters, L-functions and primes in arithmetic progressions.<pdf>
• Assignment, due on April 4th: <pdf><tex> (a misprint with the normalisation of the scalar product was corrected on the 2nd of April)
Reporters: Conor Fagan, Theo Anderson, John Prasifka, Nastya Vavryk
• Extracurricular assignment: read Chapter IV in [2], it contains the extended version of the proof of Dirichlet's Theorem given in class
9. Analytic methods III: Riemann's Hypothesis (<pdf>, <pdf>) and distribution of primes <pdf>.
• A few lemmas from complex analysis that we used without proof in class: <pdf>
• PARI/GP script approximating the Chebyshev psi function using zeros of the Riemann zeta function,
to run it on gstokes type "ssh gstokes", go to the folder where you stored the script, type "gp" to run PARI/GP and then "\r zetazeros.gp" to load the script
Unfortunately higher resolution graphics is disabled on gstokes, you will see more using your own installation of PARI
• An animation showing how psi function is approximated by the sum of waves can be found here
• Tables of zeta zeros by Andrew Odlyzhko
• Wikipedia entry containing the exact formula for the Chebyshev psi function from the lectures
• Wikipedia entry on the Prime Number Theorem