## 1.4   Counting Divisors

The applet below takes an integer n as input, and computes d(n), the number of positive divisors of n. Here's an example:

Your browser does not support java.

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, where p is a prime number. For instance, let n = 13. The applet below will generate a list of positive divisors and compute d(n):

Your browser does not support java.

#### 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 states d(n) for n = p, where p is 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 = pa, where p is a prime and a is a positive integer.

Hints: When doing computational experiments, select a small prime p and then increment the value of a by 1. Also, note that when a = 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, where p and q are distinct primes. (If p = q, then we would be in the situation covered in Research Question 3.) What is d(n) in this case? Let's try an experiment, taking n = 3 · 7:

Your browser does not support java.

#### Research Question 4

Select different primes p and q, and repeat the above experiment: Compute the list of positive divisors for n = pq, and compute d(n). When you have enough data, form a conjecture that states d(n) for n = pq, where p and q are 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 = paqb, where p and q are primes and a and b are 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 of p and q, and make simple variations in the exponents a and b. 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 p1, p2, . . . , pk are distinct primes and a1, a2, . . . , ak are positive integers. What is 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) for

n = ,

where p1, p2, . . . , pk are distinct primes and a1, a2, . . . , ak are positive integers.

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 n prime, and then n a 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 = pa, 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.

#### Exercise 2

Suppose that n =. What are the positive divisors of n in terms of their prime-power factorizations?

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