Jump to content

Discrete Math - Logic Proofs [Help]


AwesomeMcCoolName

Recommended Posts

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

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

Archived

This topic is now archived and is closed to further replies.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...