Introduction to number theory, TCD 2013/14

Lectures

Mon, 15:00 - 15:50 Salmon Lecture Theatre
Thu, 12:00 - 12:50 Synge Lecture Theatre

Tutorials

Thu, 14:00 - 14:50 Synge Lecture Theatre

Tutorial 1 (for January 23, 2014): [PDF]
Reporters: Stephen Burke, Adam Keilthy, Marianna Kelly, Katarina Manojlović, Aisling Mullins. Solutions: [PDF]. In the last solution, the logical step going from the line 4 to the line 5 is not really valid, but fortunately it did not affect the argument too much, since from line 4 one deduces 2^{2n–⁴ⁿ⁄₃} < (2n)^√ 2n, and then one can proceed with comparing the growth of logarithm and square root (with different constants) as indicated.

Tutorial 2 (for January 30, 2014): [PDF]
Reporters: Sean Bray, Jason Coyle, Clara Kavanagh, Owen Ward, Olena Yavorska. Solutions: [PDF]. In the solution to question 2, there are several misprints that make it difficult to follow. The paragraph starting with "Therefore" should rather go as follows: Therefore Db²=K+1/4. Let b=c/d in lowest terms. Then the denominator of Db² divides d², and on the other hand is equal to 4, so 4 divides d², and 2 divides d, d=2l. We then have Dc²=(4K+1)l², so l² divides Dc², hence l² divides D (as c/d=c/(2l) is written in lowest terms), but D is square-free, so l=1. Thus, b=c/2 is in 1/2+Z, so in this case both a and b are in 1/2+Z. Finally, if a=n+1/2, b=m+1/2, then a²-Db²=n²+n+1/4-D(m²+m+1/4)=S+(1-D)/4, where S is an integer. Therefore, for this number to be an integer, we should have D to be congruent to 1 modulo 4. In the last question, there is a misprint, the distance is of course |β|, not β, and it affects a few formulas.

Tutorial 3 (for February 6, 2014): [PDF]
Reporters: Sean Diffley, Eric Hattaway, Conn McCarthy, Nathan O Duill, Michael Ferreira. Solutions: [PDF].

Tutorial 4 (for February 13, 2014): [PDF]
Reporters: Ciaran Brennan, Kevin Coughlan, Rory Higgins, Jamie Khan, Michael Reynolds. Solutions: [PDF]. The last solution is unfinished. The sum which is given as an answer is obviously equal to the sum of two: first, p times 1, second, the sum of Legendre symbols of 1-y² mod p. With the exception for y=-1, for which the respective symbol is 0, we can note that 1-y² is, up to the square (1+y)², equal to (1-y)/(1+y). As y ranges over elements different from -1, (1-y)/(1+y) ranges over the same elements, so the second sum is equal to the sum of all Legendre symbols (which we know to be equal to zero) except of that of -1 mod p, that is (-1)^(p-1)/2. Overall, the answer is p-(-1)^(p-1)/2.

Tutorial 5 (for February 20, 2014): [PDF]
Reporters: Orlagh Carroll, Conor Hughes, Ciara Moynihan, Colm O'Shaughnessy, Sile Tiernan. Solutions: [PDF]. In Question 4, it is more beneficial to say that we lift the solution to g(x)=x²-2 by Hensel's lemma, rather than applying that lemma to f(x), since otherwise it is not immediately clear why f'(a) is not divisible by p.

Study week challenge (to be submitted in class on March 3, 2014): [PDF] Solutions to Part B (practical): [PDF]

Tutorial 6 (for March 13, 2014): [PDF]
Reporters: Sadhbh Stapleton Doyle, Daniel Hynes, Huitian Li, Maria Jesús Muñoz Lopez, Eoin Walsh. Solutions: [PDF]. In Question 3, there is a misprint, (2/p)=(-1)^{(16k²+24k+8)/8)}, not (-1)^{(11k²+24k+8)/8)}. Also, in that question, a somewhat easier solution (that I mentioned in class) is to note that among the numbers -1, 2, and -2, at least one must be a square residue, since the product of two square non-residue is a square residue, and then proceed as in the typed solution. In Question 5, the solution is not very clearly explained (I cannot really make sense of the sentence after the picture). I would just say instead that since the edge diagram of the product is the union of edge diagrams of factors, that means that if this polynomial can be factorised, then one of the factors is of degree 1, since one of the two edges of the diagram is of horizontal length 1.

