# Homework Help: Gcd proofs check

1. Sep 6, 2011

### Zhalfirin88

I was doing a couple proofs (since I'm new to them) involving gcds and I just would like you guys to check them to see if I actually proved anything. There are 2 separate problems here.

For both problems, a,b,c are in Z with a and b not both zero.

PROBLEM 1
1. The problem statement, all variables and given/known data
Prove $$(\frac{a}{(a,b)}, \frac{b}{(a,b)}) = 1$$

3. The attempt at a solution
With this proof I'm stuck. Let g = (a,b), thus g|a and g|b where a = lg and b = jg. Then, $$(\frac{a}{(a,b)}, \frac{b}{(a,b)})$$ becomes $$(\frac{lg}{g}, \frac{jg}{g})$$ which becomes $$(l , j) = 1.$$

And I don't know where to go from there.

PROBLEM 2

1. The problem statement, all variables and given/known data
$$(a, b) = (a + cb, b)$$

3. The attempt at a solution
Let (a, b) = d and (a + cb, b) = g, with d =/= g. Thus d|a and d|b, where a = ld and b = jd. Also g|a+cb and g|b, where b = gn. Since jd = b = gn, jd = gn, and since d|b and g|b, g=d, which is a contradiction, so (a,b) = (a+cb, b).

2. Sep 6, 2011

### micromass

Well, assume that d divides l and j. Prove that d=1.

How does it follow from d|b and g|b that g=d?

3. Sep 6, 2011

### Zhalfirin88

I know, I've tried that but I don't see how I can prove d = 1, that's why I'm stuck :)

I actually made a huge mistake in that reasoning. Here it goes:

Let (a, b) = d and (a + cb, b) = g, with d =/= g. Thus d|a and d|b, where a = ld and b = jd. Also g|a+cb and g|b, where b = gy.

g= r(a+cb)+nb = ar + cbr + nb = ldr + cjdr + njd = d(l + cj + nj). Thus, g|d.

Now, since g|a+cb, g|a and g|cb, right, since if g divides the sum, it also divides its individual parts? Let a = gx.

d = ma + nb = mgx + nyg = g(mx + ny). Thus d|g. Since d|g and g|d, d=g.

4. Sep 6, 2011

### micromass

Well, if d divides l and j, then d divides a and b. Thus...

This looks ok!