4 Number Theory I: Prime Numbers - University of Pennsylvania

1 Last edited February 11, 20164 Number Theory I: Prime NumbersNumber Theory is the mathematical study of the natural Numbers , the positivewhole Numbers such as 2, 17, and 123. Despite their ubiquity and apparent sim-plicity, the natural integers are chock-full of beautiful ideas and open primary focus of Number Theory is the study of Prime Numbers , which can beviewed as the elementary building blocks of all Number TheoryThe natural Numbers are those basic abstraction of quantity we first learn aboutas children; in particular they are the positive whole Numbers :N={1,2,3,..}.(36)Although simple in some sense, the patterns and relationships that appearamong these Numbers have intrigued and challenged generations of the mathe-maticians. Despite hundreds of years of progress, there is still many areas weknow very little about. We begin by very briefly considering three kinds ofproblems that arise in Number Theory , and which highlight di erent aspects ofthe Remainders of Large NumbersSince elementary school, readers of these notes have known how to divide twointegers and calculate whole Numbers plus remainders.

2 For example, we candivide 17 by 3 and obtain 5, remainder 2. If we useRto indicate the remainderafter division, we have:83/9=9,R123/16 = 1,R7107/27 = 3, of these calculations can be made on a simple four-function calculator with-out much the Numbers we are dividing become slightly larger, similar calcula-tions can be made with slightly more e ort. For example, we have:832/9 = 765,R4232/16 = 33,R11072/27 = 424, examples too can be calculated using a simple four-function calculator. Ifwe were so inclined, we could also solve these division problems by hand usinglong edited February 11, 2016 However, when the Number become significantly larger, conventional meth-ods can no longer help us. Consider for example the following problems:832019313/9=?,R2231323122/16 = ?,R11078723039/27 = ?, , even the most most powerful calculators and computers will have signif-icant trouble computing the correct answers. You may have noticed that halfof each question was left blank, where the correct whole Number is indicated bya ?

3 , but the remainders in each question are still filled in. The correct wholenumber itself is quite long, well over a million digits long, and even could easilycompute the Number , writing it down would take a very long time. Is it some-how possible, however, to only compute the remainder, without also knowingthe whole Number to its left?Modular arithmetic, an area of Number the-ory we will allow us to do exactly this, and hence divide gigantic Numbers bysmaller ones and exactly determine the remainder, without even knowing thewhole Number ability to perform these calculations results in our ability to encryptdata and communicate secularly over the internet. Every time you order some-thing online, your computer uses modular arithmetic to calculate remaindersof gigantic Numbers . We will discuss how this works towards the end of Integer Solutions of Pythagorean-like EquationsConsider the setNand the following equations:2+3 = 54 + 7 = 118 + 9 = each equation, we have two elements ofNthat are combined through additionto form another element ofN.

4 The reader will likely find nothing surprising inany of these equations by this point, we have been adding together wholenumbers to make other whole Numbers for many, many , consider the set of squares,S={12,22,32,42,..}, and the followingsimple equations:32+42=5252+ 122= 132202+ 212= each equation here, we have two elements ofSthat are combined to formanother element ofS. To some, these Numbers may rings bells reminding of usthe Pythagorean theorem. This theorem states that if two numbersaandbare26last edited February 11, 2016side lengths of a right triangle (a triangle one of whose internal angles is 90 ),and ifcis the length the triangle s hypotenuse, thena2+b2=c2. For example,consider the triangle illustrated below. Its two sides have lengths 1 and 2, and itshypotenuse has lengthp5. These satisfy the equation 12+22=p52= 5, whichthe reader can readily verify. In this particular situation not all three sides areintegers, or even rational Numbers . However, it is possible to find some righttriangles such that all three sides (including the hypotenuse) are integers.

5 Forexample, consider the triangle with side lengths 3 and 4 and hypotenuse length5, illustrated below. Here is an example in which all three sides (including thehypotenuse) are whole Numbers . Although it might not be clear at this point,we can in fact make infinitely many triangles with integer length any case, we point out that the Pythagorean theorem describes all righttriangles, not only those with integer sides. At this point, however, we restrictourselves to sets of natural Numbers {a, b, c}that satisfy the equationa2+b2=c2. It turns out that there are infinitely many such sets, though we will notprove this , consider the set of cubes,C={13,23,33,43,..}. Any attempt tofind two elements ofCthat can be added together to create a third element ofCwill end in failure. Although we were able to find numbersa,b, andc, such thata2+b2=c2, there are no sets of natural Numbers {a, b, c}so thata3+b3= fact, there are also sets such thata4+b4=c4. More generally, there areno sets of natural Numbers {a, b, c}such thatan+bn=cnifnis an integergreater than 2.

6 This result is commonly known as Fermat s Last de Fermat was a tremendous 17th century French mathematician whoproved many deep results in many area of mathematics, including geometry ,algebra, analysis, probability, and Number Theory . Fermat wrote this theorem in the margin of a book he was reading (a book calledArithmetica,writtenby the Greek mathematician Diophantus) and indicated that the margin wastoo small for him to record in it a proof of this beautiful theorem. Nowhereelse did Fermat describe his proof of the theorem, and hundreds of years wentby before anyone else was able to finally establish this result. Andrew Wiles,a Brittish mathematician, finally did so in the early 1990 s. Whether Fermathimself actually had a simple proof of the simple-sounding theorem is unknown,27last edited February 11, 2016though it is certain that he could not have discovered the proof of Wiles, whichrequired mathematical tools which took hundreds more years to Perfect NumbersEvery natural Number has a set of divisors, the Numbers which can evenly dividethe Number .

7 For example, the natural Numbers 1,2,3,4,6, and 12 all divide thenumber 12 itself. The Number 33 has fewer divisors, which are 1, 3, 11, and33 itself. For each numbern, let s consider the setDnof positive integers thatdividenand which are also smaller thann. Here are several examples:D4={1,2}D5={1}D6={1,2,3}D7={1}D 26={1,2,13}D27={1,3,9}D28={1,2,4,7,14}Tw o simple observations can be made. First, notice that|Dn|, the Number ofelements inDndoes not depend in a simple way onn. However, notice thatwhennis a Prime Number , thenDn={1}, since it is the only positive integersmaller thannwhich eachnwe can also consider the sum of all elements a primenumber, than this sum is 1, because that is the only Number inDn. For othernumbers, though, this Number can be bigger. Notice that for some particularnumbers, this Number is equal ton. For example,D6={1,2,3}, and if we sumthe Numbers inD6, we obtain 1 + 2 + 3 = 6. Likewise, whenn= 28 we have1 + 2 + 4 + 7 + 14 = 28. Such Numbers , for which the sum of the divisors equalsthe Number itself, are calledperfect Numbers .

8 Although we are familiar withseveral examples of perfect Numbers (for example 6, 28, 496, and 8128), it is notknown whether there are an infinite Number of these, or whether any of themare sorts of questions are somewhat abstract, but they highlight some ofthe complications that can arise in studying relatively simple objects such aswhole Numbers . Number Theory is filled with questions of patterns and structurein whole Numbers . One of the most important subsets of the natural numbersare the Prime Numbers , to which we now turn our Prime BasicsPrime Numbers can be thought of as the building blocks of all natural Numbers ,and we now take a look at what they are and some of their properties. We beginwith a edited February 11, 2016 Definition natural Number larger than 1 is calledprimeif it can beevenly divided only by 1 and itself; other natural Numbers greater than 1 give a intuitive description, we might think of a group of objects and askwhether we can divide the group of objects into several small groups, each withan equal Number of objects.

9 Depending on the Number of objects in the originalgroup, we might be able to divide the group in several ways, or in no ways atall. If we have 20 people in a room, we might break them into 4 groups of 5, orperhaps 2 groups of 10. If there are 25 people in the room, then the only way wecan evenly divide them is by separating them into five groups of 5 people some groups, though, there is no way at all divide them into separate example, if there are 13 people in the room, there is no way to evenly dividethem, except if want to divide them into 13 groups with one person Numbers which cannot be broken up into products of smaller naturalnumbers (greater than 1) are called Prime . In some sense, the Prime Numbers 2,3, 5, etc. are the atoms (taken in the classical sense, meaning indivisible) thatmake up all natural Numbers , in the way that hydrogen, helium, lithium, etcmake up the matter of our universe. Unlike the periodic table of the elements,however, the list of Prime Numbers goes on of PrimesEuclid of Alexandria was a Greek mathematician who lived several centuriesbefore the common era.

10 Aside from his many contributions to geometry , Euclidalso made important contributions to our understanding of Numbers . In partic-ular, Euclid showed that for any finite numbern, there are more thannprimenumbers. This is equivalent to what we would say, There are infinitely manyprimes . Euclid proved this by showing that if we take any finite set of primenumbers, we can always find another Prime Number that is not in that are infinitely many Prime that there are only a finite numbernprime Numbers . We canthen make a complete list of all them let s call these primesp1,p2,..pn,sothatpiis theith Prime Number , andpnis the last one; for example, the firstseveral Prime Numbers are:p1= 2,p2= 3,p3= 5 (remember that we don tusually count 1 as a Prime Number ). As far we now know, this is a complete listof all Prime Numbers . Euclid showed that for any such list of Prime Numbers ,there is always at least one Prime Number that is not on that list; this showsthat there is no such thing a complete finite list of Prime the numberM=p1 p2 p3.