Tutorial 7 (for March 20, 2014): [PDF]
Reporters: Jack Geary, Benjamin Levai, Callum MacIver, Darragh Monnin, Eoghan Sheridan. Solutions: [PDF]. The second half of the solution to Question 4 is not written very clearly, and has a misprint in the end of it. One can go as follows: we know from Question 2 that if the order of a is equal to s, then s divides n. If s is less than n, then by Question 3 n=sq^t, and s divides q-1, so q is the largest prime divisor of n, contradiction. So the order of a is equal to n (not m, as in the solution provided).

Tutorial 8 (for March 27, 2014): [PDF]
Reporters: Thomas Bourke, John Doyle, Peter Mulholland, TJ O Sullivan, Lauren Watson. Solutions: [PDF]. In Question 1, one should drop the 8th line, it has misprints but is not relevant for what follows. In Question 3, there is a somewhat simpler solution: e.g. in (a), we note that n is even, so has common factors with all even numbers smaller than n, so φ(n)≤n/2, and is equal to n/2 only if n has no odd factors. Finally, Φ₁₀(x)=x⁴-x³+x²-x+1 (there is a misprint in the typed formula). For the practical part of Question 5 (computing Φ₁₀₅(x)): any computer software would do, I was using the MAGMA online calculator; the input

Q := RationalField();
P<x> := PolynomialRing(Q);
((x^105-1)*(x^3-1)*(x^5-1)*(x^7-1)) div ((x^15-1)*(x^21-1)*(x^35-1)*(x-1));

(which you are welcome to paste into that online calculator) tells us that Φ₁₀₅(x)=x⁴⁸ + x⁴⁷ + x⁴⁶ - x⁴³ - x⁴² - 2x⁴¹ - x⁴⁰ - x³⁹ + x³⁶ + x³⁵ + x³⁴ + x³³ + x³² + x³¹ - x²⁸ - x²⁶ - x²⁴ - x²² - x²⁰ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² - x⁹ - x⁸ - 2x⁷ - x⁶ - x⁵ + x² + x + 1.

Tutorial 9 (for April 3, 2014): [PDF]
Reporters: Leo Janssens, Conor McMeel, Kondrad Timon, Niall Thornton, Daniel Vernon. Solutions: [PDF]. In Question 2, the last sentence instead of "which is a product of irreducible elements in Q[x]" it should say "and these factors cannot be grouped together to obtain a nontrivial factorisation in Q[x]". In Question 3, to justify |p_m/q_m-p/q|≥1/(qq_m), one has to remark that we cannot have p_m/q_m=p/q for all sufficiently large m, since then p_m/q_m=p_m-1/q_m-1, and hence a+(-1)^mc=0 for all m, odd or even, which implies a=c=0. In Question 6, it is important that not only Z[i] is a UFD, but that 2+i and 2-i are primes, of course.

Weekly summary

Week 1: Introduction. Eight proofs of the infinitude of prime numbers. [PDF] Chebyshev's estimates for π(N). [PDF]
Week 2: Uniqueness of prime factorisation. Quadratic fields. Norm-Euclidean rings of algebraic integers. [PDF]
Week 3: Modular arithmetics. Primitive roots. [PDF]
Week 4: Quadratic residues. Quadratic reciprocity law. [PDF]
Week 5: Equations modulo prime powers and Hensel's lemma. [PDF] Metric number theory: p-adic numbers, Ostrowski's theorem. [PDF]
Week 6: Diophantine equations and geometry. Pythagorean triples, n=4 case of Fermat's last theorem, Markov's equation. [PDF]
Week 7: Reading week, no classes.
Week 8: Recollection on polynomials. Newton's polygons. Irreducibility criteria of Eisenstein and Dumas. [PDF] Diophantine equations for polynomials. [PDF] In tutorial class on Thursday, there was a quiz instead of a regular tutorial. [PDF] Solutions to the quiz: [PDF]
Week 9: Cyclotomic polynomials and their applications: Elementary proof of the infinitude of primes in the arithmetic sequence a_n=dn+1; Wedderburn's Little Theorem. [PDF]
Week 10: Some classical arithmetic functions: Dirichlet's σ and τ functions, Euler's φ function, Möbius's μ function. Möbius inversion and its applications in combinatorics. More arithmetic functions: Mangoldt's Λ function, Chebyshev's ψ function. [PDF]
Week 11: Asymptotic analysis of arithmetic functions. [PDF] Algebraic numbers. Liouville's theorem and existence of transcendental numbers. [PDF]
Week 12: Irrationality of e. Chebyshev's functions and asymptotics of π(n). Some equivalent forms of the Riemann hypothesis. [PDF] Revision of the course.

