Euclid's lemma

﻿
Euclid's lemma

Euclid's lemma (Greek "polytonic|λῆμμα") is a generalization of Proposition 30 of Book VII of "Euclid's Elements". The lemma states that: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.That can be written as::If "p"|"ab" then "p"|"a" or "p"|"b".Often, proposition 30 is called Euclid's lemma instead of the generalization. A lemma is a "mini" theorem that is proven and used to prove a bigger theorem. Most of the time in mathematics textbooks Euclid's lemma is used to prove the fundamental theorem of arithmetic.

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:

:$b = b\left(px + ay\right)!$

:$b = bpx + bay!$.

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

:$b = bpx + rpy!$

:$b = p\left(bx + ry\right)!$.

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

Example

Euclid's lemma in plain language says: If a number "N" is a multiple of a prime number "p", and "N" = "a" &middot; "b", then at least one of "a" and "b" must be a multiple of "p". Say,

:$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).

ee also

* Euclidean algorithm
* Fundamental theorem of arithmetic

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Euclid — Infobox Scientist name = Euclid image width = caption = birth date = fl. 300 BC residence = Alexandria, Egypt ethnicity = Greek field = Mathematics known for = Euclid s Elements Euclid (Greek: . polytonic|Εὐκλείδης mdash; Eukleidēs), fl. 300 BC,… …   Wikipedia

• Ellis–Nakamura lemma — In mathematics, the Ellis–Nakamura lemma states that if S is a non empty semigroup with a topology such that S is compact and the product is left continuous, then S has an idempotent element p , (that is, with pp = p ).ApplicationsApplying this… …   Wikipedia

• List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

• Proofs of Fermat's little theorem — This article collects together a variety of proofs of Fermat s little theorem, which states that:a^p equiv a pmod p ,!for every prime number p and every integer a (see modular arithmetic). Simplifications Some of the proofs of Fermat s little… …   Wikipedia

• Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

• List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

• Pappus of Alexandria — (Greek polytonic|Πάππος ὁ Ἀλεξανδρεύς) (c. 290 ndash; c. 350) was one of the last great Greek mathematicians of antiquity, known for his Synagoge or Collection (c. 340), and for Pappus s Theorem in projective geometry. Nothing is known of his… …   Wikipedia

• Coprime — In number theory, a branch of mathematics, two integers a and b are said to be coprime (also spelled co prime) or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common …   Wikipedia

• List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

• Divisor — divisible redirects here. For divisibility of groups, see Divisible group. For the second operand of a division, see Division (mathematics). For divisors in algebraic geometry, see Divisor (algebraic geometry). For divisibility in the ring theory …   Wikipedia