Results 1 to 3 of 3

Math Help - some confusion on wording of Euclid's Lemma

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    249

    some confusion on wording of Euclid's Lemma

    The way i see it written usually is: if a prime number p divides the product of 2 integers a, b then p also divides either a or b.

    however i also see it sometimes written as "... then p also divides either a, b or both.

    it seems that from the first wording "p also divides either a or b" it excludes the possibility of p|a and p|b. even in the proof which uses Bezout's identity, it is assumed that p does not divide one of them and you then show that it must divide the other. this convinces me that p MUST divide one of them. but i feel that this proof is incomplete because it doesn't seem to take into account if it is possible for p to be able to divide both a and b.

    after proving eulclid's lemma using bezout's identity, i know for a fact that p has to divide one of them. so lets say that p|a. then p could either divide b or not divide b. so is the reason that p dividing both a and b could be a possibility is because there is nothing preventing that to be so? maybe i'm reading too far into the statement but the use of the words "either" and "or" seem to force the choices to be ONLY one or the other and NOT both. i am confused on this matter. help clearing this up would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: some confusion on wording of Euclid's Lemma

    Quote Originally Posted by oblixps View Post
    The way i see it written usually is: if a prime number p divides the product of 2 integers a, b then p also divides either a or b.

    however i also see it sometimes written as "... then p also divides either a, b or both.

    it seems that from the first wording "p also divides either a or b" it excludes the possibility of p|a and p|b. even in the proof which uses Bezout's identity, it is assumed that p does not divide one of them and you then show that it must divide the other. this convinces me that p MUST divide one of them. but i feel that this proof is incomplete because it doesn't seem to take into account if it is possible for p to be able to divide both a and b.

    after proving eulclid's lemma using bezout's identity, i know for a fact that p has to divide one of them. so lets say that p|a. then p could either divide b or not divide b. so is the reason that p dividing both a and b could be a possibility is because there is nothing preventing that to be so? maybe i'm reading too far into the statement but the use of the words "either" and "or" seem to force the choices to be ONLY one or the other and NOT both. i am confused on this matter. help clearing this up would be greatly appreciated.
    The word "either" is redundant (as is the "also"):

    It should be worded: For p prime and a and b integers; p divides ab implies that (p divides a) or (p divides b).

    "or" means one or both.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: some confusion on wording of Euclid's Lemma

    moreover, a usual proof of this is to assume that p|ab, but that p does not divide a, and then to show p MUST divide b.

    an example: 7 is prime, we will assume we know this. a simple check shows that 7 divides 1,568, which we can write as 28*56.

    7 divides 28, but that does not preclude it from dividing 56 as well.

    now if p divides "one, or the other, or both", and we know that p does NOT divide "the one" (and so, obviously not both), then it has to divide "the other" for our original statement to be true.

    of course, if p divides "the one", there is nothing to be said about the second factor, p might divide it, it might not. the statemnt "p divides one, or the other, or both" is still true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Applying Euclid's Lemma to a problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 8th 2011, 07:05 PM
  2. Euclid's Lemma Proof by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 7th 2011, 01:25 AM
  3. Replies: 0
    Last Post: May 28th 2009, 09:07 AM
  4. Euclid's lemma and induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 25th 2008, 11:44 PM
  5. Euclid,s division lemma-please help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 7th 2007, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum