Difference between revisions of "Euclid's Lemma"
m (→Proof of Euclid's Lemma) |
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>. This completes the proof. | + | 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== |
Latest revision as of 04: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.