## Chapter 12. Number Theory

Why is it that we entertain the belief that for every purpose odd numbers are the most effectual?

*Natural History*

Number theory is thousands of years old. For most of those millennia,
it’s been “pure” mathematics, meaning that it had little
practical application. That has changed in the last few decades; many
of the most important advances in cryptography resulted from number
theory. In this chapter, we concentrate on prime numbers and modular
exponentiation, both of which are invaluable for the next
chapter: *cryptography*.

Before we can talk about prime numbers, we’ll first explore the basics of number theory: the greatest common divisor (GCD) and least common multiple (LCM), and techniques for performing modular arithmetic. Then we’ll use these techniques to find large prime numbers. (We’ll also demonstrate caching techniques to make the search faster.) Finally, we’ll spend a few pages on diversions: three simple Perl programs that illustrate some unsolved problems in mathematics.

This is the most theoretical chapter in the book, but don’t let that scare you. The mathematics involved is quite simple.

## Basic Number Theory

Most of this section is about
*divisors* and
*remainders*. A divisor is a number which evenly
divides another number, its *multiple*. (2 is a
divisor of 6, 6 is a multiple of 2.) A
remainder is the amount left over when you divide one number into
another. (When you divide 7 by 2, the remainder is 1.)

We will generally ...

Get *Mastering Algorithms with Perl* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.