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

• I
• binbagsss
In summary, Bezout's theorem states that if two integers have a greatest common divisor, then that divisor is integer.
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?

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

fresh_42 said:
Simpy divide ##p## by ##q##.

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

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

binbagsss said:
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?

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

## 1. What is the significance of finding d and b in the equation pd-bq=1?

The variables d and b represent the coefficients needed to express the equation in the form of a linear combination of two coprime integers, p and q. This allows us to prove that p and q are indeed coprime, meaning they have no common factors other than 1.

## 2. How is it possible to find values for d and b in the given equation?

The values for d and b can be found using the extended Euclidean algorithm, which is a method for finding the greatest common factor (GCF) of two integers. In this case, the GCF is equal to 1, and the algorithm can be used to find the values of d and b that satisfy the equation.

## 3. What does it mean for two integers to be coprime?

Two integers are said to be coprime if their greatest common factor (GCF) is equal to 1. This means that the only positive integer that divides both numbers evenly is 1. In other words, the two integers do not share any common factors other than 1.

## 4. Why is it important to prove that p and q are coprime?

Proving that p and q are coprime is important in number theory and cryptography. It allows us to use these two integers in certain mathematical operations, such as encryption and decryption, without any interference from common factors. This ensures the security and accuracy of these operations.

## 5. Can the extended Euclidean algorithm be used to find values for d and b in any equation?

The extended Euclidean algorithm can only be used to find values for d and b in equations that have a GCF of 1. If the GCF is any other number, the algorithm will not work. Additionally, the algorithm can only be used for linear equations in the form of ax+by=c, where a, b, and c are integers.

Replies
1
Views
1K
Replies
1
Views
1K
Replies
3
Views
517
Replies
1
Views
751
Replies
1
Views
4K
Replies
8
Views
1K
Replies
4
Views
2K
Replies
2
Views
2K
Replies
4
Views
3K
Replies
61
Views
10K