GCD Proof Check: 2 Problems Involving GCDs in Z

[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

Homework Statement

Prove (\frac{a}{(a,b)}, \frac{b}{(a,b)}) = 1

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

Homework Statement

(a, b) = (a + cb, b)

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

 

[micromass]

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

Homework Statement

Prove (\frac{a}{(a,b)}, \frac{b}{(a,b)}) = 1

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.

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

PROBLEM 2

Homework Statement

(a, b) = (a + cb, b)

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

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

 

[Zhalfirin88]

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

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

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

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.

 

[micromass]

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

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

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.

This looks ok!