Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Show that you can find d and b s.t pd-bq=1 , p and q are coprime- GCF

  1. Dec 17, 2016 #1
    Context probably irrelevant but modular forms- to show that all rational numbers can be mapped to ##\infty##) that is there exists a ## \gamma = ( a b c d) ##, sorry thats a 2x2 matrix, ## \in SL_2(Z) ## with ## det (\gamma) = ad-bc=1 ## s.t ## \gamma . t = at+b/ct+d = \infty ##, where take ## t= r ## , r a rational number. )

    So I'm at the stage where I am just stuck on showing that ## p ## and ## q ## co prime implies that ## b ## and ## d ## can be found s.t ## pd-bq=1 ## , b and d integer.

    I'm not sure how to do this? I think the argument should be obvious?
     
  2. jcsd
  3. Dec 17, 2016 #2

    fresh_42

    Staff: Mentor

    Simpy divide ##p## by ##q##.
     
  4. Dec 17, 2016 #3
    ##(p/q) d - b =1 ## , now what?
     
  5. Dec 17, 2016 #4

    fresh_42

    Staff: Mentor

    It's called Bézout's identity which allows to write the greatest common divisor ##d## of two integers ##p,q## in the form ##d= pd + dq##.
    The proof uses the Euclidean algorithm and the ordering of ##\mathbb{Z}##.
     
  6. Dec 17, 2016 #5

    Math_QED

    User Avatar
    Homework Helper

    Your question is immediately answered by Bezout's theorem:

    ##Gcf(a,b) = d \iff \exists m,n \in \mathbb{Z}: ma + nb = d##. Simply set ##d = 1##. To prove this, one can use the Euclidean algorithm backwards.

    To illustrate with an example:

    ##Gcf(17,3) = 1##

    ##17 = 3*5 + 2##
    ##5 = 2*2 + 1 ##
    This was the euclidean algorithm. Now substituting back (the idea to prove Bezout's theorem)
    ##1 = 5 -2*2 = 5 - 2(17 -3*5) = 5 -2*17 + 2* 3*5 = -2*17 + 7*5##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted