1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete proofs involving divisibility

  1. Apr 21, 2014 #1
    I'm trying to do some extra course work to prepare for my final next week but I'm having a lot of trouble with the book problems. They talk about a lot of things we weren't taught. Can someone help me out here?

    Prove: n[itex]\ni[/itex]Z, n= a multiple of gcd(a,b) ⇔ n is a linear combination of a and b

    This question makes no sense to me. How do I prove that and where can I start. What does gcd have to do with linear combinations.
     
  2. jcsd
  3. Apr 21, 2014 #2
    ##n## is a linear combination of ##a## and ##b## should mean that there exist ##s,t\in\mathbb{Z}## such that ##n=sa+tb##.

    Write down the precise mathematical meaning of "##n## is a multiple of ##\gcd (a,b)##" and see if that gets you started.
     
  4. Apr 21, 2014 #3
    ok this is what i have
    Prove: n∈Z n= a multiple pf gcd(a,b) ⇔ n is a linear combination of a and b

    let gcd(a,b)=d. We are given that n=xd for some x∈Z
    Using Bezout’s identity we can expand d, d= sa+tb for some s,t∈Z
    Hence, n=xd=x(sa+tb)=xsa+xtb
    We recognise this as a linear combination of a and b

    now i don't know where to go to do the reverse direction
     
  5. Apr 21, 2014 #4
    Given ##n=sa+tb## and ##d=\gcd (a,b)##, what can you say about ##n-sa##?
     
  6. Apr 21, 2014 #5
    n-sa=tb where do i go with that?
     
  7. Apr 22, 2014 #6
    Actually, forget that hint ... at least the part about focusing on ##n-sa##.

    What are you trying to show about ##n## again? What do you know about ##a## and ##b##?
     
  8. Apr 24, 2014 #7
    umm im given n is a linear combination of a,b and im trying to show that n is a multiple of gcd (a,b)?
     
  9. Apr 25, 2014 #8
    Right. And what do you know about ##a## and ##b## in regards to ##\gcd(a,b)## that might help you establish that ##n## is a multiple of ##\gcd(a,b)##? Think about how you might prove that the sum of two even numbers is even.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Discrete proofs involving divisibility
  1. Division Proof (Replies: 1)

Loading...