Difference between revisions of "Euclid's Lemma"
(deleted fallacious proof; mentioned converse in proof; edited a little) |
m (→Proof of Euclid's Lemma) |
||
| Line 8: | Line 8: | ||
Without loss of generality, suppose <math> \gcd(p,a)=1</math> (otherwise we are done). By [[Bezout's Lemma]], there exist integers such that <math>x,y</math> such that <math>px+ay=1</math>. Hence <math>b(px+ay)=b</math> and <math>pbx+aby=b</math>. Since <math> p\mid p</math> and <math> p \mid ab </math> (by hypothesis), <math>p \mid pbx + aby =b</math>, as desired. | Without loss of generality, suppose <math> \gcd(p,a)=1</math> (otherwise we are done). By [[Bezout's Lemma]], there exist integers such that <math>x,y</math> such that <math>px+ay=1</math>. Hence <math>b(px+ay)=b</math> and <math>pbx+aby=b</math>. Since <math> p\mid p</math> and <math> p \mid ab </math> (by hypothesis), <math>p \mid pbx + aby =b</math>, as desired. | ||
| − | On the other hand, if <math>p>1</math> is not prime, then it must be composite, i.e., <math>p=ab</math>, for integers <math>a,b</math> both greater than 1. Then <math>p\nmid a</math> and <math>p\nmid b</math>. | + | On the other hand, if <math>p>1</math> is not prime, then it must be composite, i.e., <math>p=ab</math>, for integers <math>a,b</math> both greater than 1. Then, <math>p\nmid a</math> and <math>p\nmid b</math>. This completes the proof. |
==See Also== | ==See Also== | ||
Revision as of 03:18, 20 November 2023
Euclid's Lemma is a result in number theory attributed to Euclid. It states that:
A positive integer 
is a prime number if and only if 
implies that 
or 
, for all integers 
and 
.
Proof of Euclid's Lemma
Without loss of generality, suppose 
(otherwise we are done). By Bezout's Lemma, there exist integers such that 
such that 
. Hence 
and 
. Since 
and (by hypothesis), 
, as desired.
On the other hand, if is not prime, then it must be composite, i.e., 
, for integers 
both greater than 1. Then, 
and 
. This completes the proof.
