Introduction to Number Theory Lecture 1 | Math 115

[00:00:00]this lecture is part of a course on elementary number theory more precisely it's the berkeley course math 115 introduction to the introduction to number theory what it will cover is things like primes congruences quadratic forms quadratic reciprocity and derickley's theorem um the course will be very loosely following the textbook by um niven zuckerman and montgomery on an introduction to the theory of numbers um so um number theory is uh well quite a lot of it is about primes so um you recall that a prime number is a number bigger than one that's only divisible by one and itself and the first few primes look like this we can ask some basic questions about prime numbers so so the first question is how do you find prime numbers um and one way is to use the sieve of eratosthenes um where what you do is you you write out all numbers one two three four five six seven eight nine ten eleven song twenty thirty forty and we keep going and you cross off all the ones that aren't prime um well first of all zero and one don't count because 0 is 0 and 1 is a unit and the first number you haven't crossed out is 2 so we write down 2 as a prime and we then cross off all the multiples of 2.

[00:01:39]um because these are can't be prime and the first one number not on this list is three so three is our next prime and we now cross of all multiples of three so again 3 6 9 12 13 14 15 18.

[00:01:59]so we cross them off like this and um someone missed out a few it should be on that one and next we look at the first number we haven't crossed out and this number is now five so five is our next primary cross of all multiples of five which is easy because those are just those ones there and then we get to seven which is the first number not crossed out and we cross off all multiples of seven and actually all of these have already been crossed out except for and that one there and we can actually stop now because um um any bigger prime is um has a square bigger than 49 so it it can't be the smallest prime divisible by a number so what we've done is we've crossed off all numbers um less than 50 that are not divisible by 2 3 5 and 7 where these are the primes less than the square root of 50 and if we look and see what numbers we've got left we've got 11 13 17 19 and 23 29 31 37 41 43 47 and if you're doing number three you very soon learn all the primes up to about a hundred um so the next question is how many primes are there well if we look at this table primes seem to be fairly common um and there's no sign of them suddenly stopping and so this suggests that the number of primes should actually be infinite and this is the first theorem of number theory due to euclid number of primes is infinite well actually euclid didn't say the number of primes is infinite because the greeks didn't really like the concept of infinity what euclid actually said is something equivalent he said if you take any finite set of primes p1 up to pn you can find another prime not in this set and what he did was he took the product p1 times p2 and sum up to times pn and you add one to it and what we do is we take a prime factor p n plus 1 of this and we notice the prime factor p n plus 1 can't be any of these primes p1 up to pn because if it if it was um p1 up to pn then um it would divide this number here and it will also divide this number here so it would have to divide one so pn plus one is a new prime so let's just see how this works we start off with all the primes we can think of which is absolutely no primes at all because we haven't yet started yet so we take the product of all the primes we thought of which is actually one because this is the product of no primes and then we add 1 to this and we get our first prime which is 2. you notice that if you take the product of an empty set of numbers you get 1 for the same reason if you take the sum of an empty set of numbers you just get 0. so this is our first prime and now we we take the product of all the primes we thought of so far which is just two and we add one to this and we get three and then we take the product of all the primes we thought of and add one to this and we get seven and that's prime so we now take the product of all the primes we thought of and add 1 to this and this gives us 43 and now we take 2 times 3 times 7 times 43 and add 1 to this and this time it's not a prime it's it's um um 1807 and this factors as 13 times 139 so our next new prime is actually 13.

