## Introduction to Number Theory (NMAI040), winter term 2017/2018

As I am lecturing in English this term, information here will be in English too. For this course in previous years see here (in Czech, though). Syllabus and annotation in SIS. Here are lectures notes in English, here are some errata. Lectures are on Friday in S4 (3rd floor of the Malostranske square building) in 9-10:30 I built this course on the classical book G. H. Hardy & E. M. Wright: An Introduction to the Theory of Numbers and (almost) everything I am lecturing about can be found there.  In the lectures I may provide further references and literature.
Examination is in oral form (you get a question from the following list, prepare for some time and then explain it to me). Terms of examinations: see SIS (or by appoinment). Questions: 1a. Dirichlet's theorem on diophantine approximations and applications.  1b. Existence of transcendental numbers by Liouville's inequality. 1c. Proof that e is transcendental.  2a. Theory of the Pell equation. 2b. The Stothers-Mason theorem and proof of the FLT for polynomials.  3a. Lattices and their properties,  Farey fractions via plane lattices. 3b. Geometrical  proof of Lagrange's 4 squares theorem. 4a Give five proofs of infinitude of prime numbers. 4b. Čebyšev's estimates of the primes counting functione pi(x). 5. Prove the quadratic reciprocity law. 6a. Prove by PIE the Cohen - Remmel metaidentity for partitions. 6b. Prove Euler's pentagonal identity.

lecture 1, October 6, 2017. 1. Diophantine approximation. Dirichlet's theorem (DT): part 1 says that |a - p/q| < or = 1/qQ has for any real number a and an integer Q > 1 at least one rational solution p/q with 0 < q < Q, part 2 says that |a - p/q| < q^{-2}has for any irrational real number a infinitely many rational solutions p/q. I mentioned (without proofs) three other results of P. Dirichlet in NT: i) theorem on prime numbers in arithmetic progression (which is his most famous and most important), ii) asymptotic of the sum sum_{n<x}tau(n) where tau(n) counts divisors of n, iii) structural theorem on the group of units in the ring of integers of a number field (Dirichlet's theorem on units, I will state it precisely later when we discuss solutions of the Pell equation). As a corollary of part 1 of DT we proved the Euler-Fermat theorem: every prime number of the form p = 1+4n is a sum of two squares. We used a Lemma: -1 is quadratic residue modulo such p. Proof: if a = ((p - 1)/2)! then a^2 is -1 modulo p.

lecture 2, October 13, 2017. A corollary of part 2 of DT: every Pell equation x^2 - dy^2 = 1 (d > 0 and is not a square) has a nontrivial solution x, y in Z;  proof. The Farey fractions - another way how to prove part 2 of Dirichlet's theorem, in fact even that |a - p/q| < 1/2q^2 has for any irrational real number a infinitely many rational solutions p/q (an exercise for you). The best constant in the denominator is 5^{1/2}, as Hurwitz proved; so |a - p/q| < 1/5^{1/2}q^2 has for any irrational real number a infinitely many rational solutions p/q but for a = (5^{1/2} - 1)/2 and any A > 5^{1/2},  |a - p/q| < 1/Aq^2 has only finitely many rational solutions p/q (without proof). Algebraic and transcendental (real) numbers. Existence of transcendental numbers via Liouville's inequality: |a - p/q| > c/q^n for any real algebraic number a of deg(a) = n > 1 and any fraction p/q (here c = c(a) > 0 is a constant); proof. Thus the number beta := sum 1/10^{n!} is transcendental; proof as an exercise. I mentioned the theorem of Roth: the n in Liouville's inequality may be replaced with 2 + epsilon.

