# Thread: Prove these two GCD (greatest common divisor)

1. ## Prove these two GCD (greatest common divisor)

Hi, thanks for taking the time to look in this thread. Here are the GCD (great common divisior) questions that need proof:

1. Let a and b be integers. Prove that gcd(a, b)|gcd(a + b, a − b).

2. Let a, b, c be integers. Suppose that gcd(a, b) = 1 and c|(a+b). Prove
that gcd(a, c) = 1.

2. Originally Posted by jessicafreeman
Hi, thanks for taking the time to look in this thread. Here are the GCD (great common divisior) questions that need proof:

1. Let a and b be integers. Prove that gcd(a, b)|gcd(a + b, a − b).

2. Let a, b, c be integers. Suppose that gcd(a, b) = 1 and c|(a+b). Prove
that gcd(a, c) = 1.
what have you tried?

first recall that the gcd of two integers can be written as a (in fact, the smallest) linear combination of the two integers.

also recall what it means for one integer to divide another. $\displaystyle a \mid b \Longleftrightarrow b = ka$ for some $\displaystyle k \in \mathbb Z$

you think you can get anywhere with those? or do you need another hint?

for 1 i'd start this way: all variables are integers here

Let $\displaystyle d = \text{gcd}(a+b,a-b)$ and $\displaystyle d_1 = \text{gcd}(a,b)$. You want to show that $\displaystyle d = kd_1$ for some $\displaystyle k$.

Now, $\displaystyle d = r(a + b) + t(a - b) = \cdots$

use the fact that $\displaystyle d_1 = \text{gcd}(a,b)$ to finish up.

for 2, since $\displaystyle \text{gcd}(a,b) = 1$, we have that

$\displaystyle 1 = ma + nb$ for some $\displaystyle m,n$

you want to show that $\displaystyle ra + tc = 1$ for some $\displaystyle r,t$. use the fact that $\displaystyle c \mid (a + b)$ to accomplish this (start by translating that into an equation)

3. Thank you for your help Jhevron.

I was able to solve question 2, but I still haven't quite got the final proof for 1...

is there any other small hint you could throw my way, if possible? if not, thats ok. thank you for all your help!

4. Originally Posted by jessicafreeman
Thank you for your help Jhevron.

I was able to solve question 2, but I still haven't quite got the final proof for 1...

is there any other small hint you could throw my way, if possible? if not, thats ok. thank you for all your help!
good job on problem 2. if you like, you can post your solution to be scrutinized.

as for an additional hint for 1: $\displaystyle d_1 = \text{gcd}(a,b)$ means, in particular, $\displaystyle d_1 \mid a$ and $\displaystyle d_1 \mid b$. And what do each of those mean? Can you use that to finish up?

5. argh! Oh dear, i made a mistake... i meant to say that the other way around x__x. I finished problem 1 and didn't completely get problem 2 .

thank you though.

6. Originally Posted by jessicafreeman
argh! Oh dear, i made a mistake... i meant to say that the other way around x__x. I finished problem 1 and didn't completely get problem 2 .

thank you though.
essentially the same hint will work. $\displaystyle c|(a + b) \Longleftrightarrow a + b = kc$ for some integer $\displaystyle k$. what can you do with that equation?

7. Originally Posted by Jhevon
essentially the same hint will work. $\displaystyle c|(a + b) \Longleftrightarrow a + b = kc$ for some integer $\displaystyle k$. what can you do with that equation?
hehe thanks.

the result i found with how it ended up was being something of the form
1= a(k-j) + c(rk), where k, j, r, and k are some integers...
i'm worried that it's wrong because there's too many variables on c .

8. Originally Posted by jessicafreeman
hehe thanks.

the result i found with how it ended up was being something of the form
1= a(k-j) + c(rk), where k, j, r, and k are some integers...
i'm worried that it's wrong because there's too many variables on c .
you have the desired form, so we're good. you have an integer times a plus and integer times c equals 1. you seemed to use different variables than i did, but yeah, i got something like that.

9. Originally Posted by Jhevon
you have the desired form, so we're good. you have an integer times a plus and integer times c equals 1. you seemed to use different variables than i did, but yeah, i got something like that.

yay! thank you so much! i really appreciate all your help!