1.2   Divisors and Factorization

How do we find the set of positive divisors for an integer? If you happen to have a computer at your disposal, you could just use the Java applet from the previous section. However, it is important to understand how this applet works, especially if you ever stray more than a few feet from your computer.

The most basic method for computing divisors is exhaustive trial division. If we want to find the positive divisors for an integer n, we just take the integers 1, 2, 3, . . . , n, divide n by each, and those that divide evenly make up the set of positive divisors for n. This method works well and is rather simple, but it is also quite inefficient.

One way to improve upon the above procedure is by applying the following observation: if m is a divisor of n, then k = n/m is also a divisor of n, because mk = n. Thus, the positive divisors can be organized into pairs of the form (mn/m), where m < n/m. The one exception to this is if n is a perfect square and m = sqrt(n), in which case m = n/m. For example, if n = 100, then the positive divisors of n are given by

Your browser does not support java.

For this value of n, we have the pairs (1, 100), (2, 50), (4, 25), and (5, 20), and because 100 is a perfect square, the single divisor sqrt(100) = 10. Note that for each pair of positive divisors, the smaller divisor is less than sqrt(n). This is also the case in general: if m | n and m < n/m, then m < sqrt(n). (The proof of this assertion is left as a homework exercise.) Thus, all positive divisors can be found by first using exhaustive trial division by all integers up to sqrt(n), and then generating the pairs to identify the remaining positive divisors.

For example, suppose that n = 152. Then a decimal approximation for sqrt(n) is given by

Your browser does not support java.

Dividing each of 1, 2, 3, . . . , 12 into 152 reveals the divisors 1, 2, 4, and 8. The remaining positive divisors of 152 are then given by

152/1 = 152
152/2 = 76
152/4 = 38
152/8 = 19

Here's a check:

Your browser does not support java.

How much time do we save by using the second method instead of the first? We can measure how long it takes each method to compute the divisors of 10000 using the applet below. "Trial n" finds divisors by using trial division up to n, and "Trial sqrt(n)" finds divisors by using trial division up to sqrt(n):

Your browser does not support java.

"Trial sqrt(n)" is significantly faster. The reason for the difference in speed is clear: "Trial n" has to test n possible integers, while "Trial sqrt(n)" checks only sqrt(n) integers. So the running time for "Trial n" should be roughly proportional to n whereas the running time for "Trial sqrt(n)" should be roughly proportional to sqrt(n).

There are other things going on inside the computer, so one should not expect timing estimates like this to be exact. However, they can provide good ballpark estimates.

What do you think will happen to the running times for each method if we multiply n by 10? Then check the result by changing 10000 in the above applet.

Now try to answer the following question.

Exercise 1

On the basis of the timings above, extrapolate the amount of time (in years) required to find the positive divisors for 1018 using both methods discussed above. For simplicity, you may assume that all years have 365 days.

A problem related to finding the set of divisors for an integer is that of finding the prime-power factorization of an integer. Indeed, we shall see later in the chapter how to use the factorization of an integer to easily compute all of the divisors for the integer.

A number of different methods have been developed for finding the factorization of an integer. The method that we shall describe here is fairly simple, and borrows from the ideas used above to find divisors; that is, it uses trial division.

Recall that finding the prime factorization of an integer requires us to express an integer n as

n = piai.

The basic procedure for finding the factorization is as follows:

  1. Start with the first prime, p = 2, and check to see if 2 | n. If so, then replace n with n/2. Repeat until 2 will no longer divide in evenly, keeping track of the number of factors of 2.

  2. Repeat the above step with the next prime, p = 3, and then with the next prime, p = 5, and so on. As above, keep track of the number of factors along the way.

  3. Stop when you are left with 1 or with a number you know is prime.

As an example, let us find the prime-power factorization for n = 571450. We start by dividing n by 2:

Your browser does not support java.

Although it is pretty obvious from the output, let's see if 2 will divide evenly into the above quotient:

Your browser does not support java.

Since we get a noninteger for output, we know that 2 won't divide in again. Thus we know that 21 is the correct power of 2 in the factorization. Now let's move to the prime 3:

Your browser does not support java.

This doesn't divide in evenly, so 3 is not included in the factorization. Let's try 5:

Your browser does not support java.

Thus 5 divides in evenly, and as we can see from the output, 5 will divide in evenly again:

Your browser does not support java.

That's it for the 5s. Hence we know that 52 is the correct power of 5 in the factorization. Here's the test for the prime 7:

Your browser does not support java.

No luck. Here's the prime 11:

Your browser does not support java.

Continuing in this manner, we find that 1039 is not divisible by 11, 13, 17, 19, 23, 29, or 31. We already know that 1039 is not divisible by 2, 3, or 5 because we divided away all factors of 2, 3, and 5 already. If we are clever, we can stop now since sqrt(1039) is approximately . . .

Your browser does not support java.

Because 1039 has no prime divisors less than or equal sqrt(1039), it must be prime. Thus we now have the entire factorization:

571450 = 21·52 ·111·1039

The method described and illustrated above will work well for fairly small integers and can be used to factor numbers on a hand calculator. However, this technique is inefficient for larger integers, and more-advanced methods must be used in these cases. But even the more-sophisticated factoring techniques have their limits. The general problem of factoring large integers (upwards of 200 digits!) is a difficult one, and is currently an area of intense mathematical research. The problem is not only interesting in its own right, but also has some important applications. We'll see how factoring is related to cryptography in a later chapter.

Section 1.1 | Section 1.2 | Section 1.3 | Section 1.4 | Section 1.5

Chapter 1 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company