Factors of product of n distinct primes

In summary, the number of positive factors of the product of n distinct prime numbers can be calculated as 2^n. This is because for any factor, it will either be divisible by one of the n unique primes or not, and the decision for each prime is independent. If the primes are not distinct, the number of factors can be determined by calculating the number of equivalence classes of primes. This can be done using Euler's phi (or totient) function. Otherwise, if the primes are all unique, the number of factors will be the same as the number of primes.
  • #1
de_brook
74
0
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?
 
Last edited:
Physics news on Phys.org
  • #2
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...
 
  • #3
csprof2000 said:
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
 
  • #4
Yes. Hence the 2^n.
 
  • #5
csprof2000 said:
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.
 
  • #6
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|.
 
  • #7
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.
 
  • #8
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...
 

1. What is the definition of "Factors of product of n distinct primes"?

The factors of product of n distinct primes refer to the numbers that can be multiplied together to get the product of n distinct prime numbers. For example, if n=3, the factors of the product of 2, 3, and 5 would be 1, 2, 3, 5, 6, 10, and 30.

2. How do you find the factors of the product of n distinct primes?

To find the factors of the product of n distinct primes, you can use the prime factorization method. First, find the prime factorization of the product. Then, list out all the possible combinations of the prime factors. Finally, multiply these combinations to get the factors.

3. Can the factors of the product of n distinct primes be negative numbers?

No, the factors of the product of n distinct primes are always positive numbers. This is because prime numbers are only divisible by 1 and themselves, and any negative number would result in a non-prime factor.

4. What is the relationship between the number of factors and the number of distinct prime factors?

The number of factors of the product of n distinct primes is equal to 2^n, where n is the number of distinct prime factors. In other words, the number of factors increases exponentially as the number of distinct prime factors increases.

5. Are there any real-world applications of factors of product of n distinct primes?

Yes, the concept of factors of product of n distinct primes is used in cryptography and security systems. Prime factorization is a vital tool in the creation of secure encryption algorithms and in breaking them.

Similar threads

  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
877
  • Linear and Abstract Algebra
Replies
3
Views
774
  • Linear and Abstract Algebra
Replies
9
Views
2K
  • General Math
Replies
3
Views
529
  • Linear and Abstract Algebra
Replies
2
Views
761
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
Back
Top