[00:06:17]um so it seems to be a common misunderstanding that that if you take the product of all the primes you thought of and add one then you you get another prime but this isn't actually true i mean it breaks down for the first time here um so so this shows there are infinitely many primes um the next question is um how to find um large primes so um there's a sort of game in play by number theorists where they sort of compete to see who can find the biggest prime um so how can you do this well one good way is is them to look at things called mercena primes these are named after mercena who who is the first person to discuss them these are prime to the form two to the n minus one so let's have a look at a few of them where we have two to the um two minus one which is three and we can two to the three minus one which is uh seven or two to the four minus one well this is 15 and it's not prime which is it's three times five um well you notice the problem here is is that four isn't a prime because um two to the a b minus one is divisible by two to the a minus one this is two to the a minus one times two to the a b minus a plus um various things up to plus one so if we if we want two to the n minus one to be prime we should take n to be a prime so we can speed it up by by just looking at two to the primes minus one so we have two to the five minus one which is thirty-one and two to the seven minus one is um 127 and this seems to be rather good way of generating primes because you notice you know whenever we take a prime and take two to the p minus one um we always seem to get a prime um well this doesn't actually quite work because if we go to 2 to 11 minus 1 this is actually equal um to 2047 which is just uh 23 times 199 so this doesn't always work however it's it's still a reasonably good way to generate prime so 2 to the mic p minus 1 is quite often prime um we have an open problem are there infinitely many mercenar primes um so no one really knows although the answer is probably yes for a reason i'll discuss later so people have used computers to find large numbers of mercenar primes in fact there are very good tests to see if a very large number is a mercenary prime and you can actually test numbers with millions of digits to see if they're mercen primes in fact most of the time the largest known prime is actually in the send prime because they they're particularly easy to and so another famous sort of primer fermat primes well if we're going to look at primes the form 2 to the n minus 1 we should also look at primes of the form 2 to the n plus 1.

[00:09:48]so let's look at the first few cases just to see what's going on with 2 to the 0 plus 1 is 2 2 to the 1 plus 1 is 3 2 to the 2 plus 1 is 5 2 to the 3 plus one is well um two to the three plus one is now nine now that's not prime it's three times three and two to the four plus one is um seventeen that's prime two to the five plus 1 is no good because that's um 33 and um if you um think about it a bit you notice that if if if we've got a num if if if we've got a number two to the power of a b with a odd um and we add one to this and this is divisible by two to the a plus one so um the exponent can't be divisible by any odd numbers if we want it to be a prime set so we should only take n to be power of 2 in other words we should look at numbers the form 2 to the 2 to the m plus 1. so so let's restart we have 2 to the 2 to the 0 plus 1 is is now 3.

[00:11:05]so 2 to the 2 to the 1 plus 1 is 5.

[00:11:11]2 to the 2 to the 2 plus 1 is 17 2 to the 2 to the 3 plus 1 is 257 2 to the 2 to the 4 plus 1 is 6 5 5 3 7 as you know if you're a computer scientist um and all of these numbers are prime um these are called the fermat primes so two doesn't really count as a female prime because zero is kind of a bit of a special case um and fermat sort of suggested that in fact maybe two to the two to the m plus one was always prime um but in fact this is false because two to the two to the five plus one turns out to be divisible by 641.

