Prove that for two distinct primes p and q, if p|n and q|n, then (pq)|n.

Question

myininaya · Answer

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

anonymous · Answer

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?

anonymous · Answer

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?

myininaya · Answer

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

anonymous · Answer

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

zarkon · Answer

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$$