# Math Help - Proof involving GCD

1. ## Proof involving GCD

Hello, I'm having a bit of trouble with the following problem; I'm not sure about how to prove this statement. I'm not even sure on how to begin:

Let a,b ∈ Z. Prove that gcd(a,b)=gcd(2a−3b,a−2b).

I would greatly appreciate any help/tips to get me started.

Thanks!

2. Originally Posted by spoc21
Hello, I'm having a bit of trouble with the following problem; I'm not sure about how to prove this statement. I'm not even sure on how to begin:

Let a,b ∈ Z. Prove that gcd(a,b)=gcd(2a−3b,a−2b).

I would greatly appreciate any help/tips to get me started.

Thanks!
let $\displaystyle \gcd (a,b) = d_1$ and $\displaystyle \gcd (2a - 3b, a - 2b) = d_2$

Then, for some $\displaystyle m,n,x,y \in \mathbb Z$, we have:

$\displaystyle d_1 = ma + nb$ and $\displaystyle d_2 = x(2a - 3b) + y(a - 2b)$, and these are the smallest linear combinations.

But this means $\displaystyle d_2 = (2x + y)a + (-3x - 2y)b$, and so $\displaystyle d_2$ is also a linear combination of $\displaystyle a$ and $\displaystyle b$. This means that this linear combination is a multiple of $\displaystyle d_1$ (*) and hence, $\displaystyle d_2 = k d_1$ for some $\displaystyle k \in \mathbb Z \implies d_1 \mid d_2$.

The proof is complete if you can show that $\displaystyle d_2 \mid d_1$. How can you do this?

(*) this should have been proven in your class or text at some point.

3. Originally Posted by Jhevon
$\displaystyle k \in \mathbb Z \implies d_1 \mid d_2$.

The proof is complete if you can show that $\displaystyle d_2 \mid d_1$. How can you do this?
Thanks for the reply. Is this $d_1 \mid d_2$ or $d_2 \mid d_1$

I'm assuming that to $\displaystyle d_2 \mid d_1$, we would do the follwoing:

$\displaystyle d_2 = d_1 k$
Therefore, we get:

$\displaystyle k = d_2 \mid d_1$

Do you think this is a correct approach?

4. Originally Posted by spoc21
Thanks for the reply. Is this $d_1 \mid d_2$ or $d_2 \mid d_1$

I'm assuming that to $\displaystyle d_2 \mid d_1$, we would do the follwoing:

$\displaystyle d_2 = d_1 k$
Therefore, we get:

$\displaystyle k = d_2 \mid d_1$

Do you think this is a correct approach?
um, no. first, you can't assume what you want to prove. that's called begging the question.

and what you did after that makes no sense especially your last statement. what i think you were trying to say, doesn't follow from the statement you had before that.

go back to basics. what do you know about gcd. what relationship does $\displaystyle d_2$ have with $\displaystyle (2a - 3b)$ and $\displaystyle (a - 2b)$?