Difference between revisions of "Euclid's Lemma"

Latest 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 $p>1$ is a prime number if and only if $p \mid ab$ implies that $p \mid a$ or $p\mid b$ , for all integers $a$ and $b$ .

Proof of Euclid's Lemma

Without loss of generality, suppose $\gcd(p,a)=1$ (otherwise we are done). By Bezout's Lemma, there exist integers such that $x,y$ such that $px+ay=1$ . Hence $b(px+ay)=b$ and $pbx+aby=b$ . Since $p\mid p$ and $p \mid ab$ (by hypothesis), $p \mid pbx + aby =b$ , as desired.

On the other hand, if $p>1$ is not prime, then it must be composite, i.e., $p=ab$ , for integers $a,b$ both greater than 1. Then, $p\nmid a$ and $p\nmid b$ .

This completes the proof.

@@ Line 1: / Line 1: @@
-In [[Number Theory]], the result that
+'''Euclid's Lemma''' is a result in [[number theory]] attributed to [[Euclid]]. It states that:
-A positive integer <math>p</math> is a [[prime number]] if and only iff <math>p|ab \Longrightarrow p|a</math> or <math> p|b </math>
+A positive integer <math>p>1</math> is a [[prime number]] if and only if <math>p \mid ab</math> implies that <math>p \mid a</math> or <math>p\mid b</math>, for all [[integer]]s <math>a</math> and <math>b</math>.
-is attributed to [[Euclid]]
-{{stub}}
+== Proof of Euclid's Lemma ==
+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.
+==See Also==
+* [[Fundamental theorem of arithmetic]]
+* [[Euclid]]
+* [[Number theory]]
+[[Category:Number theory]]

Page

Toolbox

Search

Difference between revisions of "Euclid's Lemma"

Latest revision as of 03:18, 20 November 2023

Proof of Euclid's Lemma

See Also