# Euclid’s lemma proof

We have $a|bc$, so $bc=na$, with $n$ an integer. Dividing both sides by $a$, we have

$$\frac{bc}{a}=n$$ |

But $\mathrm{gcd}(a,b)=1$ implies $b/a$ is only an integer if $a=1$. So

$$\frac{bc}{a}=b\frac{c}{a}=n$$ |

which means $a$ must divide $c$.

Note that this proof relies on the Fundamental Theorem of Arithmetic^{}. The alternative proof of Euclid’s lemma avoids this.

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

Canonical name | EuclidsLemmaProof |

Date of creation | 2013-03-22 11:47:11 |

Last modified on | 2013-03-22 11:47:11 |

Owner | akrowne (2) |

Last modified by | akrowne (2) |

Numerical id | 9 |

Author | akrowne (2) |

Entry type | Proof |

Classification | msc 17B80 |

Classification | msc 81T30 |

Classification | msc 11A05 |

Classification | msc 81-00 |