The proof is already given in the textbook but I tried other way around.

Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,a)=1$ and $\gcd(p,b)=1$. Given that we can construct linear combinations

$sp+ta=1$ together with $up+wb=1$. Multiplying the left and the right sides of the equations we get

$spup+spwb+taup+tawb=1$ or $p(sup+swb+tau)+ab(tw)=1 \implies \gcd(p,ab)=1$. This is a contradiction.

Is it rigorous and sound proof?

  • 2
    $\begingroup$ Seems correct to me. $\endgroup$ – Peter Feb 23 '15 at 22:05
  • 2
    $\begingroup$ Yes, one of the standard Bezout-based proofs. $\endgroup$ – Bill Dubuque Feb 23 '15 at 22:06
  • 2
    $\begingroup$ Add the statement that $gcd(p,ab) = cp$ where $c \geq 1$ to make the contradiction explicit. $\endgroup$ – John Feb 23 '15 at 22:07
  • 6
    $\begingroup$ There is no need to make this an argument by contradiction: One easily turns your proof into one showing that if $p$ does not divide $a$ then it divides $b$: If $sp+ta=1$, then $sb(p)+t(ab)=b$, and the left-hand side is a multiple of $p$ by assumption. (You mention your book has an argument already, which I assume is this one. Your argument is correct, but I find it is better, for a variety of reasons, to avoid arguments by contradiction if possible.) $\endgroup$ – Andrés E. Caicedo Feb 23 '15 at 22:22
  • 4
    $\begingroup$ @AndresCaicedo: I tried to do that, but got downvoted since that was the proof alluded to from the book. $\endgroup$ – robjohn Feb 23 '15 at 22:24

The proof is correct. Below is the same proof using gcd laws (distributive, etc), for any integer $\,p$.

