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

aandbis a positive integer that divides bothaandb.Definition. The greatest common divisor of

aandb, denoted here by gcd(a,b), is the greatest of all the common divisors ofaandb.Definition. If gcd(

a,b) = 1, thenaandbare 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

aandbis a positive integer that is a multiple of bothaandb.Definition. The least common multiple of

aandb, denoted by lcm(a,b), is the smallest positive integer that is a common multiple ofaandb.

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`:

- Set the value of the variable
`c`to the larger of the two values`a`and`b`, and set`d`to the smaller of`a`and`b`. - Find the remainder when
`c`is divided by`d`. Call this remainder`r`. - If
`r`= 0, then gcd(`a`,`b`) =`d`. Stop. - Otherwise, use the current values of
`d`and`r`as the new values of`c`and`d`, respectively, and go back to step 2.

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 2^{p} − 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

2^{2} − 1 | = | 3, | |

2^{3} − 1 | = | 7, | |

2^{5} − 1 | = | 31, | |

2^{7} − 1 | = | 127, | and |

2^{11} − 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
2^{43,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
2^{p−1}(2^{p} − 1)
is a perfect number whenever the number
2^{p} − 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
2^{2n} + 1, where `n` is a
nonnegative integer. Today such numbers are called Fermat numbers.
The first several Fermat numbers are

2^{20} + 1 | = | 3, | |

2^{21} + 1 | = | 5, | |

2^{22} + 1 | = | 17, | |

2^{23} + 1 | = | 257, | |

2^{24} + 1 | = | 65,537, | and |

2^{25} + 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!

Last updated 19 February 2010. Brian Kell <bkell@cmu.edu>