Undergrad 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$