Introduction To Algebraic Number Theory Part I

Introduction to Algebraic Number TheoryPart IA. S. MosunovUniversity of WaterlooMath CirclesNovember 7th, 2018

GoalsIExplore the area of mathematics called Algebraic NumberTheory.ISpecifically, we will see how to generalize the notions ofintegers, rational numbers, prime numbers, etc.IGoal 1. Understand the basics of the theory.IGoal 2. See beautiful theorems.IGoal 3. Understand open problems.

Number TheoriesINumber theory studies properties of numbers, such as2, 1, 22/7, 2, or π.IThere are many subareas of number theory, such as Analyticnumber theory, Theory of Diophantine approximation, etc.IAlgebraic number theory studies numbers that are roots ofpolynomial equations, such as 3, which is a root of x 3 0, 2, which is a root of x 2 2 0,i, which is a root of x 2 1 0.ITranscendental number theory studies numbersthat do not 2satisfy this property, such as π, log 2 or 2 .IDetermining whether a numberis algebraic or transcendental 2can be very hard! Is 2 π transcendental?

Why Study Number Theory?Figure: Messaging apps that (hopefully!) use cryptographic protocolsbased on hard number theoretical problems

Why Study Number Theory?IIt is beautiful.IIt is applicable! Many cryptographic protocols reside ondifficult number theoretical problems.IMany protocols, such as RSA or the Diffie-Hellman Protocol,which are based on “regular” number theory are vulnerable toquantum computer attacks.IAlgebraic number theory comes to the rescue!ILattice-based cryptography is quantum-safe and it usesproperties of numbers that are roots of x n 1 0.ICSIDH is a cryptographic protocol that is quantum-safe and it uses properties of numbers of the form a b m, where m is avery small negative integer and a, b are rational numbers.

BACKGROUND

Rational IntegersIThe numbers . . . , 2, 1, 0, 1, 2, . . . are called (rational)integers. The set of all integers is denoted by Z.ILet a and b be integers. We say that a divides b when b akfor some integer k. We write a b in this case, and a - botherwise.IA number p 2 is a (rational) prime if it is divisible only by 1and p.IThe Fundamental Theorem of Arithmetic. Any integergreater than 1 can be written uniquely (up to reordering) asthe product of primes.ILet a and b be integers. The largest integer g such that g aand g b is called the greatest common divisor of a and b.It is denoted by gcd(a, b).IThe numbers a and b are called coprime if gcd(a, b) 1.

Detour: Rational Numbers and Apéry’s TheoremIIIIIA number is called rational if it is of the form a/b for somerational integers a and b, where a 1. The set of all rationalnumbers is denoted by Q.Determining whether a given number is rational or irrationalcan be very hard!In 1979 the French mathematician Roger Apéry proved thatthe number1111ζ (3) 1 3 3 3 3 . . . 1.2020569031 . . .2345is irrational.It is still unknown whether ζ (5), ζ (7), ζ (9) or ζ (11) areirrational. However, at least one of them is (proved by WadimZudilin in the 90’s).See the article A proof that Euler missed by Alfred van 957/http://www.maths.mq.edu.au/ alf/45.pdf.

Detour: Rational Numbers and Apéry’s TheoremFigure: Roger Apéry (1916 – 1994)

ExerciseIIf a, b are coprime positive integers and ab c 2 for someinteger c, show that a t 2 and b s 2 for some integers t ands.IShow that for any integer x the numbers x and x 2 1 arecoprime.INumbers 0, 1, 22 4, 32 9, . . . are called squares. Show thatthe distance between k 2 and (k 1)2 is equal to 2k 1.When is this distance equal to 1?IUse the previous results to conclude that the equationy 2 x 3 x has no solutions in positive integers x and y .

ALGEBRAIC NUMBER THEORYBEGINS

How Euler “Almost” Discovered Algebraic NTICan the distance between a square and a cube be equal toone?IIn 1700’s, Euler showed that the only square and cube thatdiffer by 1 are 8 and 9.IHomework. Prove that the equation y 2 x 3 1 has onlyone solution in positive integers. Hint: use the fact that(x 3 1) (x 1)(x 2 x 1).IHe also “almost” proved that the only square and cube thatdiffer by 2 are 25 and 27.IIdea: consider the equation y 2 x 3 2 and write it as (y 2)(y 2) x 3 . If y 2 and y 2 are “coprime”, they must be“cubes”. But what does “coprime” even mean in this setting?

Detour: Theorems of Mordell and TijdemanIWe have already seen that the distance between consecutivesquares grows. Same observation applies to cubes.IDoes the distance between consecutive squares and cubesgrow?0, 1, 4, 8, 9, 16, 25, 27, 36, 49, 64, 81, 100, 121, 125, 144, . . .IThe answer is yes. This was proved by the Britishmathematician Loius Mordell in 1960’s.IIn 1976, Robert Tijdeman showed that the number ofconsecutive powers that differ by 1 is finite. Questions aboutlarger distances is still open.IThe solutions (x, y , m, n) to the equation y m x n 1 mustsatisfy x , y , m, n e eee730.

Detour: Theorems of Mordell and TijdemanFigure: Louis Mordell (left) and Robert Tijdeman (right)

Gaussian IntegersIA complex number is a number of the form a bi, where aand b are real numbers and i satisfies the equation i 2 1 0.IA number a bi with a, b rational integers is called aGaussian integer. The set of all Gaussian integers is denotedby Z[i].Exercise. Let a bi, c di be Gaussian integers. Prove thefollowing:I1.2.3.4.IEvery rational integer is a Gaussian integer;(a bi) (c di) is a Gaussian integer;(a bi) (c di) is a Gaussian integer;(a bi)(c di) is a Gaussian integer.Sets where we can add, subtract and multiply are called rings.More formally, A when for α, β A we have α β A andαβ A.

Divisibility and NormILet a, b be Gaussian integers. We say that a divides b whenb ak for some Gaussian integer k. We write a b in thiscase, and a - b otherwise.IThe value a2 b 2 is called the norm of a Gaussian integera bi. It is denoted by N(a bi).IExercise. Prove that 1 2i divides 5 and does not divide 7.IExercise. Let α, β be Gaussian integers. Prove thatN(αβ ) N(α)N(β ).Therefore the norm function is multiplicative.IExercise. Prove that N(α) 0 for all Gaussian integers αand N(α) 0 if and only if α 0.

Units and PrimesIIn a ring A there may exist special numbers that divide 1.Such elements are called units. For example, the only in unitsin Z are 1 and 1.IExercise. Show that if α is a Gaussian unit then N(α) 1.IExercise. Prove that the units of Z[i] are 1, 1, i and i.IA Gaussian integer α is called a Gaussian prime if it is not aunit and any factorization α β γ in Z[i] forces β or γ to be aunit.IExercise. Find Gaussian primes among the integers 2, 3, 5, 7.IJust like rational primes, Gaussian primes have the followingproperty: if γ is a Gaussian prime and γ αβ , then either γ αor γ β . Remember this property: you will need in the nextexercise!

The Remainder Theorem, GCD and the FundamentalTheorem of ArithmeticIThe Remainder Theorem. Let a, b be rational integers,a 0. Then there exist unique integers q and r such thatb aq r , where 0 r a.IThe Remainder Theorem for Gaussian Integers. Let a, bbe Gaussian integers. Then there exist Gaussian integers qand r such that b aq r , where N(r ) N(a).ILet a and b be integers. An integer g such that g a andg b, with N(g ) the largest, is called the greatest commondivisor of a and b. It is denoted by gcd(a, b).IThe Fundamental Theorem of Arithmetic. Up tomultiplication by a unit, any non-zero Gaussian integer can bewritten uniquely (up to reordering) as the product of Gaussianprimes.

THE SUM OF SQUARES

The Sum of SquaresIn this exercise we will investigate which numbers n can be writtenas the sum of two squares. That is, n a2 b 2 for some integers aand b.Exercise. Compute first 10 numbers that are sums of two squares.Step 1. Let m and n be positive integers that are sums of twosquares. Prove that mn is also a sum of two squares. Hint: usethe fact that the norm N is multiplicative.Step 2. Prove that every integer that is a sum of two squares is ofthe form 4k, 4k 1 or 4k 2 for some integer k. Conclude thatevery rational prime p of the form 4k 3 is not a sum of twosquares, and so it is a Gaussian prime.

The Sum of SquaresStep 3. Let p be a rational prime of the form 4k 1 for someinteger k. In this exercise, we will use the fact that there alwaysexists an integer x such that p x 2 1.1. Show that p does not divide neither x i nor x i. Concludethat it is not prime, so p αβ for some Gaussian integersα, β neither of which is a unit.2. Prove that N(α) p, so p is a sum of two squares.Step 4. Show that 2 is a sum of 2 squares. Conclude that everynumber of the form2t p1e1 . . . pkek q12f1 . . . q 2f is a sum of two squares, where pi are primes that are of the form4k 1 and qi are primes of the form 4k 3.

Next TimeIWe will see why most of this theory fails for other rings, suchas Z[ 5].ILearn more about algebraic numbers!

THANK YOU FOR COMING!

Number Theories I Number theory studies properties of numbers, such as 2; 1;22 7, p 2, or p. I There are many subareas of number theory, such as Analytic number theory, Theory of Diophantine approximation, etc. I Algebraic number theory studies numbers that are roots of polyno