We are all used to seeing numbers written down, and to drawing some meaning from them. However, a numeral such as 6 and the number that it represents are not one and the same thing. In Roman numerals, for example, we would write the number six as VI, but we realize that this stands for the same number that is written as 6 in modern notation. Both symbolize collections of the kindcorrespondingtosixtallymarks:IIIIII.Weshallfirst spend a little time considering the different ways that we represent and think about numbers.
We sometimes solve number problems almost without realizing it.For example, suppose you are conducting a meeting and you want to ensure that everyone there has a copy of the agenda. You can deal with this by labelling each copy of the handout in turn with the initials of each of those present. As long as you do not run out of copies before completing this process, you will know that you have a sufficient number to go around. You have then solved this problem without resorting to arithmetic and without explicit counting. There are numbers at work for us here all the same and they allow precise comparison of one collection with another, even though the members that make up the collections could have entirely different characters, as is the case here, where one set is a collection of people, while the other consists of pieces of paper.
What numbers allow us to do is to compare the relative size of one set with another.
In the previous scenario you need not bother to count how many people were present as you did not have to know–your problem was to determine whether or not the number of copies of the agenda was at least as great as the number of people, and the value of these numbers was not required. You will, however, need to take a count of the number present when you order lunch forfifteen and certainly, when it comes to totting up the bill for that meal,someone will make use of arithmetic to work out the exact cost,even if the sums are all done on a calculator.
Our modern number system allows us to express numbers in an efficient and uniform manner, which makes it easy to compare one number with another and to perform the arithmetical operations that arise through counting. In the day-to-day world, we employ base ten for all our arithmetic, that is to say we count by tens, and we do that for the accidental reason that we have ten digits on our hands. What makes our number system so effective, however, is not our particular choice of base but rather the use of positionalvalue in number representation, where the value of a numeral depends on its place in the number string. For example,1984 is short for 4 ones plus 8 lots of ten plus 9 hundreds plus 1 thousand.
It is important to understand what we mean when we write numbers in particular ways. In this chapter, we will think about what numbers represent, discover different approaches to counting, meet a very important set of numbers(the primes), and introduce some simple number tricks forfinding them.
Howcountingwassortedout
It is worth taking a few moments to appreciate that there are two distinct stages to the process of building a counting system based on, for instance, tens. Two basic tasks that we impose on children are remembering how to recite the alphabet and learning how to count. These processes are superficially similar but yet have fundamental differences. Our language is based on a 26-letter alphabet and, roughly speaking, each letter corresponds to a sound that we use to speak words. In any case, it is certainly true that the English language has developed so that it can be written using a set of 26 symbols. However, we cannot compile dictionaries unless we assign an order to our alphabet. There is no particularly natural order available and the one that we have settled on and all sing in school, a,b,c,d,...seems very arbitrary indeed. To be sure, the more frequently used letters generally occur in thefirst half of the alphabet, but this is only a rough guide rather than a rule, with the common letters s and t,forexample,sounding off late in the roll call. By contrast, the counting numbers, or natural numbers as they are called,1,2,3,...come to us in that order:for example, the symbol 3 is meant to stand for the number that follows 2 and so has to be listed as its successor.We can, up to a point, make up a fresh name for each successive number. Sooner or later, however, we have to give up and start grouping numbers in batches in order to handle the unending sequence. Grouping by tens represented thefirst stage of developing a sound number system, and this approach has been near universal throughout history and across the globe.
There was, however, much variation in detail. The Roman system favours gathering byfives as much as tens, with special symbols,V and L, forfive and forfifty respectively. The Ancient Greek system was squarely based on grouping by tens. They would use specific letters to stand for numbers, sometimes dashed to tell the reader that the symbol should be read as a number rather than as a letter in some ordinary word. For example,πstood for 80 andγfor 3, so they might writeγπto denote 83. This may look equally as efficient, and indeed much the same as our notation, but it is not. The Greeks still missed the point of the positional system as the value of each of their symbols wasfixed. In particular,γπcould still only represent the same number,3+80, whereas if we switch the order of the digits in 83 we have the different number 38.
In the Hindu-Arabic system, the second stage of number representation was attained. Here the big idea is to make the value of a symbol dependent upon where it occurs in the string. This allows us to express any number with just afixed family of symbols. We have settled on the set of ten numerals 0,1,2,···,9,so the normal number system is described as base ten, but we could build our number system up from a larger or a smaller collection of basic symbols. We can even manage with as few as two numerals,0 and 1 say, which is what is known as the binary system, so often used in computing. It is not the choice of base size, however, that was revolutionary but the idea of using position to convey extra information about the identity of your numbers.
For example, when we write a number like 1905, the value of each digit depends on its place in the number string. Here there are5 units,9 lots of one hundred(which is 10×10), and one lot of one thousand(which is 10×10×10). The use of the zero symbol is important as a placeholder. In the case of 1905, no contribution comes from the 10’s place, but we cannot ignore that and just write195 instead, as that represents an entirely different number.Indeed, each string of digits represents a different number and it is for that reason that huge numbers may be represented by short strings. For instance, we can assign a unique number to every human being on Earth using strings no longer than ten digits and in this way give a personal identifier to every individual belonging to this huge set.
Societies of the past sometimes used different bases for their writing of numbers but that is much less significant than the fact that nearly all of them lacked a true positional system with full use of a zero symbol as a placeholder. In view of how very ancient is the civilization of Babylon, it is remarkable that they among the peoples of the ancient world came closest to a positional system.
They did not, however, fully embrace the use of the not-so-natural number 0 and eschewed using the empty register in thefinal position the way we do to distinguish, for example,830 from 83.
The conceptual hurdle that had to be cleared was the realization that zero was indeed a number. Admittedly, zero is not a positive number but it is a number all the same and until we incorporate it into our number system in a fully consistent manner, we remain handicapped. This crucialfinal step was taken in India in about the 6th century AD. Our number system is called Hindu-Arabic as it was communicated from India to Europe via Arabia.
Living with and without decimals
Adopting a particular base for a number system is a little like placing a particular grid scale on a map. It is not intrinsic to the object but is rather akin to a system of coordinates imposed on top as an instrument of control. Our choice of base is arbitrary in character and the exclusive use of base ten saddles us all with a blinkered view of the set of counting numbers:1,2,3,4,···. Only by lifting the veil can we see numbers face to face for what they truly are. When we mention a particular number, let us say for example forty-nine, all of us have a mental picture of the two numerals 49. This is somewhat unfair to the number in question as we are immediately typecasting forty-nine as(4×10)+9. Since49=(4×12)+1, it may just as easily be thought of that way and,indeed, in base twelve, forty-nine would therefore be written as 41,with the numeral 4 now standing for 4 lots of 12. However, what gives the number forty-nine its character is that it equals the product 7×7, known as the square of 7. This facet of its personality is highlighted in base seven, as then the number forty-nine is represented as 100, the 1 now standing for one lot of7×7.We would be equally entitled to use another base, such as twelve,for our number system:the Mayans used twenty and the Babylonians base sixty. In one way, the number 60 is a good choice for a counting base as 60 has many divisors, being the smallest number divisible by all the numbers from 1 through to 6.A relatively large number such as 60 has the disadvantage,however, that to use it as a base would require us to introduce 60separate symbols to stand for each of the numbers from zero up to fifty-nine.
One number is a factor of another if thefirst number divides into the second a whole number of times. For example,6 is a factor of42=6×7 but 8 is not a factor of 28 as 8 into 28 goes 3 times with a remainder of 4. The property of having many factors is a handy one to have for the base of your number system, which is why twelve may have been a better choice than ten for our number base as 12 has 1,2,3,4,6, and 12 as its list of factors while 10 is divisible only by 1,2,5, and 10.
The effectiveness and sheer familiarity of our number system embues us with a false confidence and with some inhibitions. We feel happier with a single whole number than with an arithmetical expression. For example, most people would rather talk about5969 than 47×127, although the two expressions represent the same thing. Only after‘working out the answer’,5969, do we feel that we‘have’the number and can look it in the eye. There is,however, an element of delusion in this as we have only written the number as a sum of powers of ten. The general shape of the number and other properties can be inferred more from the alternative form where the number is broken down into a product of factors. To be sure, this standard form,5969, does allow direct comparison with other numbers that are expressed in the same way but it does not reveal the full nature of the number. In Chapter 4, you will see one reason why the factorized form of a number can be much more precious than its base ten representation, which can keep vital factors hidden.
One advantage that the ancients did have over us is that they were not mentally trapped within a decimal-style mindset. When it came to number patterns, it was natural for them to think in terms of special geometric properties that a particular number may or may not enjoy. For example, numbers such as 10 and 15 aretriangular, something that is visible to us through the triangle of pins in ten-pin bowling and the triangular rack offifteen red balls in snooker. But this is not something that comes to mind from the base ten displays of these numbers alone. The freedom the ancients enjoyed by default we can recapture by casting aside our base ten prejudices and telling ourselves that we are free to think of numbers in quite different ways.
Having emancipated ourselves in this way, we might choose to focus on factorizations of a number, that is to say the way the number can be written as a product of smaller numbers multiplied together. Factorizations reveal something of the number’s inner structure. If we suspend the habit of thinking of numbers simply as servants of science and commerce, and take a little time to study them in their own right without reference to anything else, much is revealed that otherwise would remain hidden. The natures of individual numbers can manifest themselves in ordered patterns in nature, more subtle than mere triangles and squares, like the spiral head of a sunflower, which represents a so-called Fibonacci number, a number type that will be introduced in Chapter 5.
Aglance attheprimenumbersequence
One of the glories of numbers is so self-evident that it may easily be overlooked–every one of them is unique. Each number has its own structure, its own character if you like, and the personality of individual numbers is important because when a particular number arises, its nature has consequences for the structure of the collection to which that number applies. There are also relationships between numbers that reveal themselves when we carry out the fundamental number operations of addition and multiplication. Clearly any counting number greater than 1 can be expressed as the sum of smaller numbers. However, when we start multiplying numbers together, we soon notice that there are some numbers that never turn up as the answer to our sums. These numbers are the primes and they represent the building blocks of multiplication.
A prime number is a number like 7 or 23 or 103, which has exactly two factors, those necessarily being 1 and the number itself.(The word divisor is also used as an alternative word for factor.)We do not count 1 as a prime as it has only one factor. Thefirst prime then is 2, which is the only even prime and the following trio of odd numbers 3,5, and 7 are all prime. Numbers greater than 1that are not prime are called composite as they are composed of smaller numbers. The number 4=2×2=22 is thefirst composite number;9 is thefirst odd composite number, and 9=32 is also a square. With the number 6=2×3, we have thefirst truly composite number in that it is composed of two different factors that are greater than 1 but smaller than the number itself, while8=23 is thefirst proper cube, which is the word that means that the number is equal to some number raised to the power 3.
After the single-digit numbers, we have our chosen number base10=2×5, which is special nonetheless being triangular in that10=1+2+3+4(remember ten-pin bowling). We then have a pair of twin primes in 11 and 13, which are two consecutive odd numbers that are both prime, separated by the number 12, which in contrast has many factors for its size. Indeed,12 is thefirst so-called abundant number, as the the sum of its proper factors,those less than the number itself, exceeds the number in question:1+2+3+4+6=16.Thenumber14=2×7maylook undistinguished but, as the paradoxical quip goes, being the firstundistinguished number makes it distinguished after all. In15=3×5, we have another triangular number and it is thefirst odd number that is the product of two proper factors. Of course,16=24 is not only a square but thefirst fourth power(after 1),making it very special indeed. The pair 17 and 19 are another pair of twin primes, and I leave the reader to make their own observations about the peculiar nature of the numbers 18,20, and so on. For each you can make a claim to fame.
Returning to the primes, thefirst twenty of them are:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71.
Clearly, near the very beginning of the number sequence, primes are commonplace as there is little opportunity for small numbers to have factorizations. After that, the primes become rarer. For example, there is only one triple of consecutive odd primes:the trio 3,5,7 is unique, as every third odd number is a multiple of 3,and so this can never happen again. The thinning process of prime occurrence is, however, quite leisurely and surprisingly erratic. For example, the thirties have only two primes, those being 31 and 37,yet immediately after 100 there are two‘consecutive’pairs of twin primes in 101,103 and 107,109.
The primes have been a source of fascination for thousands of years because they never run out(a claim that we shall justify in the next chapter)yet they arise among the natural numbers in a somewhat haphazard fashion. This mysterious and unpredictable facet of their nature is exploited in modern cryptography to safeguard confidential communication on the Internet, which is the subject of Chapter 4.
Checking for primality:prime divisibility tests
The most simple-minded way offinding all the primes up to a given number such as 100 is to write all the numbers down and cross off the composite numbers as youfind them. The standard method based on this idea is called the Sieve of Eratosthenes and runs as follows. Begin by circling 2 and then cross off all the multiples of 2(the other even numbers)in your list. Then return to the beginning, circle thefirst number you meet that has not been crossed off(which will be 3)and then cross off all its multiples in the remaining list. By repeating this process sufficiently often, the primes will emerge as those numbers that never get crossed out, although some will be circled and some not.For example, Figure 1 shows the workings of the sieve up to 60.
How do you know when you can stop sieving?You need to repeat this process until you circle a number that is greater than the square root of the largest number in your list. For instance, if you do your own sieve for all numbers up to 120, you will need to run through the sieve for multiples of 2,3,5, and 7, and when you circle 11 you can stop, as 112=121. At that point, you will have circled as far as thefirst prime exceeding the square root of your biggest number(120 in this case)with the remaining primes sitting there untouched. All composite numbers will now have been crossed out as each is a multiple of one or more of 2,3,5,and 7.
1. Prime sieve:the primes up to 60 are the numbers notcrossed out
It is very easy to test for divisibility by 2 and by 5 as these primes are the prime factors of our number base ten. In view of this, you only need to check thefinal digit of the number nin question:nis divisible by 2 exactly when its units digit is even(i.e.0,2,4,6, or8), and nhas 5 as a factor if and only if it ends in 0 or 5. No matter how many digits the number nhas, we only need to check the last digit to determine whether we have a multiple of 2 or of 5. For primes that do not divide into 10, we need to do a bit more work but nevertheless there are simple tests for divisibility that are much quicker than resorting to doing the full division sum.
A number is divisible by 3 if and only if the same is true of the sum of its digits. For example, the sum of the digits ofn=145,373,270,099,876,790 is 87 and 87=3×29 and so n is in this case divisible by 3. Of course, we can apply the test to the number 87 itself and indeed go on taking the sum of digits of the outcome at each stage until the result is obvious. Doing this for the given example produces the following sequence:
145,373,270,099,876,790→87→15→6=2×3.
You will see that all the division tests listed here are so quick that you can handle numbers with dozens of digits with relative ease even though these numbers are billions of times greater than the biggest number with which your hand calculator can cope.
The tests given here for the remaining primes up to 20 are chosen because they are all of the same general type. These routines are all simple to apply, although it is less obvious why they work.Although the justifications are not recorded here, the proofs of their validity are not especially difficult.
n=27,916,924→2,791,684→279,160→27,916→2,779→259→7
and so n is divisible by 7. Each time we run through the loop of instructions, we lose at least one digit, so the number of passes through the loop is about the same as the length of the number with which we begin.
To test whether or not n has a factor of 11, subtract thefinal digit from the remaining truncated number and repeat. For example,the next number is a multiple of 11 as our method reveals:
4,959,746→495,968→49,588→4,950→495→44=4×11.
To check for divisibility by 13, add four times thefinal digit to the remaining truncated number and precede as with 7 and 11. For instance, the next number turns out to have 13 as one of its prime factors:
11,264,331→1,126,437→112,671→11,271
→1131→117→39=3×13.For 17 and for 19, we subtractfive times thefinal digit in the case of 17, and add twice thefinal digit when testing if 19 is a factor,once more applying this step to the truncated number that remains, repeating the process as often as we need. For example,we test 18,905 for divisibility by 17:
18,905→1,865→161→11
so it is not a multiple of 17, but for 19, the test gives the opposite conclusion:
18,905→1,900=100×19.
Armed with this battery of tests, you can readily check the primality of all numbers up to 500(as 232=529 exceeds 500, so19 is the largest potential prime factor that you need concern yourself with). For example, to settle the matter for 247, we just need to check for divisibility up to the prime 13(as the square of the next prime,172=289, exceeds 247). Applying the test for 13,however, we learn from 247→(24+28)=52→13, that we have a multiple of 13:(247=19×13).
The divisibility tests for primes can also be mounted in parallel to furnish divisibility tests for those numbers that are square-freeproducts of these primes(numbers not divisible by the square of any prime)such as 42=2×3×7:a number nwill be divisible by42 exactly when npasses the trio of divisibility tests for 2,3, and 7.However, tests for those numbers that have square factors, such as9=32, do not come automatically, although it is the case that n has 9 as a factor if and only if that is true of the sum of the digits of n.
You might ask, after thousands of years, haven’t those clever mathematicians come up with better and more sophisticated methods of testing for primality?The answer is yes. In 2002, a relatively quick way was discovered to test if a given number is prime. The so-called‘AKS primality test’does not, however,provide the factorization of the given number if it happens to be composite. The problem offinding the prime factors of a given number, although in principle solvable by trial, still seems practically intractable for extremely large integers, and for that reason it forms the basis of much ordinary encryption on the Internet, a subject to which we will return in Chapter 4. Before that we shall, in the next two chapters, look a little more closely at primes and factorization.