Euclid's lemma: Difference between revisions
imported>Michael Underwood No edit summary |
mNo edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | |||
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 [[multiplication|product]] of two [[integer]]s, ''ab'', then either ''p'' is a divisor of ''a'' or ''p'' is a divisor of ''b'' (or both). | 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 [[multiplication|product]] of two [[integer]]s, ''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. | 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 | ==Proof== | ||
In order to prove Euclid's lemma we will first prove another, unnamed, lemma that will become useful later. | |||
This additional lemma is | |||
'''Lemma 1:''' Suppose ''p'' and ''q'' are [[relatively prime]] integers and that ''p''|''kq'' for some integer ''k''. Then ''p''|''k''. | |||
'''Proof:''' Because ''p'' and ''q'' are relatively prime, the [[Euclidean Algorithm]] tells us that | |||
there exist integers ''r'' and ''s'' such that 1=gcd(''p'',''q'')=''rp''+''sq''. | |||
Next, since ''p''|''kq'' there exists some integer ''n'' such that ''np=kq''. Now write | |||
: ''k''=(''rp''+''sq'')''k'' = ''rpk'' + ''s''(''kq'') = ''rpk'' + ''snp'' = ''p''(''rk''+''sn''). | |||
Since ''rk''+''sn'' is an integer, this shows that ''p''|''k'' as desired. | |||
Now we can prove Euclid's lemma. | |||
Let ''a'', ''b'', ''p'' <math>\in\mathbb{Z}</math> with ''p'' prime, and | Let ''a'', ''b'', ''p'' <math>\in\mathbb{Z}</math> with ''p'' prime, and | ||
suppose that ''p'' is a divisor of ''ab'', ''p''|''ab''. | suppose that ''p'' is a divisor of ''ab'', ''p''|''ab''. | ||
Now let ''g''=gcd(''a'',''p''). Since ''p'' is prime and ''g'' divides it, then either ''g''=''p'' or ''g''=1. | |||
'' | In the first case, ''p'' divides ''a'' by the definition of the gcd, so we are done. | ||
In the second case we have that ''a'' and ''p'' are relatively prime and that ''p''|''ba'' so by the Lemma 1, | |||
''p'' divides ''b''. | |||
Thus in either case ''p'' divides (at least) one of ''a'' and ''b''. | |||
Note that it is of course possible for ''p'' to divide both ''a'' and ''b'', the simplest example of which is | |||
the case ''a''=''b''=''p''. | |||
[[category:Mathematics Workgroup]] | [[category:Mathematics Workgroup]][[Category:Suggestion Bot Tag]] | ||
Latest revision as of 06:00, 14 August 2024
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.
Proof
In order to prove Euclid's lemma we will first prove another, unnamed, lemma that will become useful later. This additional lemma is
Lemma 1: Suppose p and q are relatively prime integers and that p|kq for some integer k. Then p|k.
Proof: Because p and q are relatively prime, the Euclidean Algorithm tells us that there exist integers r and s such that 1=gcd(p,q)=rp+sq. Next, since p|kq there exists some integer n such that np=kq. Now write
- k=(rp+sq)k = rpk + s(kq) = rpk + snp = p(rk+sn).
Since rk+sn is an integer, this shows that p|k as desired.
Now we can prove Euclid's lemma. Let a, b, p with p prime, and suppose that p is a divisor of ab, p|ab. Now let g=gcd(a,p). Since p is prime and g divides it, then either g=p or g=1. In the first case, p divides a by the definition of the gcd, so we are done. In the second case we have that a and p are relatively prime and that p|ba so by the Lemma 1, p divides b. Thus in either case p divides (at least) one of a and b. Note that it is of course possible for p to divide both a and b, the simplest example of which is the case a=b=p.
