# alternative proof of Euclid’s lemma

We give an alternative proof (see Euclid’s lemma proof), which does not use the Fundamental Theorem of Arithmetic^{} (since, usually, Euclid’s lemma is used to prove FTA).

###### Lemma 1.

If $a\mathrm{\mid}bc$ and $\mathrm{gcd}\mathit{}\mathrm{(}a\mathrm{,}b\mathrm{)}\mathrm{=}\mathrm{1}$ then $a\mathrm{\mid}c$.

###### Proof.

By assumption^{} $\mathrm{gcd}(a,b)=1$, thus we can use Bezout’s lemma to find integers $x,y$ such that $ax+by=1$. Hence $c\cdot (ax+by)=c$ and $acx+bcy=c$. Since $a\mid a$ and $a\mid bc$ (by hypothesis), we conclude that $a\mid acx+bcy=c$ as claimed.
∎

Title | alternative proof of Euclid’s lemma |
---|---|

Canonical name | AlternativeProofOfEuclidsLemma |

Date of creation | 2013-03-22 14:12:27 |

Last modified on | 2013-03-22 14:12:27 |

Owner | alozano (2414) |

Last modified by | alozano (2414) |

Numerical id | 4 |

Author | alozano (2414) |

Entry type | Proof |

Classification | msc 11A05 |