Results 1 to 3 of 3

Math Help - GCD proof help

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    11

    GCD proof help

    Hi everyone, not sure how to do this question.

    If gcd(m,n)=1 and p|mq and p|nq then prove that p|q.

    Thanks in advance for any help guys.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: GCD proof help

    Quote Originally Posted by alexgeek101 View Post
    Hi everyone, not sure how to do this question.

    If gcd(m,n)=1 and p|mq and p|nq then prove that p|q.

    Thanks in advance for any help guys.
    gcd(m,n)=1 \Rightarrow \exists x,y \in \mathbb{Z} \, such \, that \, mx+ny=1 \Rightarrow mqx+nqy=q.
     p|LHS \Rightarrow p|RHS.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433

    Re: GCD proof help

    If you're working over the integers, here's the intuition: since p|mq, you can imagine taking all the prime factors of p, and dividing as many of them as possible into q, with the remaining ones dividing m. Likewise, the remaining ones divide n, since p|nq. But (m,n)=1, so in fact all the factors of p can be divided into q.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 12:13 PM
  2. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum