Thread: Coprime Proof
View Single Post
  #4  
Old November 6th, 2009, 09:47 AM
Drexel28's Avatar
Drexel28 Drexel28 is offline
MHF Contributor
  
Join Date: Nov 2009
Location: Philadelphia, PA
Posts: 1,899
Country:
Thanks: 74
Thanked 560 Times in 522 Posts
Drexel28 is a name known to allDrexel28 is a name known to allDrexel28 is a name known to allDrexel28 is a name known to allDrexel28 is a name known to allDrexel28 is a name known to all
Default
Quote:
Originally Posted by sirellwood View Post
Hi all,

a, b are coprime integers such that a|m and b|m, for some integer m. Prove, using Euclid’s lemma, that ab|m.
Alternatively

Problem: Suppose \text{gcd}\left(a,b\right)=1. Furthermore suppose that a\mid m and b\mid m. Prove that ab\mid m.

Proof: Since \text{gcd}(a,b)=1 we know \exists x,y\in\mathbb{Z} such that ax+by=1. Therefore for the same x,y we'd have that axm+bmy=m. Since b|m it is clear that ab|axm similarly since a|m is it clear that ab|bym. Therefore ab|axm+bym=m\quad\blacksquare
Reply With Quote
The following users thank Drexel28 for this useful post:
Donate to MHF