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 (m, n/m), where
m < n/m. The one exception to
this is if n is a perfect square and m =
,
in which case m = n/m. For example,
if n = 100, then the positive divisors of n
are given by
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
= 10.
Note that for each pair of positive divisors, the smaller divisor
is less than
.
This is also the case in general:
if m | n and m < n/m,
then m < .
(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
,
and then generating the pairs to identify the remaining
positive divisors.
For example, suppose that
n = 152. Then a decimal approximation for
is given by
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:
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
:
"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
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
.
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
.
The basic procedure for finding the factorization is as follows:
- 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.
- 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.
- 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:
Although it is pretty obvious from the output, let's see if 2 will divide evenly into the above quotient:
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:
This doesn't divide in evenly, so 3 is not included in the factorization. Let's try 5:
Thus 5 divides in evenly, and as we can see from the output, 5 will divide in evenly again:
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:
No luck. Here's the prime 11:
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
is approximately . . .
Because 1039 has no prime divisors less than or
equal ,
it must be prime. Thus we now have the entire factorization:
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.