Added to Favorites

Related Searches

Euclid's lemma (Greek λῆμμα) is a generalization of Proposition 30 of Book VII of Euclid's Elements. The lemma states that
## Proof of Proposition 30

Say p is a prime factor of ab, but also state that it is not a factor of a.
Therefore, $rp\; =\; ab!$, where r is the other corresponding factor to produce ab.
As p is prime, and also because it is not a factor of a, a and p must be coprime. This means that two integers x and y can be found so that $1\; =\; px\; +\; ay!$ (Bézout's identity). Multiply with b on both sides:## Example

Euclid's lemma in plain language says: If a number N is a multiple of a prime number p, and N = a · b, then at least one of a and b must be a multiple of p. Say,## See also

- If a positive integer divides the product of two other positive integers, and the first and second integers are coprime, then the first integer divides the third integer.

This can be written in notation:

- If n|ab and gcd(n,a) = 1 then n|b.

Proposition 30, also known as Euclid's first theorem, states:

- If a prime number divides the product of two positive integers, then the prime number divides at least one of the positive integers.

- If p|ab then p|a or p|b.

- $b\; =\; b(px\; +\; ay)!$

- $b\; =\; bpx\; +\; bay!$.

We stated previously that $rp\; =\; ab!$, and so:

- $b\; =\; bpx\; +\; rpy!$

- $b\; =\; p(bx\; +\; ry)!$.

Therefore, p is a factor of b. This means that p must always exactly divide either a or b or both. Q.E.D.

- $N\; =\; 42!$,

- $p\; =\; 7!$,

and

- $N\; =\; 14\; cdot\; 3!$.

Then either

- $x\; cdot\; 7\; =\; 14!$

or

- $x\; cdot\; 7\; =\; 3!$.

Obviously, in this case, 7 divides 14 (x = 2).

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday June 02, 2008 at 05:32:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday June 02, 2008 at 05:32:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.