factors of product of n distinct primes


by de_brook
Tags: distinct, factors, primes, product
de_brook
de_brook is offline
#1
Mar9-09, 06:48 PM
P: 74
What will be the numbers of positive factors of product of n distinct prime numbers?

i was able to get 2^n. pls how do i prove this?
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
csprof2000
csprof2000 is offline
#2
Mar9-09, 07:02 PM
P: 288
In any factor you come up with, it will either be divisible by one of the n unique primes, or not. Whether or not your particular factor is divisible by a prime is independent of whether your factor is divisible by another prime; so how many ways can you make a factor if you have to make n yes/no decisions?

Think about it as a prime factor set. You're finding the cardinality of the power set...
de_brook
de_brook is offline
#3
Mar9-09, 07:09 PM
P: 74
Quote Quote by csprof2000 View Post
In any factor you come up with, it will either be divisible by one of the n unique primes, or not. Whether or not your particular factor is divisible by a prime is independent of whether your factor is divisible by another prime; so how many ways can you make a factor if you have to make n yes/no decisions?

Think about it as a prime factor set. You're finding the cardinality of the power set...
you mean there will exist a 1-1 correspondence between power set of a set A with cardinality n and the set of positive factors of the product of n primes

csprof2000
csprof2000 is offline
#4
Mar9-09, 10:03 PM
P: 288

factors of product of n distinct primes


Yes. Hence the 2^n.
de_brook
de_brook is offline
#5
Mar10-09, 03:03 AM
P: 74
Quote Quote by csprof2000 View Post
Yes. Hence the 2^n.
what about if the primes are not distinct? i don't the number of positive factor will be 2^n, it will be less than that.
csprof2000
csprof2000 is offline
#6
Mar10-09, 06:19 AM
P: 288
You said "distinct primes" in your first post. So your answer - and my reason - were correct.

If you are now changing the question, that's fine.

If the primes are not distinct, all you need to do is to calculate the number of equivalence classes of primes. For instance,

P = {2, 2, 3, 3, 3, 5, 7, 7, 11, 11, 11, 11}

=>

P' = { {2, 2}, {3, 3, 3}, {5}, {7, 7}, {11, 11, 11, 11} }

Then the number of factors is 2^|P'| = 32.

If the primes are all unique, then clearly |P'| = |P|.
matt grime
matt grime is offline
#7
Mar10-09, 07:55 AM
Sci Advisor
HW Helper
P: 9,398
That is clearly incorrect: just consider a prime power. By your logic it always has exactly 2 divisors.

Google for Euler's phi (or totient) function.
csprof2000
csprof2000 is offline
#8
Mar10-09, 10:43 AM
P: 288
Oh, yeah. Sorry, I was still thinking in terms of the first question.

Matt Grime is correct for the second question. I was for the first one. Sorry for the confusion...


Register to reply

Related Discussions
Distinct Eigenvalues Precalculus Mathematics Homework 4
[SOLVED] Electrolysis, factors=>n(product) Biology, Chemistry & Other Homework 3
distinct primes Calculus & Beyond Homework 1
Certain product sequences and their factors Linear & Abstract Algebra 1
Product of Primes! Programmers! General Math 15