## escolas one year ago Prove that for two distinct primes p and q, if p|n and q|n, then (pq)|n.

1. myininaya

p|n => pa=n for some integer a q|n => qb=n for some integer b we want to show pqk=n for some integer k we also have that p and q are two distinct primes if we were to give the prime factorization for n it would look something like p*q*some other prime integers possibly

2. escolas

And we know that a and b have prime factorizations as well, so we could say that a and b are some product of primes and then that n^2 is pq times some other primes, but how do we know that pq isn't larger than n?

3. escolas

Oh, is it because if p and q both divide n then they are both part of n? Kinda an Euler's Totient type thing?

4. myininaya

Yeah since both p and q divide n then we know the prime factorization for n=p*q(some other primes possibly) For example: Let n=972 n=3(324)=2(3)(162)=2^2(3)(81)=2^2*3^5=2*3*(2*3^4) 2|972 => 2a=972 3|972 => 3b=972 But as we can see in the prime factorization we also have 2*3*k=n

5. escolas

Thanks, that makes a lot of sense. Much more clear now.

6. Zarkon

IF you want a more rigorous way you can do the following: since p and q are distinct primes then theie gcd is 1 and so they can be written as a linear combination $\alpha p+\beta q=1$ and using the notation from above $$n=ap$$ and $$n=bq$$ we have $n=n\cdot 1=n(\alpha p+\beta q)$ $=n\alpha p+n\beta q=bq\alpha p+ap\beta q$ $=(b\alpha+a\beta)pq$ so $$n$$ is an integer multiple of $$pq$$. Thus $pq|n$