$\!\!\phantom{\frac{.}{\dfrac{.}.}} 1 = \smash[b]{\underbrace{\color{#0a0}{(p,a)}}_{\large =\, 1}\underbrace{(p,b)}_{\large =\, 1} = (\color{#0a0}{(p,a)}p,\color{#0a0}{(p,a)}b) = (p^2,ap,bp,ab) = ((\underbrace{p,a,b}_{\color{#c00}{\large =\,1}})\, p,ab) = (p,ab)} $

where above we have used the inference: $\ \ (p,a)=1\,\Rightarrow\,(p,a,b)\color{#c00}{ = 1}.$

Remark $\ $ The following comparison might prove instructive.

Euclid's Lemma in Bezout form, gcd form and ideal form
$\quad \smash[t]{\begin{align}\\ \\ px\!+\!ay=&\,\color{#c00}1,\,\ p\ \mid\ ab\ \ \ \Rightarrow\, p\ \mid\ b.\ \ \ {\bf Proof}\!:\,\ p\ \mid\ pb,ab\, \Rightarrow\, p\,\mid pbx\!\!+\!aby = \!(\overbrace{px\!+\!ay}^{\large\color{#c00} 1}\!) b = b\\ (p,\ \ \ a)=&\,\color{#c00}1,\,\ p\ \mid\ ab\ \ \ \Rightarrow\, p\ \mid\ b.\ \ \ {\bf Proof}\!:\,\ p\ \mid\ pb,ab\, \Rightarrow\, p\,\mid (pb,\ \ ab) = (p,\,\ \ \ a) \ b =\, b\\ P\! +\!A\ =&\,\color{#c00}1,\, P\supseteq AB\, \Rightarrow P \supseteq B.\ {\bf Proof}\!:\! P \supseteq\! PB,\!AB\!\Rightarrow\!\! P\supseteq\! PB\!+\!\!AB =(P\!+\!A)B = B \end{align}}$

Note how the Distributive Law for integers is replaced by the Distributive Law for gcds and ideals in the $2$nd last equality in the proofs.

  • 1
    $\begingroup$ +1 Another one of those disappointingly rare occasions on which someone who knows does the translation between different points of view so that the generalisation more general formulation has a clear context. $\endgroup$ – Mark Bennet Feb 23 '15 at 23:20

Another elementary proof, which uses only euclidean division.

Let $p$ dividing $ab$, but not $a$. Consider the following set of natural numbers: $$E=\bigl\{\,n\in \mathbf N^{*}\:;\:p\mid nb\,\bigr\}. $$ $E$ is not empty since it contains $p$ and $a$. Hence it contains a smallest element, $n_0$.

Claim: $n_0$ divides all elements of $E$. Indeed, let $n$ be any element of $E$. We want to prove the remainder of the division of $n$ by $n_0$ is $0$. So let's write: $n=qn_0+r, \enspace 0\le r <n_0$.

As $p\mid nb$ and $p\mid n_0b$, $p\mid (n-qn_0)b=rb$, hence if $r\neq 0$, $r$ is an element of $E$, which contradicts $n_0$ being minimal. Thus $r=0$ and $n_0\mid n$.

In particular, $n_0\mid p$, hence $n_0=1$ or $p$. The latter case is impossible by hypothesis, since $n_0\mid a$. So $n_0=1$, and $p\mid n_0b=b$.

  • $\begingroup$ Key idea $\,E\,$ is closed under subtraction, hence its least positive element divides every element. This ideal/subgroup view is emphasized in proof $(2)$ in this answer, along with $4$ other proofs of Euclid's Lemma. Here $\,E\,$ can be viewed as the denominator ideal of $\,b/p\,$ or the order ideal of $\,b\pmod p.\ $ $\endgroup$ – Bill Dubuque Feb 24 '15 at 0:27
  • $\begingroup$ Fine reference! Actually, the proof I ppresent can be extended to a proof of Gauß's lemma (if $n\mid ab$ and $n$ is coprime with $a$, then $n\mid b$. $\endgroup$ – Bernard Feb 24 '15 at 0:52
  • $\begingroup$ Yes, that's true for most proofs of Euclid's Lemma. $\endgroup$ – Bill Dubuque Feb 24 '15 at 0:53
  • $\begingroup$ See also both of my answers here for some conceptual ways to perform such descent-based proofs. $\endgroup$ – Bill Dubuque Nov 2 '16 at 3:32
  • 1
    $\begingroup$ @jiten: $1$. No, $n$ is a generic name for any natural number such that $p$ divides the product $nb$. In particular, $a$ is one of these numbers, by hypothesis,and $p$ is another, because $p$ obviously divides $pb$. $2$. Where did you find that $p\mid b$? That's what we have to prove if we suppose $p$ doesn't divide $a$. $3$.~Yes, but why do you want to rename $n_0$ $a_0$? $\endgroup$ – Bernard Jun 15 '18 at 22:22

I hope that it is also another elementary proof of this lemma :

Let's assume that $p$ (a prime number) doesn't divide $a$ and $p$ doesn't divide $b$.

That means that $\exists\ (k_1,r_1), (k_2,r_2) \in \mathbb{Z}\times\mathbb{Z}^*$ such as :

$a=pk_1+r_1$ with $0<\vert r_1 \vert<p$ and $b=pk_2+r_2$ With $0<\vert r_2\vert <p$

$\Rightarrow$ $ab=(pk_1+r_1)(pk_2+r_2)=p(pk_1 k_2 + k_1 r_2 + k_2 r_1)+r_1 r_2 = pK+R$

$p$ doesn't divide $R$. Indeed if $p$ divided $R=r_1 r_2$ with $\gcd(p,r_1)=1$ by Gauss Lemma $p$ should divide $r_2$. Impossible.

Hence, $p$ doesn't divide $ab$.

I conclude by contraposition that : if $p$ doesn't divide $a$ and $p$ doesn't divide $b$ then $p$ doesn't divide $ab$.

With this method, I can easily generalize this lemma to $n$ numbers : "If $p$ is a prime number which divides $a_1 a_2 ... a_n$ then $p$ divides $a_1$ or ... or $a_n$".

NB : It will just work in Euclidean Domains like $\mathbb{Z}$.

  • 1
    $\begingroup$ There is no notion of size or a norm in a PID so this proof is not valid for that case. You use the fact that $0 < |r_1| < p$ which is only applicable in Euclidean Domains (which are a subset of PID), since you can say $N(r_1) < N(p)$. $\endgroup$ – gowrath Jan 12 '17 at 19:12
  • $\begingroup$ @gowrath indeed thank you for confirmation ! Nice in $\mathbb{Z}$ !!! $\endgroup$ – Maman Jan 12 '17 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.