Prove these two GCD (greatest common divisor)

**jessicafreeman** · January 10th 2010, 03:37 PM

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.

**Jhevon** · January 10th 2010, 04:24 PM

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. $a \mid b \Longleftrightarrow b = ka$ for some $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 $d = \text{gcd}(a+b,a-b)$ and $d_1 = \text{gcd}(a,b)$ . You want to show that $d = kd_1$ for some $k$ .

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

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

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

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

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

**jessicafreeman** · January 11th 2010, 04:42 PM

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!

**Jhevon** · January 11th 2010, 05:27 PM

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: $d_1 = \text{gcd}(a,b)$ means, in particular, $d_1 \mid a$ and $d_1 \mid b$ . And what do each of those mean? Can you use that to finish up?

**jessicafreeman** · January 12th 2010, 02:04 PM

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.

**Jhevon** · January 12th 2010, 02:18 PM

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. $c|(a + b) \Longleftrightarrow a + b = kc$ for some integer $k$ . what can you do with that equation?

**jessicafreeman** · January 12th 2010, 05:54 PM

Originally Posted by Jhevon

essentially the same hint will work. $c|(a + b) \Longleftrightarrow a + b = kc$ for some integer $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

.

**Jhevon** · January 12th 2010, 06:17 PM

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.

**jessicafreeman** · January 12th 2010, 06:51 PM

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!

Thread: Prove these two GCD (greatest common divisor)

LinkBack

Thread Tools

Display

Prove these two GCD (greatest common divisor)

Similar Math Help Forum Discussions

Greatest Common Divisor of (9m+8, 6m+5)

[SOLVED] Least common multiple - Greatest common divisor

Greatest common divisor

greatest common divisor

greatest common divisor

Search Tags