Factors of product of n distinct primes

Click For Summary

Discussion Overview

The discussion centers on determining the number of positive factors of the product of n distinct prime numbers, with an exploration of the implications when the primes are not distinct. Participants engage in reasoning about the independence of prime factors and the relationship to power sets.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant proposes that the number of positive factors of the product of n distinct prime numbers is 2^n and seeks a proof for this assertion.
  • Another participant explains that each factor can either be divisible by one of the n unique primes or not, suggesting that the independence of these decisions leads to a total of 2^n factors, relating this to the cardinality of the power set.
  • A later reply reinforces the idea of a one-to-one correspondence between the power set of a set of n distinct primes and the set of positive factors.
  • One participant questions the validity of the 2^n result if the primes are not distinct, suggesting that the number of positive factors would be less than that.
  • Another participant responds by clarifying that if the primes are not distinct, the calculation should consider equivalence classes of primes, providing an example to illustrate this point.
  • One participant challenges the reasoning by stating that the logic does not hold for prime powers, indicating a potential misunderstanding in the application of the proposed method.
  • A participant acknowledges the confusion and clarifies their position regarding the distinct and non-distinct cases.

Areas of Agreement / Disagreement

Participants generally agree on the calculation for distinct primes resulting in 2^n factors, but there is disagreement regarding the case of non-distinct primes, leading to multiple competing views on how to approach the problem.

Contextual Notes

The discussion includes assumptions about the definitions of distinct and non-distinct primes, as well as the implications of prime powers on the number of factors, which remain unresolved.

de_brook
Messages
74
Reaction score
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
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...
 
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
 
Yes. Hence the 2^n.
 
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.
 
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|.
 
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.
 
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...
 

Similar threads

Undergrad Fundamental theorem of arithmetic from Jordan-Hölder theorem
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K
An integer n>1 is square-free if and only if?
  • · Replies 13 ·
Replies
13
Views
4K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
Undergrad How to Prove a Congruence Relation for Prime Numbers?
  • · Replies 17 ·
Replies
17
Views
2K
MHB Prove R is a Sub-ring of $\mathbb{Q}$ - Prime $p \in \mathbb{Z}$
  • · Replies 11 ·
Replies
11
Views
2K
High School Probability that 2 distinct integers are divisible by the same number
  • · Replies 9 ·
Replies
9
Views
3K
Undergrad Irreducible polynomials and prime elements
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad P-adic valuation expression for a given natural number
  • · Replies 9 ·
Replies
9
Views
2K