Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

escolas

  • 2 years ago

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

  • This Question is Closed
  1. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  6. Zarkon
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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\]

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy