Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the expression for the number of distinct greatest common divisors possible for the number $N$? Let us say that $N$ is composed of 4 prime numbers $N = p_3 p_2 p_1 p_0$. Now if $p_i$ are all unique, I think the answer is $$ C = \sum_{i = 0}^4 {4 \choose i} $$ I can also tell that there are less than this if a prime repeats, say $p_3 = p_2$ (by enumerating by hand).

share|improve this question
    
what do you mean by gcd of a number? –  user17762 Jan 6 '13 at 1:31
2  
Do you just mean 'divisors'? –  anon Jan 6 '13 at 1:33
    
    
I meant 'divisors' but my original issue was trying to calculate the maximum possible number of greatest common divisors between a number $N$ and a different positive integer (knowing nothing of this second integer), which turns out to be equivalent to asking the number of distinct positive divisors of $N$, or so it appears from the answers. –  dcdo Jan 6 '13 at 13:54
add comment

2 Answers

up vote 2 down vote accepted

You are essentially asking for the number of positive divisors of $N$. If $$N=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n},$$ where the $p_i$ are distinct primes, the number of positive divisors of $N$ is $$(a_1+1)(a_2+1)\cdots(a_n+1).$$

For to make a positive divisor of $N$, we first sit in front of the prime $p_1$, and decide how many copies of $p_1$ the positive divisor will get. Our choices are $0$, $1$, and so on up to $a_1$, a total of $a_1+1$ choices. Now we sit in front of $p_2$, and decide on how many copies of $p_2$ the divisor will get. There are $a_2+1$ choices. And so on.

The result uses the fact that any positive integer has an essentially unique representation as a product of prime powers.

share|improve this answer
add comment

Assuming you just mean "number of divisors" rather than "common divisors", then the number is just $16 = 2^4$, which can be seen from the fact that each subset of $\{p_0, p_1, p_2, p_3\}$ give rise to a distinct divisor of their product.

Your expression has the same value, as can be seen by expanding $(1+1)^4$ by the binomial theorem.

In the general case with $N$ distinct prime factors, you get the answer $2^N$ by exactly the same process.

If you have some repeated factors then you should look at the answer provided by André Nicolas, or look up Divisor Function on Wikipedia.

Note that to answer your question about the greatest number of distinct divisors of $N$, the greatest number will always be attained when all the prime factors of $N$ are distinct, since if they are not distinct, then some of the subsets of $\{p_0, p_1, \dots,p_n\}$ will give rise to the same divisors of $N$.

For example, if $N=pq$ then the subsets of $\{p,q\}$ are $\emptyset, \{p\}, \{q\}, \{p,q\}$ leading to the factors $1, p, q, pq$, whereas if $p=q$, (so that $N=p^2$) then the factors are $1, p, p, p^2$ which are not all distinct, so you get 3 factors instead of the maximum of 4.

share|improve this answer
1  
You should do the general case, instead of only the specific case used to explain the problem. –  Calvin Lin Jan 6 '13 at 1:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.