**Question 1:**

Find the number of proper divisors of 441000. (A proper divisor of a positive integer n is any divisor other than 1 and n):

**Solution 1:**

Any integer can be uniquely expressed as the product of powers of prime numbers (Fundamental theorem of arithmetic); thus, . Any divisor, proper or improper, of the given number must be of the form where , , , and . In this paradigm, the exponent a can be chosen in 4 ways, b in 3 ways, c in 4 ways, d in 3 ways. So, by the product rule, the total number of proper divisors will be .

**Question 2:**

Count the proper divisors of an integer N whose prime factorization is:

**Solution 2:**

By using the same reasoning as in previous question, the number of proper divisors of N is , where we deduct 2 because choosing all the factors means selecting the given number itself, and choosing none of the factors means selecting the trivial divisor 1.

**Question 3:**

Find the number of ways of factoring 441000 into 2 factors, m and n, such that , and the GCD of m and n is 1.

**Solution 3:**

Consider the set associated with the prime factorization of 441000. It is clear that each element of A must appear in the prime factorization of m or in the prime factorization of n, but not in both. Moreover, the 2 prime factorizations must be composed exclusively of elements of A. It follows that the number of relatively prime pairs m, n is equal to the number of ways of partitioning A into 2 unordered nonempty, subsets (unordered as mn and nm mean the same factorization; recall the fundamental theorem of arithmetic).

The possible unordered partitions are the following:

,

and

Hence, the required answer is .

**Question 4:**

Generalize the above problem by showing that any integer has factorizations into relatively prime pairs m, n ().

**Solution 4:**

Proof by mathematical induction on k:

For , the result holds trivially.

For , we must prove that a set of k distinct elements, has sets. Now, one partition of Z is

All the remaining partitions may be obtained by first partitioning W into two parts — which, by the induction hypothesis, can be done in ways — and then, including in one part or other — which can be done in 2 ways. By the product rule, the number of partitions of Z is therefore

. QED.

*Remarks: Question 1 can be done by simply enumerating or breaking it into cases. But, the last generalized problem is a bit difficult without the refined concepts of set theory, as illustrated; and of course, the judicious use of mathematical induction is required in the generalized case. *

Cheers,

Nalin Pithwa.