Number theory is concerned with the properties of the integers. One of the most important is divisibility.
Let and be integers with We say that divides if there is an integer such that This is denoted by Another way to express this is that is a multiple of
(does not divide).
The following properties of divisibility are useful.
Let represent integers.
For every and Also, for every
If and then
If and then for all integers and
Proof. Since we may take in the definition to obtain Since we take to prove Since we have This proves (1). In (2), there exist and such that and Therefore, so For (3), write and Then so
For example, take in part (2). Then simply means that is even. The statement in the proposition says that which is a multiple of the even number must also be even (that is, a multiple of ).
A number whose positive divisors are only 1 and itself is called a prime number. The first few primes are An integer that is not prime is called composite, which means that must be expressible as a product of integers with A fact, known already to Euclid, is that there are infinitely many prime numbers. A more precise statement is the following, proved in 1896.
Let be the number of primes less than Then
in the sense that the ratio as
We won’t prove this here; its proof would lead us too far away from our cryptographic goals. In various applications, we’ll need large primes, say of around 300 digits. We can estimate the number of 300-digit primes as follows:
So there are certainly enough such primes. Later, we’ll discuss how to find them.
Prime numbers are the building blocks of the integers. Every positive integer has a unique representation as a product of prime numbers raised to different powers. For example, 504 and 1125 have the following factorizations:
Moreover, these factorizations are unique, except for reordering the factors. For example, if we factor 504 into primes, then we will always obtain three factors of 2, two factors of 3, and one factor of 7. Anyone who obtains the prime 41 as a factor has made a mistake.
Every positive integer is a product of primes. This factorization into primes is unique, up to reordering the factors.
Proof. There is a small technicality that must be dealt with before we begin. When dealing with products, it is convenient to make the convention that an empty product equals 1. This is similar to the convention that Therefore, the positive integer 1 is a product of primes, namely the empty product. Also, each prime is regarded as a one-factor product of primes.
Suppose there exist positive integers that are not products of primes. Let be the smallest such integer. Then cannot be 1 ( the empty product), or a prime ( a one-factor product), so must be composite. Therefore, with Since is the smallest positive integer that is not a product of primes, both and are products of primes. But a product of primes times a product of primes is a product of primes, so is a product of primes. This contradiction shows that the set of integers that are not products of primes must be the empty set. Therefore, every positive integer is a product of primes.
The uniqueness of the factorization is more difficult to prove. We need the following very important property of primes.
If is a prime and divides a product of integers then either or More generally, if a prime divides a product then must divide one of the factors
For example, when this says that if a product of two integers is even then one of the two integers must be even. The proof of the lemma will be given at the end of the next section, after we discuss the Extended Euclidean algorithm.
Continuing with the proof of the theorem, suppose that an integer can be written as a product of primes in two different ways:
where and are primes, and the exponents and are nonzero. If a prime occurs in both factorizations, divide both sides by it to obtain a shorter relation. Continuing in this way, we may assume that none of the primes occur among the ’s. Take a prime that occurs on the left side, say Since divides which equals the lemma says that must divide one of the factors Since is prime, This contradicts the assumption that does not occur among the ’s. Therefore, an integer cannot have two distinct factorizations, as claimed.
The greatest common divisor of and is the largest positive integer dividing both and and is denoted by either or by In this book, we use the first notation. To avoid technicalities, we always assume implicitly that at least one of and is nonzero.
We say that and are relatively prime if There are two standard ways for finding the gcd:
If you can factor and into primes, do so. For each prime number, look at the powers that it appears in the factorizations of and Take the smaller of the two. Put these prime powers together to get the gcd. This is easiest to understand by examples:
Note that if a prime does not appear in a factorization, then it cannot appear in the gcd.
Suppose and are large numbers, so it might not be easy to factor them. The gcd can be calculated by a procedure known as the Euclidean algorithm. It goes back to what everyone learned in grade school: division with remainder. Before giving a formal description of the algorithm, let’s see some examples.
Compute gcd(482, 1180).
SOLUTION
Divide 482 into 1180. The quotient is 2 and the remainder is 216. Now divide the remainder 216 into 482. The quotient is 2 and the remainder is 50. Divide the remainder 50 into the previous remainder 216. The quotient is 4 and the remainder is 16. Continue this process of dividing the most recent remainder into the previous one. The last nonzero remainder is the gcd, which is 2 in this case:
Notice how the numbers are shifted:
Here is another example:
Therefore,
Using these examples as guidelines, we can now give a more formal description of the Euclidean algorithm. Suppose that is greater than If not, switch and The first step is to divide by hence represent in the form
If then divides and the greatest common divisor is If then continue by representing in the form
Continue in this way until the remainder is zero, giving the following sequence of steps:
The conclusion is that
There are two important aspects to this algorithm:
It does not require factorization of the numbers.
It is fast.
For a proof that it actually computes the gcd, see Exercise 59.