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 2Multiplying 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
