Our textbook, Problem Solving Through Recreational Mathematics, does a good job of explaining many topics in number theory in Chapter 4. Here are a few interesting ideas that aren’t covered in the book.
The following definitions are given in the book on page 116:
Definition. A common divisor of a and b is a positive integer that divides both a and b.
Definition. The greatest common divisor of a and b, denoted here by gcd(a, b), is the greatest of all the common divisors of a and b.
Definition. If gcd(a, b) = 1, then a and b are said to be relatively prime.
For example, the common divisors of 18 and 30 are 1, 2, 3, and 6, so gcd(18, 30) = 6. The only common divisor of 14 and 25 is 1, so gcd(14, 25) = 1, and therefore 14 and 25 are relatively prime. Note that “relatively prime” expresses a relationship between two numbers; it makes no sense to say, for example, “14 is relatively prime.” (Some authors use the word coprime instead of relatively prime.)
A similar idea is the concept of least common multiple, defined below.
Definition. A common multiple of a and b is a positive integer that is a multiple of both a and b.
Definition. The least common multiple of a and b, denoted by lcm(a, b), is the smallest positive integer that is a common multiple of a and b.
For example, the common multiples of 6 and 10 are 30, 60, 90, 120, and so on, so lcm(6, 10) = 30.
The greatest common divisor and the least common multiple of two numbers can be found using the numbers’ prime factorizations. For example, let’s consider the two numbers 10 and 12. Their prime factorizations are 10 = 2 × 5 and 12 = 2 × 2 × 3. The prime numbers that appear in either of these factorizations are 2, 3, and 5, and these primes appear different numbers of times in the two factorizations: the prime factorization of 10 has one 2, no 3’s, and one 5, while the prime factorization of 12 has two 2’s, one 3, and no 5’s.
A common divisor of 10 and 12 cannot have more of any one prime factor than either of the two numbers 10 and 12, so to find the greatest common divisor we take as many of each prime factor as we can without “going over.” We can take one factor of 2, because 10 has one 2 and 12 has two 2’s (we can’t take two 2’s for the greatest common divisor, because that is more than the number of 2’s in 10). We can’t take any 3’s, because 10 doesn’t have any, and we can’t take any 5’s, because 12 doesn’t have any. So the greatest common divisor of 10 and 12 has just one 2 and nothing else, which means gcd(10, 12) = 2.
Finding the least common multiple is similar, but we take the fewest of each prime factor as we can while still “covering” all of the prime factors of both 10 and 12. We must take two 2’s, because 12 has two 2’s (10 has only one 2, so taking two 2’s will cover it). We must take one 3 to cover the 3 in the factorization of 12, and we must take one 5 to cover the 5 in the factorization of 10. So the least common multiple of 10 and 12 is 2 × 2 × 3 × 5 = 60.
For large numbers, there is a simpler way to find the greatest common divisor, which doesn’t require us to find the prime factorizations of the two numbers. This method, which we will describe next, is called the Euclidean algorithm.
An algorithm is a method or a sequence of steps that can be followed to solve a problem. There are two important features that a method should have in order to be called an algorithm: First, it should always eventually come to an end, so that the method can always be completed. Second, each step in an algorithm should be precisely and unambiguously defined. (It can take a considerable amount of creativity and ingenuity to design an algorithm to solve a particular problem, but it should require no imagination to follow the steps of the algorithm once it has been specified. Each step should be simple enough that it can be performed mechanically, by a computer, for example.)
The study of algorithms became very important in the 20th century, because any task that is to be performed by a computer must first be described by an algorithm. Many beautiful and deep results about algorithms have been discovered; we will mention a few of these results in broad terms throughout the rest of this course.
The Euclidean algorithm is an algorithm to find the greatest common divisor of two numbers. It is named after Euclid, a Greek mathematician who lived in Egypt about 300 B.C. Euclid probably did not discover this algorithm himself, but his description of the algorithm is the earliest that still survives.
Here are the steps of the Euclidean algorithm to find the greatest common divisor of two positive integers a and b:
For example, suppose we want to find gcd(357, 462). In step 1, we set the value of c to 462 and the value of d to 357. Let’s keep track of the current values of the variables c, d, and r in a table:
| c | d | r | |
|---|---|---|---|
| Step 1 | 462 | 357 |
In step 2, we find the remainder when 462 is divided by 357. This remainder is 105, so we set the value of r to 105.
| c | d | r | |
|---|---|---|---|
| Step 2 | 462 | 357 | 105 |
The remainder r is not 0, so we skip step 3 and go to step 4. We use the current values of d and r as the new values of c and d, respectively, so we set c to 357 and d to 105. (Technically the value of r remains 105 at this step, but we are going to replace it with a new value in the next step, so we’ll just leave a blank in the table.)
| c | d | r | |
|---|---|---|---|
| Step 4 | 357 | 105 |
Now we go back to step 2. We set the value of r to the remainder when 357 is divided by 105, which is 42.
| c | d | r | |
|---|---|---|---|
| Step 2 | 357 | 105 | 42 |
Again, r ≠ 0, so we skip step 3 and go to step 4. We set c to 105 and d to 42.
| c | d | r | |
|---|---|---|---|
| Step 4 | 105 | 42 |
We go back to step 2 and continue, repeating these steps until the remainder r becomes 0:
| c | d | r | |
|---|---|---|---|
| Step 2 | 105 | 42 | 21 |
| Step 4 | 42 | 21 | |
| Step 2 | 42 | 21 | 0 |
Now r = 0, so we go to step 3. We conclude that the current value of d is the greatest common divisor of the two numbers we started with, so gcd(357, 462) = 21.
We can summarize this whole procedure in one table:
| c | d | r | |
|---|---|---|---|
| Step 1 | 462 | 357 | |
| Step 2 | 462 | 357 | 105 |
| Step 4 | 357 | 105 | |
| Step 2 | 357 | 105 | 42 |
| Step 4 | 105 | 42 | |
| Step 2 | 105 | 42 | 21 |
| Step 4 | 42 | 21 | |
| Step 2 | 42 | 21 | 0 |
| Step 3 | gcd(357, 462) = 21 | ||
Note that 357 = 21 × 17 and 462 = 21 × 22, so 21 is indeed a common divisor of 357 and 462. (This is a good check, just to make sure we didn’t make a mistake in our arithmetic.)
The Euclidean algorithm is very efficient and easy to use. It is still in common use over 2,000 years after Euclid first described it (of course, today the algorithm is usually performed by electronic computers).
A key step in the Euclidean algorithm is finding the remainder when one number is divided by another. It is helpful to be able to do this with a calculator, especially if the numbers are large. So let’s see how this can be done.
First, if the result of the division is a whole number, the remainder is 0. For instance, if we enter 345 ÷ 23, we get 15 exactly, which means that the remainder when 345 is divided by 23 is 0.
Now suppose we want to find the remainder when, say, 709 is divided by 63. If we enter 709 ÷ 63 into a calculator, we get 11.253968. This is not a whole number, so the remainder is not 0. There are two ways to get the remainder.
The first way goes like this: The number 63 goes into 709 somewhere between 11 and 12 times. This means that 63 × 11 is the greatest multiple of 63 that is no more than 709. We find that 63 × 11 = 693, so the remainder we seek is 709 − 693 = 16.
The second method works with the decimal part of the quotient, 0.253968. (Note that this decimal itself is not the remainder!) To find the remainder, we multiply this decimal part by the number 63, and we get 0.253968 × 63 = 15.999984. We round this to 16, which is the remainder we are looking for. (The reason the multiplication doesn’t come out to 16 exactly is that the decimal 0.253968 is rounded off—the true decimal part goes on forever, but only a few digits can fit in the calculator’s display.)
Note that both of these methods give us the same answer, which is good (otherwise something would be wrong with mathematics).
Ancient mathematicians were intrigued by the relationships between numbers and their factors (modern mathematicians are too, of course). The proper divisors of a positive integer are all its divisors except the number itself. For example, the proper divisors of 12 are 1, 2, 3, 4, and 6. The Greeks called a number perfect if the sum of its proper divisors was equal to the original number. The smallest perfect number is 6: its proper divisors are 1, 2, and 3, and 1 + 2 + 3 = 6. What is the next perfect number?
The positive integers which are not perfect can be classified as either deficient or abundant. A number is called deficient if the sum of its proper divisors is less than the number itself, and conversely a number is called abundant if the sum of its proper divisors is greater than the number itself. For example, 8 is a deficient number, because the proper divisors of 8 are 1, 2, and 4, and 1 + 2 + 4 = 7, which is less than 8. On the other hand, 12 is an abundant number, because the proper divisors of 12 are 1, 2, 3, 4, and 6, and 1 + 2 + 3 + 4 + 6 = 16, which is greater than 12.
The number 1 presents a special case, because it has no proper divisors (the only divisor of 1 is 1 itself). So the sum of the proper divisors of 1 is considered to be 0 (because there aren’t any). This is less than 1, so 1 is deficient.
Perfect numbers are quite rare. The ancient Greeks knew only the first four of them, and even today, after extensive searching by computer, we know of only 47 perfect numbers (the largest of which has almost 26 million digits). It is possible that there are infinitely many perfect numbers, but it is also possible that there are only a fixed number of them; no one knows for certain.
All of the perfect numbers that have been found so far are even. No one knows if odd perfect numbers exist. No odd perfect number has ever been found, but no one knows a reason there shouldn’t be any.
Numbers that can be written as 2p − 1, where p is a prime number, are called Mersenne numbers, after the 17th-century French mathematician Marin Mersenne (who was also a theologian, philosopher, and music theorist). The first few Mersenne numbers are
| 22 − 1 | = | 3, | |
| 23 − 1 | = | 7, | |
| 25 − 1 | = | 31, | |
| 27 − 1 | = | 127, | and |
| 211 − 1 | = | 2047. |
Note that 3, 7, 31, and 127 are all prime, but 2047 = 23 × 89, so 2047 is composite. A Mersenne number that is prime is called a Mersenne prime.
Many of the largest primes known are Mersenne primes, because efficient methods have been developed to test whether Mersenne numbers are prime, but these methods do not work for other numbers. A coordinated effort using the Internet, called the Great Internet Mersenne Prime Search (or GIMPS), has found 13 Mersenne primes since 1997, including the largest prime number currently known. This record-holding prime is 243,112,609 − 1, which has almost 13 million digits. (The achievements of GIMPS are even more impressive when one considers that there are only 47 Mersenne primes known in all.)
There is a strong connection between the even perfect numbers and the Mersenne primes. Euclid proved that the number 2p−1(2p − 1) is a perfect number whenever the number 2p − 1 is prime. In the 18th century the Swiss mathematician Leonhard Euler (pronounced “Oiler”) proved that this formula actually gives all of the even perfect numbers. So every Mersenne prime corresponds to exactly one even perfect number, and vice versa. (This is the reason there are currently 47 perfect numbers known: they correspond to the 47 known Mersenne primes.)
The 17th-century French lawyer Pierre de Fermat was an avid recreational mathematician. Many of his discoveries laid the groundwork for modern number theory. Among other things, he investigated the numbers that can be written as 22n + 1, where n is a nonnegative integer. Today such numbers are called Fermat numbers. The first several Fermat numbers are
| 220 + 1 | = | 3, | |
| 221 + 1 | = | 5, | |
| 222 + 1 | = | 17, | |
| 223 + 1 | = | 257, | |
| 224 + 1 | = | 65,537, | and |
| 225 + 1 | = | 4,294,967,297. |
Fermat conjectured that all such numbers are prime (a Fermat number that is prime is called a Fermat prime). He was able to check this statement for a few numbers, but he was unable to prove it in general. It turns out that his conjecture is false, which was established in 1732 when Euler showed that the Fermat number corresponding to n = 5 is composite:
4,294,967,297 = 641 × 6,700,417.
(Remember that Euler figured this out without the help of a computer!)
Fermat numbers have been investigated with computers, and so far no Fermat primes have been found other than the five known to Fermat (those corresponding to n = 0 through n = 4). It is unknown whether any other Fermat primes exist. It seems unlikely, but no one knows for sure. In fact, as far as anyone knows, it is possible that there are infinitely many Fermat primes!