About this module

The ultimate goal of this module is to introduce the students to most of the basic concepts of number theory, at the same time demonstrating interactions of number theory with other areas of maths and giving an overview of number-theoretic methods and results of contemporary mathematics. This ambitious goal is achieved through combining rigorous proofs with only hints on proofs and even just vague ideas in some cases, the latter being more of a roadmap for future studies rather than an examinable material.

The module will include weekly tutorials in the form of problem-solving sessions. Tutorials take place on Thursdays at 2 pm; in the end of each tutorial, questions for the next tutorial will be made available.

Prerequisites: The module relies on basic linear algebra (vector spaces, dimensions) and group theory (mainly Lagrange's theorem) from the first year, and fields-rings-modules from the beginning of the second year (ideals, Euclidean domains, PID, UFD); some basics of metric spaces and complex analysis would help but will be recalled along the way.

Syllabus

Infinitude of primes: various proofs. First instance of analytic methods: Chebyshev's estimates and Bertrand's postulate.
Uniqueness and non-uniqueness of prime factorisation. Integers in quadratic fields. Units in quadratic fields and Pell's equation.
Recollections on modular arithmetic. Combinatorics and number theory: Fermat's Little Theorem and Euler's Theorem, and their matrix generalisations. Primitive roots. Quadratic residues. Quadratic reciprocity law.
Some classical arithmetic functions: Dirichlet's σ and τ functions, Euler's φ function, Möbius's μ function. Möbius inversion and its applications in combinatorics.
More arithmetic functions: Mangoldt's Λ function, Chebyshev's ψ function. Asymptotic analysis of arithmetic functions. Some equivalent forms of the Riemann hypothesis.
Diophantine equations and geometry. Pythagorean triples, n=4 case of Fermat's last theorem, Markov's equation.
Metric number theory: p-adic numbers, Ostrowski's theorem. Equations modulo prime powers and Hensel's lemma.
Recollection on polynomials. Newton's polygons. Irreducibility criteria of Eisenstein and Dumas. Fermat's last theorem for polynomials, and complications arising for integers (the abc conjecture).
Cyclotomic polynomials and their applications: Elementary proof of the infinitude of primes in the arithmetic sequence a_n=dn+1; Wedderburn's Little Theorem.
Number theory meets computer science and cryptography: the Agrawal--Kayal--Saxena primality test and the Rivest--Shamir--Adleman algorithm.
Algebraic numbers. Liouville's theorem and examples of transcendental numbers.

Textbooks

H. Davenport, The higher arithmetic. Cambridge University Press, 2008. (Modular arithmetic, RSA etc.)
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Oxford University Press, 2008. (Many parts of the course are there; in particular, this book contains an awful lot of information on algebraic and transcendental numbers.)
Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory. Springer, 1990. (Chinese remainder theorem, irreducibility, diophantine equations, modular arithmetic.)
Neal Koblitz, P-adic numbers, p-adic analysis, and zeta-functions. Springer, 1984. (Mainly Chapter 1 on p-adic arithmetic.)
Serge Lang, Math talks for undergraduates. Springer, 1999. (Mainly talk 2, on Fermat theorem for polynomials, the abc-conjecture etc.)
I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, Fifth Edition, 1991. See also errata on Montgomery's webpage. (An extensive treatment of most parts of the course.)
Victor V. Prasolov, Polynomials. Springer, 2004. (Mainly Chapter 2, including various results on irreducibility.)

Assessment

Continuous assessment contributes 20% of your final mark. There are two ways of earning marks through continuous assessment: by solving a question on the board during a tutorial (which earns 2%, i.e. 1/10 of the maximal 20%; one cannot get more then 2% per week even if they solve two questions or more) and by writing writing solutions to the weekly problem batch in LATEX (each week a group of up to 5 "reporters" is assigned to do this job as acollective during that week, the outcome of their work is a PDF file compiled from LATEX containing complete solutions for that week's problems, for which each reporter earns 10%, i.e. 1/2 of the maximal 20%; one can be a reporter only once).

Disclaimer

The person who is solely responsible for the choice of content on this page is Vladimir Dotsenko. Any views expressed here do not necessarily represent the official views of Trinity College Dublin.