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

[binbagsss]

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 that's 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?

 

[fresh_42]

Simpy divide ##p## by ##q##.

 

[binbagsss]

Simpy divide ##p## by ##q##.

##(p/q) d - b =1 ## , now what?

 

[fresh_42]

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}##.

 

[member 587159]

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 that's 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?

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##