lecture 3, October 20, 2017. I mentioned Thue's inequality from 1908: |a - p/q| >>_{a, ep}q^{-n/2 - 1 - ep} for any real algebraic number a with deg(a) = n > 1, any ep > 0 and any fraction p/q. It implies that every Thue's equation F(x, y) = c has only finitely many integral solutions x, y (here c is an integer and F is a homogeneous integral polynomial that is irreducible in Q[x, y] and has degree at least 3, e.g. x^3 - 2y^3). Hermite's theorem with Hilbert's proof: the number e = 2.71828... is transcendental. 2. Diophantine equations.  Theorem (Putnam, Davis, Robinson, Matiyasevich): solvability of a given Diophantine equation P = 0 is (algorithmically) undecidable (here P is in Z[x_1, ..., x_n] and we seek a solution in Z), without proof of course. Exercise: show that one can (algorithmically) reduce the solvability problem to polynomials with degree at most 4. Pythagorean triples: integral solutions of x^2 + y^2 = z^2. Theorem: (x, y, z) is a primitive P. triple (x, y, z coprime, positive, x even y, z odd) <=> x = 2ab, y = a^2 - b^2, z = a^2 + b^2 with a > b > 0 being coprime integers, one odd and the other even, proof next time.

lecture 4, October 27, 2017. I indicated by an example the reduction from the exercise, a smaller example is here: x^5 + y^6 = 22334455667788 is solvable <=> (a - x^2)^2 + (b - a^2)^2 + (c - bx)^2 + (d - y^2)^2 + (e - d^2)^2 + (f - de)^2 + (c + f - 22334455667788)^2 = 0 is solvable (Mr. Skotnica pointed out that I had omitted the last square). Proof of the theorem about primitive P. triples. Fermat's theorem (FLT for n = 4): x^4 + y^4 = z^2 has no nontrivial solution (solution in N), proof by infinite descent. The Stothers-Mason theorem (SMT): if a, b, c in C[t] are coprime polynomials, not all of them constant, such that a + b = c then max(deg a, deg b, deg c) < r(abc) where r(p) is the number of distinct roots of a polynomial p, proof next time. I concluded with showing that the SMT => if a, b, c in C[t] are coprime polynomials, not all of them constant, and n > 0 is an integer  such that a^n + b^n = c^n then n < 3. This is FLT (Fermat's last theorem) for polynomials. But I promised to show next time for it a more direct proof, not using the SMT.

lecture 5, November 3, 2017. Proof of the SMT.  A direct proof of the FLT for polynomials: if a, b, c in C[t] are coprime polynomials, not all of them constant, and n > 0 is an integer  such that a^n + b^n = c^n then n < 3. Proof goes as follows. Suppose for contradiction that n > 2 and that max(deg a, deg b) is minimum. For  odd n we have factorization c^n = a^n + b^n = (a + b)(a + bd)(a + bd^2) ... (a + bd^{n-1}) where d is a primitive n-th root of 1 (for even n we switch to c^n = a^n - b^n). Since the factors are coprime and C[t] is a UFD (and every unit in C[t] is an n-th power), a + bd^j = e_j^n for every j = 0, 1, ..., n-1 and some polynomials e_j. This and the identity (a + bd^2) + d(a + b) = (1 + d)(a + bd) give a smaller solution - a contradiction. Examples of large smallest nontrivial solutions of Pell equations. Theorem: S = {positive solutions a + bd^{1/2} of the Pell equation x^2 - dy^2 = 1}(with the usual multiplication of real numbers) is the infinite cyclic group and R = {all solutions} = S times Z_2. Proof next time.

lecture 6, November 10, 2017. Some more remarks on Diophantine equations, FLT, formalized proofs and the Feit--Thompson theorem from group theory. Proof of the structural theorem for solution sets of Pell equations. Generalized Pell equation x^ - dy^2 = m (m is a nonzero integer, d as before) - either no solution or infinitely many. Some remarks on Dirichlet's theorem on units and on the abc conjecture and Mochizuki's purported proof.  3. Geometry of numbers. Lattices in R^n, their bases and fundamental parallelepipeds.

November 17, 2017.  State holiday.

lecture 7, November 24, 2017. Proof of the independence of the lattice volume of the basis. Shifts of the fundamental parallelepiped by all vectors in the lasttice partition R^n. By this I proved the basic property of Farey fractions: two consecutive ones (of order n) have minimum possible distance (reciprocal of the product of their denominators). Minkowski's theorem: If B is a bounded, convex and centrally symmetric body in R^n, L is a lattice in R^n and Vol(B) > 2^n.Vol(L), then B intersects L in a point different from the origin, proof. Lemma: 1) the congruence a^2 + b^2 + 1 =  0 (mod p) is always solvable and 2) the same holds for any square-free modulus m in place od the prime p, proof postponed to the next lecture. Lagrange's theorem: any integer n > -1 is sum of four squares, proof by means of Minkowski's theorem and the Lemma. 4. Prime numbers. I promised to give 10 (ten) proofs of Eucli'd theorem on infinitude of prime numbers (but I must not forget to prove the Lemma).

lecture 8, December 1, 2017. Proof of the Lemma from the last lecture. Ten proofs of infinitude of prime numbers. 1. The proof of Euclid. 2. The proof of Goldbach. 3. The first proof of Erdos (by the mapping n |-> (A,b) ). 4. The second proof of Erdos (by the inequality p^k || {n choose m} => p^k < n + 1 ). 5. The proof by periodic sets of integers (the simplified version of Furstenberg's topological proof, due to Cass and Wildenberg).

lecture 9, December 8, 2017. 6. The proof based on the counting bound #{m_1^{a_1}... m_k^{a_k} < x | a_i are nonnegative integers} = O((1 + log x/log 2)^k) where m_i > 1 are k fixed integers. The remaining four proofs use Euler's identity prod_p (1 - 1/p^s)^{-1} = sum_n 1/n^s. 7. The proof of Euler (s=1, infinite sums). 8. The proof of Sylvester (s=1, finite sums). 9. The proof of Euler again (s --> 1+). 10. Formal proof  (s is a formal variable). Čebyšev's bounds c_1x / log x < pi(x) < c_2x / log x.

lecture 10, December 15, 2017. Čebyšev's bounds c_1x / log x < pi(x) < c_2x / log x, conclusion of the proof . 5. Quadratic congruences. Quadratic residues and non-residues, Legendre's symbol (a/p), Euler's criterion, multiplicativity of (a/p) in a. The 1st suplement (of the q. reciprocity law) (-1/p) = (-1)^{(p - 1)/2}. Statement of the reciprocity law and of the 2nd suplement. Gaus lemma  (proof next time) and deduction of the 2nd suplement that (2/p) = (-1)^{(p^2 - 1)/8}.

lecture 11, December 22, 2017. Proof of the Gauss lemma. The sum S(a, b) = sum_{0 < j <b / 2}[ja / b] (here a, b > 1 are odd and coprime and [.] is lower integer part) and its two properties:  S(a, b) + S(b, a) = (a - 1)(b - 1) / 4 and (-1)^{S(a, p)} = (a / p), these prove the reciprocity law. 6. Integer partitions. Definition of the partition function p(n), Euler's identity for its GF. Another identity of Euler: the number of partitions of n into distinct parts = the number of partitions of n into odd parts, proof by GF. Next time: proof of the last identity of Euler by PIE (the principle of inclusion and exclusion, in a more general setting) and Euler's pentagonal identity.

lecture 12, January 5, 2018. PIE and its corollary. Integer partitions as finite multisets (of natural numbers). Norm ||M|| of a multiset M, containment of multisets, their union and sum. The Cohen - Remmel metaidentity: If A_1, A_2, ... and B_1, B_2, ... are injective sequences of partitions such that ||A|| = ||B|| whenever A and B are finite unions of A_i's and B_i's with the same indices, then for every n there are as many partitions of n avoiding every A_i as are those avoiding every B_i, proof. Example: every n has as many partitions into non-squares as partitions such that each part m has multiplicity less than m. Euler's pentagonal identity and its three formulations, proof next time.

lecture 13, January 12, 2018. Proof of equivalence of the three formulations of Euler's pentagonal identity. Franklin's bijective proof of the partition formulation. Proof, by the generating function sum p(n)x^n = prod(1 - x^n)^{-1}, of the partition function bound p(n) < (pi / sqrt{6(n - 1)})exp(pi.sqrt{2n / 3}).

January (= leden (led = ice)) 2018