AwesomeMcCoolName Posted February 13, 2014 Share Posted February 13, 2014 Having some trouble figuring this proof out... Fact: For any integers p and q, there are integers s and t such that gcd(p,q) = sp + tq.Using this background information, prove the claim directly from the definition of divides, without using fractions. Claim: For any integers a,b, and c, if a and c are relatively prime and c|ab, then c|b. Suppose GCD(a,c)=sa + tc. GCD(a,c)=1 by definition of relatively prime. 1=sa+tc And from there i'm kind of lost, i'm not really sure how to incorporate either divide statements in. Definition of divides: c divides ab if ab=cm for some integer m. Link to comment Share on other sites More sharing options...
Aaron H. #11BUDS Posted February 13, 2014 Share Posted February 13, 2014 math231312321 Link to comment Share on other sites More sharing options...
Julia Gillard the Honest Posted February 13, 2014 Share Posted February 13, 2014 c|ab so for an integer, say, k, ab=kc. From 1 = sa + tc, we have (multiplying by b ) b = sab + tcb = skc + tbc = (sk+tb)c. Thus c|b. I read it quickly so please let me know if I misread any of the given assumptions. If I read it correctly then there are other ways too (such as: multiply by b and then say that b | sab and b | tbc so b divides their sum). Link to comment Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.