# Thread: some confusion on wording of Euclid's Lemma

1. ## 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.

2. ## Re: some confusion on wording of Euclid's Lemma

Originally Posted by oblixps
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

3. ## 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.