[00:11:58]um actually a bit of a historical puzzle about why firma didn't notice this because he was perfectly capable of checking that two to the two to five was divisible by 641 and the consensus seems to me that he probably did check but just made some sort of numerical error and and um got it wrong um so fermat primes turn up in a rather um unexpected place um there's a famous problem um about which regular polygons can you construct using a ruler and compass and it's easy to figure out how to construct polygons of side 4 and 8 and 16 and sun because you can bisect angles and the greeks figured out how you can construct polygons of sides 3 or 5 or 15 and what gauss discovered is that if a number is a firma prime then you can construct a polygon with that number of sides using ruler and compass which is really rather bizarre and in fact it turns out the only numbers you can construct with the ruler and compass are the ones that are products of distinct firm are primes times a power of two so we have an almost complete list of polygons you can construct by lure and compass except that nobody knows whether there are any further firmer primes so people have checked the next 30 or so cases and there and haven't found any further fermat primes um and it's a completely open question about whether there are infinite number of these or not um well so firm has suggested this might be an easy way to find primes but it doesn't quite work so we can ask um is there any easy way to generate large primes and this is a sort of open question i mean it depends a bit on what we mean by an easy way to generate large primes since we have some reasonably fast methods that computers can use to generate large primes but it'd be really nice if we could find say a polynomial f of n such that f of n is always prime so are there any polynomials f such that f of n is always prime well the answer is yes it's quite easy to generate these we can just write f of n equals three for all n it's the constant polynomial so what we really want is f to be non-constant otherwise we've got a rather trivial answer so we want to find a non-constant polynomial such that f of n is is prime for all positive integers and you can get pretty close to this suppose i take the polynomial n squared plus n plus 41 just found by euler and if you try n equals 0 1 2 3 well you'll probably find this is always prime for as long as your patience holds up in fact it's prime for all numbers n up to 40. however it's not prime for n equals 41 and it's it's obviously not prime for n equals 41 because if you put n equals 41 here this is divisible by 41 of course um so so we can get polynomials that try very hard to be prime but but they don't quite make it so you can ask is is there any polynomial such that f of n is always prime such that um f isn't constant and the answer is no and we can see this as follows let's look at f of n equals n to the um k plus so something times n to the k plus something times n plus some constant term and now suppose this constant term is bigger than one let's call it k well then if we put n equals k this will be f of n will be divisible by k because all the or all the terms are divisible by k so it's not prime so if if the constant term of f is not one it is bigger than one then it can't always be prime so what happens if the constant term is equal to one well we can just change f of n to f of n plus k for some number k such that the constant term is not equal to one and repeat our arguments there's no polynomial that always generates primes apart from the trivial case of a polynomial that's constant and no one has ever found anything better i mean that there just doesn't seem to be a really easy simple way that that will always generate primes um well we've shown there are infinite number of primes but we can ask another question and instead of asking how many primes there are we can ask how many primes are there less than or equal to x where x is some number now the number of primes less than or equal to x is often denoted by pi of x and um you've got to be a little bit careful not to muddle this up with the number 3.141 and so on so pi is the greek letter for p which stands for prime um and it's not very easy to find an exact formula for pi of x i mean you can see primes are a little bit chaotic and you it would be a bit unreasonable to expect an explicit formula for them although rather surprisingly the we've seen a moment there is one but we can ask what is pi of x roughly equal to so we can ask roughly how many primes are there and gauss came up with a pretty good answer to this um one version of gauss's suggestion is that pi of x should be approximately x over log of x and just warn everybody since this is a mathematics course log means log to base e not to base 10 there's absolutely no point in taking logs to base 10. so in mathematics log always means log to base e um and this was um finally proved by hadamard and de la pusan in about 1896 and this is you know this at the time was proved this is probably one of the deepest and most difficult themes proved in the 19th century um so informally this means suppose you take all the numbers up to x it means about one over log x of them a prime so we can think of this as saying the chance of n being prime is about 1 over log of n and you've got to be a little bit careful about what you mean by this because the chance of n being prime isn't one over log of n it's either the chance of n being prime is one if n is prime and at zero if n is not prime so it's it's kind of a little bit meaningless to say what is the chance of n being prime but but whatever um it's sort of reasonably obvious what's meant um so let's have an application of this let's ask is the number of mercen primes infinite so you remember a mercen prime is a number of the form two to the n minus one so what's the chance of 2 to the n minus 1 being prime well it's about 1 over log of 2 to the n minus 1 and this is about some constant involving log of 2 over over n so in order to find out the total number of mercenary primes what we could do is we could just take the sum over or n of the chance of two to the n minus one being prime so we're taking the sum over n of k over n and this will hopefully give us a rough estimate of the number of mercen primes well um this is just equal to k times one plus a half plus a third and so on and this is the famous harmonic series which you remember from calculus is infinite so this sort of suggests the number of mercen primes is infinite well fine but there's a bit of a problem with this argument first of all it assumes these numbers are random and they're obviously not random because they're two to the n minus one um there's another very obvious problem suppose we try and ask how many numbers of the form two to the n minus two are prime well we can apply exactly the same argument and it suggests there should be an infinite number of primes in the form two to the n minus two and this is just totally stupid because two to the n minus two is obviously divisible by two so it's almost never prime unless n is two or something um so these probability arguments are a useful guideline to what is true or not but you should be always be really cautious when using them because they can give horribly misleading answers um a rule of thumb is that in number theory um um arguments using these sort of probabilistic arguments are generally god is worth almost nothing because they're very easy to to do but they're they're extremely hard to make rigorous and they sometimes give the wrong answer and they sometimes give um extremely ambiguous answers suppose for example we try to count how many firmer primes are there well what we should do is we should take the sum over um 1 over log of 2 to the 2 to the n plus 1.

