Results 1 to 11 of 11

Math Help - proof

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    84

    proof

    Let m, n and p be integers, with p prime. Prove that if p divides mn then p divides m or p divides n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by leinadwerdna View Post
    Let m, n and p be integers, with p prime. Prove that if p divides mn then p divides m or p divides n.

    In many cases this is jsut the definition of prime number, so: what's the definition you're using?

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by tonio View Post
    In many cases this is jsut the definition of prime number, so: what's the definition you're using?

    Tonio
    Perhaps this is one of the first corollaries of the definition of a prime number, but I haven't seen a prime number defined this way. This problem is called Euclid's Lemma I believe.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2009
    Posts
    84
    the definition of prime number i am using is that is a number whose only divisors are 1 and itself

    how can I prove this without using Bezout's Identy about relative primes.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by leinadwerdna View Post
    the definition of prime number i am using is that is a number whose only divisors are 1 and itself
    tonio appears to be busy, so I'll give you a link to look at. This is a standard proof of this problem, but uses another lemma which you may not have covered and be allowed to use.

    Euclid's lemma - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by tonio View Post
    In many cases this is jsut the definition of prime number, so: what's the definition you're using?

    Tonio
    I was mistaken, my apologies. I have found multiple sources defining prime numbers this way.

    Assume p|mn, thus for some integer q, pq=mn. By definition of prime, the gcd(m,p)=1 or gcd(m,p)=p. If gcd(m,p)=p, then p|m and the desired result is shown. If gcd(m,p)=1, then p|gcd(m,p)n. See here for a proof.

    Here is the whole proof I outlined above. I'm sorry to link so much but I don't really know what you can use or not so I don't want to type out a bunch of stuff for nothing. Does the above info help?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by leinadwerdna View Post
    the definition of prime number i am using is that is a number whose only divisors are 1 and itself.
    Quote Originally Posted by Jameson View Post
    I was mistaken, my apologies. I have found multiple sources defining prime numbers this way.
    There are multiple sources that use that definition. I even hear Keith Devlin use it.
    But nonetheless, strictly speaking it is incorrect.
    That definition makes 1 a prime number.
    The number 1 has only 1 and itself as divisors.

    So I think that the correct wording is: A positive integer is prime if and only if it has exactly two divisors.
    You understand that 1 has only one divisor: itself.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Ok, ok, I get what you mean. All that is needed is to add "distinct" to that definition to make it such that 1 isn't prime.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Jameson View Post
    Ok, ok, I get what you mean. All that is needed is to add "distinct" to that definition to make it such that 1 isn't prime.
    Well 16 has two distinct divisors: {1,16}, or {2,8} or {4,16}.
    So we need the word exactly.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Mar 2009
    Posts
    84
    p|gcd(m,p)n.

    how do you prove this step in your proof jameson
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by leinadwerdna View Post
    p|gcd(m,p)n.

    how do you prove this step in your proof jameson
    Look at the link I gave. It comes down to using the fact that if gcd(a,b)=d given a|bc then there exist integers x,y such that ax+by=d. This is just basically saying that if a and b are both multiples of d, then some linear combination of them can result in d. Look at the link for the next steps.

    I don't know if you can use this though, or if you are supposed to do it another way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  4. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 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, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum