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.(adsbygoogle = window.adsbygoogle || []).push({});

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 [tex] (\frac{a}{(a,b)}, \frac{b}{(a,b)}) = 1 [/tex]

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, [tex] (\frac{a}{(a,b)}, \frac{b}{(a,b)}) [/tex] becomes [tex] (\frac{lg}{g}, \frac{jg}{g}) [/tex] which becomes [tex] (l , j) = 1. [/tex]

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

PROBLEM 2

1. The problem statement, all variables and given/known data

[tex] (a, b) = (a + cb, b) [/tex]

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).

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Gcd proofs check

**Physics Forums | Science Articles, Homework Help, Discussion**