Euclid's lemma
Encyclopedia
In mathematics
, Euclid's lemma (Greek
) is an important lemma
regarding divisibility
and prime number
s. In its simplest form, the lemma states that a prime number that divides a product
of two integer
s must divide one of the two integers. This key fact requires a surprisingly sophisticated proof
(using Bézout's identity
), and is a necessary step in the standard proof of the fundamental theorem of arithmetic
.
Euclid's lemma (also known as Euclid
's first theorem
) appears as proposition 30 in Book VII of Euclid's Elements
. In modern notation:
Here
means “divides”; that is, 
if 
is a divisor of 
.
In modern mathematics, “Euclid's lemma” is often used to refer to the following generalization of this statement:
This statement reduces to Euclid's proposition 30 in the case where
is prime.
The standard proof of Euclid's lemma uses Bézout's identity
. This states that, for any relatively prime integers x and y, there exist integers r and s such that
To prove Euclid's lemma, suppose that p is a prime factor of ab, but that p is not a factor of a.
Then p and a must be relatively prime, so there exist integers r and s such that
Multiplying through by b gives
Now, the first term on the left is clearly a multiple
of p. Since p divides ab, the second term on the left hand side of the equation is also a multiple of p. It follows that b is a multiple of p, so p divides b. This proves that p is always either a divisor of a, a divisor of b, or both. Q.E.D.
http://books.google.com/books?id=r_HuAAAAMAAJ&q=Euclid+Lemma&dq=Euclid+Lemma&hl=en&ei=au9aTaCMEo7EsAOa47WeCg&sa=X&oi=book_result&ct=book-thumbnail&resnum=1&ved=0CCwQ6wEwAA
We wish to prove the following statement for any nonnegative integers p, a and b, with p prime (and positive):
(*) if p divides ab, then p divides a and/or p divides b.
In order to achieve a contradiction, assume the theorem is false. Then there is some smallest prime number p as above for which there are a and b making (*) false. That is, p divides ab but divides neither a nor b. For this choice of p, pick a and b making (*) false, with a as small as possible.
Note that since we choose a and p as small as possible, the theorem (*) has to be true for all smaller numbers. This fact will be used in this proof.
First we see that a > 1. If a = 0, then p divides a, making (*) true, a contradiction. If a = 1, then ab = b. Since p divides ab by assumption, it also divides b, again contradicting the choice of a and b. Therefore a > 1.
Next we prove a is prime. Otherwise, we could write a = cd, with 1 < c,d < a. Since c < a, and a was chosen as small as possible, (*) is true for the numbers p, a′ and b′, where a′ = c and b′ = db. Now p divides ab = cdb, so by (*), p either divides c or divides
db. If p divided c, it would also divide cd = a, contradicting the choice of a. Therefore p divides db. Since d < a, we may again apply (*) to conclude that p either divides d or divides b. p does not divide b, by hypothesis. But again, if p divided d, it would also divide cd = a, contradicting the choice of a. Thus the assumption that a was not prime was impossible.
Now we prove that a < p. Otherwise, write a′ = a - p ≥ 0. Then a′b = (a - p)b = ab - pb. Since p divides ab by hypothesis, and clearly also divides pb, it must divide their difference, which is a′b. Since a′ < a, and a was chosen as small as possible, (*) must be true for p, a′ and b. Therefore p divides a′ and/or p divides b. But since by assumption p does not divide b, p must divide a′. Therefore p divides a′ + p = a, a contradiction.
Since a is prime, a < p, and p was the smallest prime number for which the theorem was false, we conclude that the theorem is true for a. That is, if a divides any product cd, then it divides one of the factors c or d.
Now since p divides ab, we can write ab = cp for some number c. This shows that a divides cp. Since the theorem is true for a, either a divides c or a divides p. But a cannot divide p, since p is prime and 1 < a < p. Therefore a divides c, so we can write c = ak for some k. Thus ab = cp = akp. Hence, dividing by a, we find b = kp, whence p divides b, contradicting the choice of b. This shows that the theorem is true for p, contradicting the choice of p. In conclusion, the theorem must be true.
,
,
and
.
Then either
or
.
Obviously, in this case, 7 divides 14 (x = 2).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Euclid's lemma (Greek
Greek language
Greek is an independent branch of the Indo-European family of languages. Native to the southern Balkans, it has the longest documented history of any Indo-European language, spanning 34 centuries of written records. Its writing system has been the Greek alphabet for the majority of its history;...
) is an important lemma
Lemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
regarding divisibility
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
and prime number
Prime number
A prime number 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 called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s. In its simplest form, the lemma states that a prime number that divides a product
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
of two integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s must divide one of the two integers. This key fact requires a surprisingly sophisticated proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
(using Bézout's identity
Bézout's identity
In number theory, Bézout's identity for two integers a, b is an expressionwhere x and y are integers , such that d is a common divisor of a and b. Bézout's lemma states that such coefficients exist for every pair of nonzero integers...
), and is a necessary step in the standard proof of the fundamental theorem of arithmetic
Fundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
.
Euclid's lemma (also known as Euclid
Euclid
Euclid , fl. 300 BC, also known as Euclid of Alexandria, was a Greek mathematician, often referred to as the "Father of Geometry". He was active in Alexandria during the reign of Ptolemy I...
's first theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
) appears as proposition 30 in Book VII of Euclid's Elements
Euclid's Elements
Euclid's Elements is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria c. 300 BC. It is a collection of definitions, postulates , propositions , and mathematical proofs of the propositions...
. In modern notation:
- If
is prime and 
then 
and/or 
.
Here
means “divides”; that is, if is a divisor of .In modern mathematics, “Euclid's lemma” is often used to refer to the following generalization of this statement:
- If
and 
and 
are relatively prime, then 
.
This statement reduces to Euclid's proposition 30 in the case where
is prime.The standard proof of Euclid's lemma uses Bézout's identity
Bézout's identity
In number theory, Bézout's identity for two integers a, b is an expressionwhere x and y are integers , such that d is a common divisor of a and b. Bézout's lemma states that such coefficients exist for every pair of nonzero integers...
. This states that, for any relatively prime integers x and y, there exist integers r and s such that
To prove Euclid's lemma, suppose that p is a prime factor of ab, but that p is not a factor of a.
Then p and a must be relatively prime, so there exist integers r and s such that
Multiplying through by b gives
Now, the first term on the left is clearly a multiple
Multiple (mathematics)
In mathematics, a multiple is the product of any quantity and an integer. In other words, for the quantities a and b, we say that b is a multiple of a if b = na for some integer n , which is called the multiplier or coefficient. If a is not zero, this is equivalent to saying that b/a is an integer...
of p. Since p divides ab, the second term on the left hand side of the equation is also a multiple of p. It follows that b is a multiple of p, so p divides b. This proves that p is always either a divisor of a, a divisor of b, or both. Q.E.D.
Q.E.D.
Q.E.D. is an initialism of the Latin phrase , which translates as "which was to be demonstrated". The phrase is traditionally placed in its abbreviated form at the end of a mathematical proof or philosophical argument when what was specified in the enunciation — and in the setting-out —...
http://books.google.com/books?id=r_HuAAAAMAAJ&q=Euclid+Lemma&dq=Euclid+Lemma&hl=en&ei=au9aTaCMEo7EsAOa47WeCg&sa=X&oi=book_result&ct=book-thumbnail&resnum=1&ved=0CCwQ6wEwAA
Alternate proof without Bézout's identity
This proof does not use Bézout's identity, or even Euclidean division.We wish to prove the following statement for any nonnegative integers p, a and b, with p prime (and positive):
(*) if p divides ab, then p divides a and/or p divides b.
In order to achieve a contradiction, assume the theorem is false. Then there is some smallest prime number p as above for which there are a and b making (*) false. That is, p divides ab but divides neither a nor b. For this choice of p, pick a and b making (*) false, with a as small as possible.
Note that since we choose a and p as small as possible, the theorem (*) has to be true for all smaller numbers. This fact will be used in this proof.
First we see that a > 1. If a = 0, then p divides a, making (*) true, a contradiction. If a = 1, then ab = b. Since p divides ab by assumption, it also divides b, again contradicting the choice of a and b. Therefore a > 1.
Next we prove a is prime. Otherwise, we could write a = cd, with 1 < c,d < a. Since c < a, and a was chosen as small as possible, (*) is true for the numbers p, a′ and b′, where a′ = c and b′ = db. Now p divides ab = cdb, so by (*), p either divides c or divides
db. If p divided c, it would also divide cd = a, contradicting the choice of a. Therefore p divides db. Since d < a, we may again apply (*) to conclude that p either divides d or divides b. p does not divide b, by hypothesis. But again, if p divided d, it would also divide cd = a, contradicting the choice of a. Thus the assumption that a was not prime was impossible.
Now we prove that a < p. Otherwise, write a′ = a - p ≥ 0. Then a′b = (a - p)b = ab - pb. Since p divides ab by hypothesis, and clearly also divides pb, it must divide their difference, which is a′b. Since a′ < a, and a was chosen as small as possible, (*) must be true for p, a′ and b. Therefore p divides a′ and/or p divides b. But since by assumption p does not divide b, p must divide a′. Therefore p divides a′ + p = a, a contradiction.
Since a is prime, a < p, and p was the smallest prime number for which the theorem was false, we conclude that the theorem is true for a. That is, if a divides any product cd, then it divides one of the factors c or d.
Now since p divides ab, we can write ab = cp for some number c. This shows that a divides cp. Since the theorem is true for a, either a divides c or a divides p. But a cannot divide p, since p is prime and 1 < a < p. Therefore a divides c, so we can write c = ak for some k. Thus ab = cp = akp. Hence, dividing by a, we find b = kp, whence p divides b, contradicting the choice of b. This shows that the theorem is true for p, contradicting the choice of p. In conclusion, the theorem must be true.
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,,,and
.Then either
or
.Obviously, in this case, 7 divides 14 (x = 2).