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, 2015 at 22:05
  • 2
    $\begingroup$ Yes, one of the standard Bezout-based proofs. $\endgroup$ Feb 23, 2015 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, 2015 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$ Feb 23, 2015 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, 2015 at 22:24

3 Answers 3


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},\,$ and basic gcd arithmetic.

Remark $ $ The following comparison (from here) might prove instructive ($p$ is any integer below)

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\\[.2em] (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\\[.2em] 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.

Generally $\,\ c\mid ab\iff c/(c,a)\mid b\,$ by here, or even more generally for both gcds and ideals we have $\,(c,ab) = (c,(a,c)b).\,$ OP is special case $\,(c,as)=1\,$ (for $\,c\,$ prime).

  • 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$ Feb 23, 2015 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$ Feb 24, 2015 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, 2015 at 0:52
  • $\begingroup$ Yes, that's true for most proofs of Euclid's Lemma. $\endgroup$ Feb 24, 2015 at 0:53
  • $\begingroup$ See also both of my answers here for some conceptual ways to perform such descent-based proofs. $\endgroup$ Nov 2, 2016 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, 2018 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, 2017 at 19:12
  • $\begingroup$ @gowrath indeed thank you for confirmation ! Nice in $\mathbb{Z}$ !!! $\endgroup$
    – Maman
    Jan 12, 2017 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.