Find the number of proper divisors of 441000. (A proper divisor of a positive integer n is any divisor other than 1 and n):
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 .
Count the proper divisors of an integer N whose prime factorization is:
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.
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.
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:
Hence, the required answer is .
Generalize the above problem by showing that any integer has factorizations into relatively prime pairs m, n ().
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
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.