Number Theory: A Very Short Introduction
Page 3
In this chapter I’ll lay the groundwork for our later explorations, by introducing several types of number that you’ll meet again and posing several questions. Some of these questions are easy to answer, whereas others are harder but are solved in subsequent chapters, and a few are notorious problems for which no answer has yet been found. For the moment I won’t reveal which questions fall into which category, because you may like to think about them first. Their answers (where known) are summarized at the end of this book, in Chapter 9.
Integers
This book is about the integers (or whole numbers),
2. The integers.
These include the counting numbers or positive integers (1, 2, 3, 4, 5, … ), the negative integers ( …, −4, −3, −2, −1), and the number 0 (see Figure 2).
We can also split the collection of integers into the even numbers
and the odd numbers
Every even number is twice another integer—that is, it has the form 2n, where n is an integer: for example,
Similarly, every odd number is one more than twice another integer—that is, it has the form where n is an integer: for example,
The multiples of a given integer n are those numbers that leave no remainder when divided by n: for example,
These numbers all end in 0, and conversely all numbers that end with 0 (such as 70) are multiples of 10. Similarly,
These numbers all end in 0 or 5, and conversely all numbers that end in 0 or 5 (such as 40 and 65) are multiples of 5.
The multiples of 2 are the even numbers—those numbers that end in 2, 4, 6, 8, or 0. But what can we say about the multiples of other numbers? For example:
How can we recognize whether a given number, such as 12,345,678, is a multiple of 8? or of 9? or of 11? or of 88?
I’ll answer these questions in Chapter 2, where we’ll explore multiples in greater detail.
In number theory the single word ‘number’ generally refers to a positive integer, and we shall follow this convention unless otherwise stated.
Squares and cubes
The Pythagoreans seem to have been particularly interested in perfect squares, which they depicted geometrically by square patterns of dots, as in Figure 3.
3. The first four non-zero squares.
A square (or perfect square) has the form , where n is an integer: for example, 144 is a square because or (−12)2, and 0 is a square because . All the non-zero squares are positive integers, the first ten being
These squares all end in 1, 4, 5, 6, 9, or 0, and we might ask:
Do any squares end in 2, 3, 7, or 8?
We also notice that each of these squares is
either a multiple of 4: for example, ,
or one more than a multiple of 4: for example, ,
and we might ask whether this is always true:
Must all squares be of the form 4n or , where n is an integer?
The Pythagoreans also apparently observed such results as
Because 16 and 49 are both squares, we might ask:
Must the sum of the first few odd numbers, 1, 3, 5, 7, …, always be a square?
What happens if we add two squares together? The number can be written as the sum of two squares, as can the number . But the numbers 12, 14, and 15 cannot be written in this way, and we may ask:
Which numbers can be written as the sum of two squares?
However, the numbers and can be written as the sum of three squares, and the number can be written as the sum of four squares, and we can ask such questions as:
Can 9999 be written as the sum of two squares? or of three squares? or of four squares?
Squares also arise in the geometry of right-angled triangles. By the Pythagorean theorem, the lengths a, b, c of the sides of a right-angled triangle satisfy the equation (see Figure 4): for example,
and we might ask:
Which other right-angled triangles have integer-length sides?
4. Right-angled triangles.
Let’s now turn our attention to cubes.
A cube (or perfect cube) has the form , where n is an integer: for example, 343 and −216 are cubes because and . Cubes can be positive, negative, or zero, and the first ten positive cubes are
Each of these cubes is
either a multiple of 9: for example, ,
or one more than a multiple of 9: for example, ,
or eight more than a multiple of 9: for example, ,
and we might ask:
Must all cubes be of the form , where n is an integer?
An unexpected link between squares and cubes is
and we might ask:
Must the sum of the first few cubes 13, 23, 33, … always be a square?
Above we saw that the sum of two squares can be another square: for example, . We may ask whether there’s a similar statement for cubes:
Are there any integers a, b, c for which ?
Just as we can write numbers as the sum of squares, so we can also write them as the sum of cubes—for example:
So we might ask:
Can every number be written as the sum of six cubes?
I’ll answer these questions in Chapters 2 and 5 where we’ll explore squares and cubes in greater detail.
Perfect numbers
The factors, or divisors, of a given number are the positive integers that divide exactly into it, leaving no remainder: for example, the factors of 10 are 1, 2, 5, and 10. A factor that’s not equal to the number itself is a proper factor: the proper factors of 10 are 1, 2, and 5.
In Book IX of his Elements Euclid discussed perfect numbers, which were believed to have mystic or religious significance. A perfect number is a number whose proper factors add up to the original number: for example,
6 is perfect, because its proper factors are 1, 2, and 3, which add up to 6;
28 is perfect, because its proper factors are 1, 2, 4, 7, and 14, which add up to 28.
The first four perfect numbers, already known to the Ancient Greeks, are 6, 28, 496, and 8128, and we might ask:
What is the next perfect number after 8128?
and, more generally,
Is there a formula for producing perfect numbers?
We’ll explore perfect numbers in Chapter 3.
Prime numbers
As you saw earlier, a prime number is a number that has no factors other than itself and 1: for example, 13 and 17 are prime numbers, whereas is not. The first fifteen primes are
A number that is not prime (such as 14, 15, or 16) is called composite.
The number 1 is regarded as neither prime nor composite. We’ll explain why in Chapter 3, where we explore prime numbers in greater detail.
Prime numbers lie at the heart of number theory because they’re the ‘building blocks’, or ‘atoms’, of our counting system, in the sense that every number that’s greater than 1 can be obtained by multiplying primes together: for example,
In some cases we can answer difficult questions about numbers in general by first answering them for primes and then combining the results.
From the above list we see that 2 and 3 seem to be the only prime numbers that differ by 1, but that several pairs of primes differ by 2: some examples are
Such pairs are called twin primes, and larger examples include 101 and 103, 2027 and 2029, and 9,999,971 and 9,999,973. Knowing that the list of primes is never-ending, we may likewise ask:
Does the list of twin primes go on for ever?
On the other hand, we sometimes find large gaps between successive prime numbers; for example, the prime numbers 23 and 29 are separated by the five composite numbers, 24, 25, 26, 27, and 28, and the primes 113 and 127 are separated by the thirteen consecutive composite numbers from 114 to 126. But how large can these gaps be? For example:
Is there a string of 1000 consecutive composite numbers?
Another question arises when we add prime numbers. Noticing that
we might ask:
Can every even number be written as the sum of two primes
?
Several prime numbers can be written as the sum of two squares: for example,
But some other primes, such as 11, 23, and 47, cannot be written like this, and we might ask:
Which prime numbers can be written as the sum of two squares?
We may also notice that some prime numbers are one less than a power of 2: for example,
But none of the following numbers of this type is prime:
Noticing that the exponents (2, 3, 5, and 7) in the first list are all prime, whereas those in the second list (4, 6, 8, 9, and 10) are all composite, we might ask:
Is the number always prime when n is prime, and always composite when n is composite?
Prime numbers of the form are called Mersenne primes after the 17th-century French mathematician and friar Marin Mersenne, who explored their properties. They arise in connection with perfect numbers, and with the search for large primes, as we’ll see in Chapter 3.
Likewise, some prime numbers are one more than a power of 2. For example, Pierre de Fermat considered numbers of the form , where n is itself a power of 2, and when , he obtained the numbers
Recognizing that these five numbers are all prime, Fermat tried (but failed) to prove that this was always the case, and so we may ask:
Are all numbers of this form prime?
These numbers are now called Fermat numbers, and we’ll investigate them in Chapter 3, where we’ll see how they arise unexpectedly in connection with an ancient problem in geometry.
Before leaving prime numbers, we notice that every prime number (other than 2), being an odd number, must be either one more, or three more, than a multiple of 4—that is, it’s of the form or , for some integer n. Examples of primes of the first type are
and of the second type are
Do these lists go on for ever?—that is, we may ask:
Are there infinitely many primes of the form ? or of the form ?
We may also ask the following related question:
Are there infinitely many primes with final digit 9?
We’ll explore such questions in Chapter 7.
This introductory chapter was designed to give you some idea of what to expect in the coming chapters, and some intimation of the delights that await you as we explore an area of study that has fascinated amateurs and professionals alike for thousands of years. Number theory is now a massive subject and many important topics have had to be omitted from these pages, but I hope that my selection will give you some idea of the wide-ranging aspects of number theory as it arose historically and as it is still practised today.
Chapter 2
Multiplying and dividing
Much of number theory is concerned with multiplying and dividing whole numbers, and in this chapter we’ll explore their multiples and divisors (or factors). After presenting the division rule and Euclid’s algorithm for finding the greatest common divisor of two numbers, we’ll explore some properties of squares and cubes, present some quick tests for determining which numbers can be divided evenly by certain given numbers (such as 4, 9, and 11), and conclude with the ancient method of ‘casting out nines’.
Multiples and divisors
Given two integers a and b, we say that b is a multiple of a if there’s an integer x with : for example, 18 is a multiple of 3 because ; here, . In this case, we also say that a is a divisor or a factor of b, and that a divides b, and b is divisible by a, so 3 is a divisor or factor of 18, 3 divides 18, and 18 is divisible by 3 (see Figure 5). All of these terms are in common use and we’ll use them interchangeably.
5. 18 is a multiple of 3, and 3 is a divisor of 18;
b is a multiple of a, and a is a divisor of b.
As further examples, we see that the first five positive multiples of 100 are
and that the positive divisors of 100 are
Also, the number 1 divides every positive integer.
A basic result on multiples and divisors is:
If a and b are both multiples of a number d, then so is their sum ,
or, in terms of divisors,
If d divides both a and b, then d also divides their sum .
This is because if and , for some numbers x and y, then
(see Figure 6). For example, 5 divides both 40 and 30, and so also divides their sum, 70.
6. If d divides a and b, then d also divides
We can likewise prove that if d divides a and b, then d also divides their difference, : for example, 5 divides both 40 and 30, and so also divides their difference, 10.
We can also see that
If d divides a, then d divides all of its multiples .
This is because, if , then
for example, 5 divides 40, and so divides all of its multiples, such as 160.
Combining this with the above result about the sum, we deduce that:
If d divides both a and b, then d divides all numbers of the form , for any integers m and n.
This is because d divides the multiples and , and so divides their sum: we’ll call these numbers ‘combinations’ of a and b. For example, because 5 divides both 40 and 30, it also divides their multiples and , and so divides the sum of these, the combination . We notice that the special cases , , and , , give us the above statements on the sum and difference .
For a change of pace, we’ll end this section with a puzzle that involves divisors:
A census-taker visits a mathematical family at their home and the following conversation takes place:
Census-taker: How old are your three children?
Parent: The product of their ages is 36 and the sum is our house number.
Census-taker: I need more information. Are your two youngest children the same age?
Parent: No.
Census-taker: Ah! Now I know their ages.
How old were they?
How might we go about answering this, as there seems to be too little information provided? To do so, let’s look first at the possible ways of writing 36 as the product of three numbers:
with sums of 38, 21, 16, 14, 13, 13, 11, and 10, respectively. The census-taker, seeing the house number, would know which of these was correct, unless the sum were the repeated number 13, in which case there are two possibilities. But because the two youngest children are not the same age, their ages cannot be 9, 2, and 2, and so must be 6, 6, and 1.
Least common multiple and greatest common divisor
In this section we’ll investigate two important numbers associated with the numbers a and b.
The least common multiple
Let’s look at two situations. The first involves two ancient calendars:
In the first millennium ad the Mayans of Central America had two yearly calendars, one based on 260 days and the other on 365 days, which they then combined into a single ‘calendar round’ of 18,980 days (= 52 years). But where did this number come from?
The second situation involves two gears (see Figure 7):
7. Two gears with 90 and 54 teeth.
I have two rotating gears, with 90 and 54 teeth. When do the starting positions of these gears align?
The starting positions align whenever the number of teeth that have passed the starting position is simultaneously a multiple of 90 and a multiple of 54. So what are these multiples?
For the first gear, the first few multiples are
whereas for the second gear, they are
and the multiples that they have in common are the numbers in bold type—that is, 270 and 540. The smaller of these is 270, and we say that 270 is the ‘least common multiple’ of 90 and 54. So the starting positions align whenever 270 teeth have passed—that is, after every three rotations of the first gear and every five rotations of the second gear.
In general, m is a common multiple of the integers a and b if m is a multiple of both a and b, and the least common multiple is the smallest positive common multiple. If m is the least common multiple of a and b, we write . In the above example,
and further examples are
For the
Ancient Mayans, the two calendars came together after each period of .
Many people meet least common multiples for the first time when they learn how to add fractions. For example, to add the fractions and we first put them over a common denominator:
We can now add these fractions directly to give , which then simplifies to . Here, the common denominator is the least common multiple,
The greatest common divisor
Related to the least common multiple of two integers is their greatest common divisor.
The divisors of 90 are
and those of 54 are
so the ones that they have in common are 1, 2, 3, 6, 9, and 18. The largest of these is 18, so 18 is the ‘greatest common divisor’ of 90 and 54.
In general, d is a common divisor of the numbers a and b if d divides both a and b, and the greatest common divisor is the largest of these common divisors. If d is the greatest common divisor of a and b, we write ; it is sometimes called their highest common factor (written hcf). In the example above,