How to find the number of proper divisors of an integer and other cute related questions

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, 441000 = (2^{3})(3^{2})(5^{3})(7^{2}). Any divisor, proper or improper, of the given number must be of the form (2^{a})(3^{b})(5^{c})(7^{d}) where 0 \leq a \leq 3, 0 \leq b \leq 2, 0 \leq c \leq 3, and 0 \leq d \leq 2. 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 (4)(3)(4)(3)-2=142.

Question 2:

Count the proper divisors of an integer N whose prime factorization is: N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} p_{3}^{\alpha_{3}}\ldots p_{k}^{\alpha_{k}}

Solution 2:

By using the same reasoning as in previous question, the number of proper divisors of N is (\alpha_{1}+1)(\alpha_{2}+1)(\alpha_{3}+1)\ldots (\alpha_{k}+1)-2, 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 m>1, n>1, and the GCD of m and n is 1.

Solution 3:

Consider the set A = {2^{3}, 3^{2}, 5^{3}, 7^{2}} 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:

A = \{ 2^{3}\} + \{ 3^{2}, 5^{3}, 7^{2}\} = \{3^{2}\}+\{ 2^{3}, 5^{3}, 7^{2}\} = \{ 5^{3}\} + \{ 2^{3}, 3^{2}, 7^{2}\} = \{ 7^{2}\}+\{ 2^{3}, 3^{2}, 5^{3}\},

and A = \{ 2^{3}, 3^{2}\} + \{ 5^{3}, 7^{2}\}=\{ 2^{3}, 5^{3}\} + \{3^{2}, 7^{2} \} = \{ 2^{3}, 7^{2}\} + \{ 3^{2}, 5^{3}\}

Hence, the required answer is 4+3=2^{4-1}+1=7.

Question 4:

Generalize the above problem by showing that any integer has 2^{k-1}-1 factorizations into relatively prime pairs m, n (m>1, n>1).

Solution 4:

Proof by mathematical induction on k:

For k=1, the result holds trivially.

For k=2, we must prove that a set of k distinct elements, Z = \{ a_{1}, a_{2}, a_{3}, \ldots, a_{k-1}, a_{k}\} has 2^{k-1}-1 sets. Now, one partition of Z is

Z = \{ a_{k}\} \bigcup \{ a_{1}, a_{2}, a_{3}, \ldots, a_{k-1}\} \equiv \{ a_{k}\} \bigcup W

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

1 + (2^{k-2})(2)=2^{k-1}-1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.