Lecture Note
University
Stanford UniversityCourse
Introduction to Mathematical ThinkingPages
6
Academic year
2023
Murphyal
Views
51
Number Theory 1 Number Theory is the branch of mathematics concerned with the study of the integers. Number theorists are interested in properties, relationships, andgeneralizations involving integers. The development of this field has been closelyintertwined with the historical development of whole numbers, integers and rationalnumbers. In many ways, number theory can be viewed as a branch of puremathematics; however, more recently it has become a part of applied mathematics.In fact, number theory is now often defined as a branch of applied mathematics thatspecializes in problems concerning the integers. In addition to its own history, number theory is also considered to be connected tomany other areas within mathematics such as algebraic number theory, arithmeticalgebraic geometry (AARH) and diophantine approximation. In mathematics, the integers and the real numbers are convenient domains fromwhich to illustrate proofs.Those fields are number theory and elementary realanalysis. The principal advantage is that example domains are available to use. Letus begin by considering the integers. The development of the mathematical study of the integers, a branch of mathematicsknown as number theory that is concerned with properties exhibited by integersother than calculation, began around 700 BCE. The study has contributed to one ofthe most significant branches of Pure Mathematics. Number Theory. Number theory is filled with problems that are easy to state but difficult to solve, and many remain unsolved. However, some of the results haveapplications in modern life. Internet security being perhaps the most important. Inmathematics, the interest lies not in their use as a counting device, but in thearithmetical system they create. For any two integers (positive or negative wholenumbers), the result of adding them together, subtracting one from the other, ormultiplying them will always be another integer. Division, however, is more complex. This is where things get particularly intriguing. Ifa pair of integers is divisible by 5, and the second integer is divisible by 15, then thefirst integer is divisible by 5. The integer 3 is the result of dividing 15 by 5. Whendividing two integers, such as 7 and 15, you can only get whole-number results if youare willing to allow fractional results. When division is restricted to the integers, itactually relates to two numbers, a quotient and a remainder. In mathematics, whenyou divide nine by four, you get a quotient of two and a remainder of one. Thenumber nine can be expressed as the product of four, two, and one—a special caseof the first theorem concerning integers. The division theorem. The division theorem states that if a and b are integers with
b greater than 0, then there exist unique integers q and r such that a = qb + r and 0less than or equal to r less than b. The theorem has two parts. There is an existenceproof for sets of integers which exhibit this property. And there is a uniquenessproperty associated with integer pairs, since these pairs are unique in satisfying thegiven property. In order to prove the theorem, we'll take each step one at a time. Wewill first prove the existence of the function, and then we will prove that it is unique. Itis always a good idea to begin a proof by stating the method you will use. Let allnonnegative entities of the form a-kb be considered as integers. Make sure that atleast one of them is less than b. The theorem states that among the integers a-qb,there exists one with r between 0 and b. Let us consider all possible candidates for aminus k b or a minus q b, and prove that among those candidates one satisfies thegiven condition. The k for which the equation is true will be the q that we choose totake with the k. One must first show that there are such integers. For example, consider the equation k equals negative absolute value of k. Next,since b is greater than or equal to 1, a - kb = a + |b| = a + b, which is greater than orequal to a + |a|, which in turn is greater than or equal to 0. By finding the integer kthat gives us a number with this property, we can choose the smallest number of thiskind. Let r be the smallest integer satisfying the equation and let q be the value of kfor which it holds true. Under these conditions, we have r = a - qb. With thisrelationship defined, we can indeed say that a is equal to qb plus r. If it can be shownthat r lies between zero and b, then it will have been proven that the function exists.We complete the proof by showing that r < b. But if we assume that r is greater thanor equal to b, in other words we use proof by contradiction and show that r is lessthan b. If r is greater than or equal to b, then a – q + 1 b = a – qb – b, which equals r– b, which is greater than or equal to 0 by the assumption stated above. Thus, thevalue of a- (q + 1)b is a non-negative integer of the form a-(k-1)b. Thus r is thesmallest such number and a-(q+1)b < a-qb, which is r. This is a contradiction. If r isas small as this, we cannot find a value of r smaller than it. Since there is acontradiction, r cannot be equal to b. This proves that r is less than b. If you are unfamiliar with the proof, then you may find the argument difficult to follow.It is not hard to understand; it just has a complicated structure. The goal is to look atall of the possible candidates to make this statement true. First, we need todemonstrate that a candidate exists. By exhibiting one, we do just that. In order tosatisfy this additional requirement, we pick the one where r is the smallest; it is theminimum value of r which gives us one of these things. Next, we show that itsatisfies this requirement by showing that it is minimal. Elementary algebra is just astep in the argument; it's necessary to take each step before moving on to the next.There are many arguments in mathematics like this one. They involve only basicarithmetic and algebra, but the structure of the argument is intricate enough to proveits point.
Okay, well that proves that something exists. Now we must determine if it is uniqueor not. To prove that a number is unique, we show that if there are tworepresentations of the number—for example, a = qb + r, where 0 < r < b and r isprime and less than b—then r = r prime, and q = q prime. The first part of the divisiontheorem shows that such representations exist. We are now showing that if there aretwo representations of a function, then they are actually the same. The r is the sameand the q is the same. The letters q and r are used to denote quotient andremainder, respectively. We have not yet defined quotients and remainder. Dividing one integer by another. Let's review the equation we have here. Qb + r = qprime b + r prime. Rearranging the equation, we get r prime - r = b(q - q prime). Letus label that equation 1 for later reference. Now we take the absolute value of bothsides of this equation; when we do that, we get r prime minus r equals b times |q – qprime|. Let us label that equation 2 for later reference. If you remember that b ispositive, then when you check absolute values you will find that b remains the same.So -b will be less than -r which will be less than or equal to 0, which is less than orequal to r prime, which is less than b. Thus, b is less than r prime minus r, which isless than b. If r prime minus r is between negative b and plus b, then the absolutevalue of r prime minus r is less than or equal to b. Thus, by 2b times the absolutevalue of q minus q prime is less than b. We can divide the absolute value of q-qprime by b to give us, q-q prime is less than 1. But all of the values here are integers,and in order to have a pair of integers with an absolute value difference less thanone, their absolute value must be zero. This means that if q equals q i, then r equals
r i , and equation one proves the uniqueness of r. And we have proven the divisiontheorem. The focus of this section is the proof that the division property holds for all pairs ofintegers. The skill of mathematical proof is developed through the practice of provingsimple results. Once mathematicians gain confidence in the method of proof, theyare able to accept results that are not at all obvious. One example of an unexpectedresult was in the late 19th century, when mathematician David Hilbert described ahypothetical hotel with an unusual property. Hilbert's Hotel, a hypothetical hotel withan infinite number of rooms, has come to be known as the ultimate hotel. Like mosthotels, the rooms at this hotel are numbered using natural numbers—one, two, threeand so on. All the hotel's rooms are occupied on one particular evening when anunexpected guest arrives. "I'm sorry," says the receptionist, "but all our rooms arefilled." You will have to travel elsewhere. The mathematician thinks for a moment before offering a solution. He says, "There isa way for you to give me a room without having to reject any of your existing guests."The clerk is reluctant to make such a change, but asks the mathematician to explainhow it might be done. The mathematician proposes a solution. Each guest movesinto the room number that is one more than his or her current room number, so theguest in room 1 moves into room 2, the guest in room 2 moves into room 3, and soon through the hotel. The occupants of room n usually moved into room n + 1. Whenthat was full, room 1 became vacant. You put me in that room. The clerk considers
the problem for a moment, then acknowledges the solution. A hotel canaccommodate an additional guest in a completely full hotel without rejecting anyguests if the new person shares a room with someone who is already staying there.With his logic, the mathematician persuades the innkeeper to give him a room for thenight. The Hilbert hotel argument rests on the idea that a hotel with infinitely many roomscan exist. In fact, in order to illustrate one of the properties of infinity, Hilbert devisedthe following story. The importance of understanding infinity is that it allows one todeduce calculus, which is the foundation of modern science and engineering. Afteryou've understood Hilbert's solution, consider the following variants. In the firstvariant of the Hilbert's Hotel scenario, all the rooms in the hotel were full when twoadditional guests arrived. How can they be accommodated in separate rooms,without anyone being asked to leave? A second variant: The clerk is again facedwith a challenge. The hotel has no rooms available, but an infinite tour group arrives,each member wearing a badge that says, "Hello, I am n," for each natural number nequals 1, 2, 3, etc. Given that there is no room for any guest besides these infinitemembers of the tour group and that it would be unacceptable to eject any guest fromtheir room even temporarily, can the clerk find a way to give all of these new guestsa room to themselves without having to eject any existing guests? In the example of Hilbert's Hotel, we can see the importance of strict proof.Verification is a mathematical tool used to check the validity of an already knownresult, such as the division theorem. When used to verify obvious results, it mayseem frivolous. When applied to an issue we are not familiar with, however—such asquestions involving infinity—a rigorous proof is the only thing we can rely on. Now, we shall return to the division theorem. The division theorem in this formapplies only to division by a positive integer b. So, the general division theorem letsus assume that a and b are integers with b ≠ 0. In particular, there exist uniqueintegers q and r, such that a = qb + r and 0 < r < |b|. The general division theorem,like the previous division theorem we proved, is based on the principle of divisibility.We require only that b be non-zero, not strictly positive. Next, we will find the absolute value of b. The proof is fairly straightforward from theprevious result. Thus, if b is an integer greater than 0, then the previous theoremshows that there are unique integers q and r such that b = qr. The equation a=qprime times the absolute value of b + r prime and 0 less than or equal to r prime, lessthan absolute value of b is possible. Now we can make the substitutions q = -q prime, and r = r prime. The absolute valueof b, in this case a negative b, is the difference between qb and r. The result is that ais equal to qb + r, where 0 is less than or equal to r. This theorem simply follows from the previous results. According to the GeneralDivision Theorem, we can officially give names to the two numbers q and r. We will
call q the quotient of a divided by b. And r is called the remainder. Thus we've comefull circle, returning to the concept taught in elementary school about dividingnumbers and the existence of quotients, remainders and so on.
Exploring Number Theory: Study of Integers
Please or to post comments