The applet below takes an integer

nas input, and computesd(n), the number of positive divisors ofn. Here's an example:In this section, we shall perform some experiments to learn how the number of positive divisors of a given integer can be determined from the factorization of the integer. We'll do this by starting with fairly simple cases and building up to more complicated situations. Along the way, a pattern should (hopefully!) emerge.

Let us begin with the simplest case: Suppose that

n=p, wherepis a prime number. For instance, letn= 13. The applet below will generate a list of positive divisors and computed(n):

## Research Question 2

Select different primes, and repeat the above experiment: Compute the divisor list, and then compute

d(n). When you have enough data, form a conjecture that statesd(n) forn=p, wherepis prime. (It probably won't take much data for you to form a conjecture!) Then prove your conjecture.

## Research Question 3

Repeat Research Question 2, but this time for

n=p, where^{a}pis a prime andais a positive integer.

Hints:When doing computational experiments, select a small primepand then increment the value ofaby 1. Also, note that whena= 1, you revert to the case covered by Research Question 2. Thus, whatever your conjecture, it must be consistent with your results from the preceding Research Question.Now suppose that

n=pq, wherepandqare distinct primes. (Ifp=q, then we would be in the situation covered in Research Question 3.) What isd(n) in this case? Let's try an experiment, takingn= 3 · 7:

## Research Question 4

Select different primes

pandq, and repeat the above experiment: Compute the list of positive divisors forn=pq, and computed(n). When you have enough data, form a conjecture that statesd(n) forn=pq, wherepandqare distinct primes.

Note:We will no longer state that you should prove your conjecture, since you should always prove (or try to prove) all conjectures made in this course.

## Research Question 5

Repeat Research Question 4, but this time take

n=p, where^{a}q^{b}pandqare primes andaandbare positive integers.

Hints:When doing your numerical experiments, it will make life easier if you are systematic. (In fact, systematic experimentation is the hallmark of good scientific work.) You might try starting with fixed values ofpandq, and make simple variations in the exponentsaandb. Note also that the previous Research Questions are all special cases of this one. Therefore, your conjecture in this case must be consistent with your previous results.All of the earlier work has been leading up to the most general case of all. Suppose that

n=_{},where

p_{1},p_{2}, . . . ,pare distinct primes and_{k}a_{1},a_{2}, . . . ,aare positive integers. What is_{k}d(n) in this case? On the basis of your earlier investigations, you may not need any additional experimentation to form a conjecture. On the other hand, there is no harm in further experimentation, so feel free to do more if you wish.

## Research Question 6

Form a conjecture that states

d(n) forn=_{},where

p_{1},p_{2}, . . . ,pare distinct primes and_{k}a_{1},a_{2}, . . . ,aare positive integers._{k}It may seem that we led to this formula in an inefficient manner; why not go for the whole formula at once? As you may have discovered along the way, it can help a great deal to work up to the general case through various special cases. In number theory, starting with cases such as

nprime, and thenna prime power, and so on, is a standard progression of study. Keep this in mind for later investigations in the course.An important part of proving your conjectures for Research Questions 2 through 6 is being able to list the positive divisors of an integer of the forms

n=p,n=pq,n=p, and so on. The basic idea of listing these divisors was implicit in the section above where we derived a formula for the greatest common divisor of two integers in terms of their factorizations. In the next exercise, you should formulate the statement precisely.^{a}

## Exercise 2

Suppose that

n=_{}. What are the positive divisors ofnin terms of their prime-power factorizations?

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

Copyright © 2001 by W. H. Freeman and Company