[00:22:30]well the logarithm of this is going to be some constant times 1 over 2 to the n if we ignore the plus one and this is going to be finite so this suggests there should be a finite number of firm primes and indeed we uh numerical evidence sort of suggests that maybe the ones ferment you about the only ones they have but there's another argument you could say you could ask how many primes are there of the form two to the n plus one well here we would take sum over one over log of two to the n plus one and this is going to be about k times 1 over n and this is going to be infinite so this argument suggests there should be an infinite number of primes in the form two to the n plus one um all of which um have to be have to be firmer prime so we've got two probabilistic arguments one of which says there should be an infinite number of firmer primes and one which says there should be a finite number and which is correct i have no idea and nobody else really has any idea either um um so um riemann actually um found a rather astonishing explicit formula for the number of primes what you do is you define the logarithmic integral of x to be the integral from 0 to x of 1 over log of x dx well actually there's a little bit of a problem with this integral because if x is equal to 1 um um the integral actually becomes infinite and sort of diverges so um when i say it's equal to that it's not actually equal to that you need to fiddle around with this little bit but i'm not going to worry about this the logarithmic integral is going to be approx given by something slightly modified version of this and riemann found the following astonishing explicit formula for primes well first of all he wasn't counting primes he was counting prime powers so riemann discovered that p to the n should count as one over n of a prime so in some sense four is really half is sort of 50 of a prime and eight is one third of a prime and um in some sense and he found that it's instead of counting primes it's easier to count prime powers in this funny sense so pi prime of x is the number of prime powers less than x where where and p to the n counts as one over n of a prime power so so um if um and and he found a completely explicit formula for for this number here so this is just equal to the logarithmic integral of x um minus sum over some funny numbers rho of the logarithmic integral of x um to the rho um so um um here the sum is over all these numbers rho which are some so-called zeros of the zeta function which i'll explain in a moment and now um this is a really astonishing formula because these are all you know nice continuous um real valued functions however this function here is certainly not continuous because it sort of jumps by one whenever x goes beyond a prime power so we've got this absolutely astonishing form of a discontinuous function being given as a natural sum of all these nice continuous functions and here the logarithmic integral of x turns out to be approximately x over log of x so this explains why why the number of primes less than x is approximately given by by this number here so what are these mysterious numbers rho um well um the numbers wrote that zeros of the zeta function which is given by this number here 1 over 1 to the s plus 1 over 2 to the s plus 1 over 3 to the s and so on and so for example zeta of 2 is equal to 1 over 1 squared plus 1 over 2 squared plus 1 over 3 squared this is a rather difficult sum to evaluate euler became famous by discovering it was actually equal to pi squared over 6.

[00:27:15]and the numbers rho are the numbers rho such that the zeta of rho is equal to zero well there's a bit of a problem here because um the known zeros of rho tend to be complex numbers and they're complex numbers for which the this series doesn't actually converge so we need to do quite a lot of work in order to make sense of the riemann zeta function for other complex numbers um and um um then try and work out where the zeros of the riemann zeta function are at this point we come to the probably the most one of the most famous open problems in mathematics which is the riemann hypothesis which just says the real part of any zero row is at most a half um so uh um there's a million dollar prize for solving this if you ever managed to solve it in fact solving this riemann hypothesis isn't the hard part the really hard problem um is not in solving the riemann hypothesis but trying to get someone else to read your solution when you've solved it because um you know crackpots produce several proofs the riemann hypothesis every month so if you show a proof of the riemann hypothesis to a mathematician the mathematician will just throw it in the bin on red because all mathematicians are sick of getting sent proofs of this anyway riemann riemann's work gives an astonishingly accurate formula for the number of primes less than a number for example the number of primes less than a hundred million is exactly equal to five seven six one four five five um riemann's estimate um not counting the zeros over row um turns out to be five seven six one five two two as as you can see it's sort of already accurate to four significant figures so this is using um l i of x as an approximation not to pi of x but to the number of prime powers you have to subtract out the squares and cubes and so on with primes and if you do that you get this astonishingly accurate formula for number of numbers less than um um so one of the basic facts about primes we're going to prove is the fundamental theorem for arithmetic so the fundamental theorem of arithmetic says that every integer greater than or equal to naught so greater than or equal to one is a product of primes in a unique way that means unique up to order um and there's a very nice formula for this involving the riemann zeta function which is um one over one to the s plus one over two to the s plus one over three to the s and so on and euler discovered that you could write this as follows it's the product of 1 over 1 minus 2 to the minus s times 1 over 1 minus 3 to the minus s times 1 over 1 minus 5 to the minus s and so on where this is a product over all primes and this looks rather astonishing if you see it for the first time but it's actually quite easy to prove if you if you just write each of these factors as a geometric series we get 1 over 1 1 over 1 plus 1 over 2 to the s plus 1 over um four to the s plus one over eight the s and so on times one plus one over three to the s plus one over nine to the s and so on and now if you multiply out this product of an infinite number of factors um each of the terms you get by taking um one term from each of these factors and multiplying them together so for instance if we take this term this term and this term and one's everywhere else we get one over two to the s times one over three to the s squared times one over five to the s which is equal to one over two times three squared times 5 which corresponds to 1 over 90.

[00:31:50]and now here we have a term 1 over 90 to the s so you see every term in this series here comes from a unique term in this infinite product because every integer can be written as a product of prime powers in the unique way so this is euler's version of the fundamental theorem of arithmetic it's this amazing factorization for the riemann zeta function euler also used this to give another proof of euclid's theorem that they're infinitely many primes what you do is you just take s equals one and now you notice this term here is infinite because it's just one over one plus one and a half plus a third and some which is infinite so it means this product over primes must be also also must be infinite but if the number of primes were finite then this would just be a finite non-zero product and so it couldn't be infinite so the number of primes has to be infinite because um because this series here diverges for s equals one so this is a completely bizarre proof you're saying the number of primes is infinite because the harmonic series um diverges um so um next thing you can discuss in um number theory diphantine equations so a diaphantine equations are made of of alexandria and not very much is known about him i mean he lived a few centuries um in the common era but no one even knows his exact the exact date when he lives in fact pretty much all that anybody knows about him is he wrote a book about diaphantine equations so diaphantine equations are equations where you want solutions in integers actually diaphantus himself didn't discuss solutions in integers he mostly discussed solutions and rational numbers but um whatever so let's have some examples um famous example that everyone knows about is pythagoras equation x squared plus y squared equals z squared um and this is solutions in integers that everyone knows we all know 3 squared plus 4 squared equals 5 squared or 5 squared plus 12 squared equals 13 squared and so on another example you might have linear equations so can you solve 27x plus 11y equals 1.

