Euclid's lemma: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Michael Hardy
imported>Michael Hardy
(This proof is at best incomplete and very likely circular; see the talk page.)
Line 2: Line 2:


Euclid's lemma is used in the proof of the [[unique factorization theorem]], which states that a number cannot have more than one prime factorization.
Euclid's lemma is used in the proof of the [[unique factorization theorem]], which states that a number cannot have more than one prime factorization.
==Proof of the lemma==
Let ''a'', ''b'', ''p'' <math>\in\mathbb{Z}</math> with ''p'' prime, and
suppose that ''p'' is a divisor of ''ab'', ''p''|''ab''.
Then there exists an [[integer]] ''n'' such that ''ab = pn''.  But this means that the fraction
:<math>\frac{ab}{p}=n</math>
must be an integer as well.  Now, since ''p'' is prime the [[greatest common divisor]] of ''p'' and ''a'' is either 1 or ''p''.  If it is ''p'' then the proof is complete since ''p''|''a'', so suppose that ''p'' does not divide ''a''.  In this case we write
:<math>a\frac{b}{p}=n\ ,</math>
and since gcd(''a'', ''p'') = 1 and ''n'' is an integer, ''b/p'' must also be an integer, say ''m''.
But then ''b = mp'' so ''p'' divides ''b''.
Therefore in either case we have ''p'' dividing (at least) one of ''a'' and ''b'', and the proof is complete.


[[category:Mathematics Workgroup]]
[[category:Mathematics Workgroup]]

Revision as of 19:38, 3 August 2007

In number theory, Euclid's lemma, named after the ancient Greek geometer and number theorist Euclid of Alexandria, states that if a prime number p is a divisor of the product of two integers, ab, then either p is a divisor of a or p is a divisor of b (or both).

Euclid's lemma is used in the proof of the unique factorization theorem, which states that a number cannot have more than one prime factorization.

Retrieved from "https://citizendium.org/wiki/index.php?title=Euclid%27s_lemma&oldid=268937"