[00:34:43]and we'll see how to fairly soon how to solve all linear diphantine equations using euclid's algorithm so this particular case we can for example take x equals minus 2 y equals 5 gives a simple solution another example is the equation 2x squared equals y squared and this is an obvious solution x equals y equals zero um but it does no other solutions so this is like asking is y over x equal to the square root of two and in other words is the square root of two rational and the answer is it can't be in the w when the greeks discovered this they got a bit upset about it because there was a feeling that all rash numbers should be rational and having irrational numbers was a little bit disturbing so it's quite easy to prove there are no non-zero solutions of this for instance this equation implies y must be equal to even because if it were odd then this side would be odd and this side would be even so y is even and you can then divide out a factor of 2 from both sides and you then find x squared is equal to 2y squared now you've found a smaller solution of 2x squared equals y squared so um given any nonzero solution you can find a small and nonzero solution so there can't be any nonzero solutions another particularly notorious example is x to the n plus y to the n equals z to the n so this is firm as last theorem and we want n to be at least three and we want x y and z to be greater than zero because if you allow x to be zero for example it has some rather obvious trivial solutions and for many years this was the most famous open problem in mathematics and um there are thousands of incorrect solutions of it and so it was finally solved by andrew wiles in the 1990s um um there are also some variations of um this for example we can ask um what about x the 4 plus y to the 4 plus c to the 4 equals t to the 4. can we find a non-zero solution of this well you can but it's really rather difficult so one solution be 206 1 5 6 7 three to the four plus two six sorry equals two six eight two four four zero to the four plus one five three six five six three nine to the four plus one eight seven nine six seven six o to the four obviously people had to use a computer to find this because it'd be a bit difficult to find by hand using trial and error so it as you see from this it can be really hard to tell whether or not a diaphantine equation has a solution or not sometimes there may be no solutions but it's really difficult to prove sometimes they might be solutions but they're really difficult to find because they're rather big so you can ask the following problem this is hilbert's tenth problem is there an algorithm to solve all diaphantine equations um what this means is given a different time equation f x y z and so on um the algorithm should either give you the output that tell you there are no solutions or it should find a solution now having an algorithm to find a solution if there is a solution is actually really easy all you have to do is to check all possible solutions in order until you find a solution the problem is that if the differential equation has no solutions your algorithm might just go on forever without ever stopping so we want the algorithm to actually stop and tell you there are no solutions if there are no solutions and the answer is that this is not possible in general um it it it doesn't mean it's impossible for any particular diaphantine equation um i mean for particular diaphantine equations we can quite often solve this um and the problem is there's no algorithm that will work for all diaphantine equations so so this was originally shown by robinson um davies and putnam and um the final step was um done by um mattier cevich actually he he he did the last step in this and showing that this was impossible when he was about 22 or 23 or something so so pretty young um so uh another example of a differential equation is variations of um pell's equation so we can ask can you solve the equation x squared plus equals d y squared plus or minus 1.

[00:40:24]so let me give some examples of this so we can ask can you solve x squared equals 94 y squared plus one well it turns out the smallest solution is x equals two one four three two nine five and y equals two two one o six four so again um this is not something that would be easy to do by trial and error but as we'll see later on in the course that there's a sort of reasonably efficient way of finding these solutions using continued fractions this is another historical example of this problem which is done by duttone who um had a some puzzle box that these are actually puzzles that i think he gave in a newspaper column or something so here he has a puzzle about the battle of hastings where he says well the men of harold formed 61 squares all of the same size and when harold joined and they all formed one big square so what you're trying to do is to solve the equation um x squared equals 61y squared plus one oops let me i'm gonna fight down a bit so you can see that and again the smallest solution of this turns out to be ridiculously big so here's dudney's solution um if you look here he has the total number of men is this rather ridiculously large number here so even harmless looking diaphantine equations with rather small coefficients can have absurdly large smallest solutions another variation of this is the equation x cubed plus y cubed equals z cubed plus t cubed and obviously there are trivial solutions because you can take x equals z and y equals t and so on but we would like a non-trivial solution and um the smallest non-trivial solution would be 1729 is equal to 12 cubed plus 1 cubed which is equal to 10 cubed plus 9 cubed um there's a famous legend about this number that um the mathematician hardy um claimed that he was once visiting romanogen when he was ill and mentioned to a manager that his taxi cab number was 1729 and said this is a very boring number and ramanujan said no it's a very interesting number it's the smallest number that's the sum of two cubes in two different ways and while this is a charming story and i'm rather skeptical of it because even among mathematicians you don't start conversations by telling the other person your taxi cab number um i suspect what might have happened is that harding knew perfectly well that this number was the sum of two cubes in two different ways and was just giving it to ramanujan um in a sort of attempt to cheer him up because ramanujan was feeling a bit miserable or something like that but anyway this this is now notorious or famous or something as being ramanujan's taxicab number um so the next part of the lecture i'll record separately because this is getting a little bit long and i'll be continuing um examples of some problems in number theory