# Homework Help: Abstract Algebra Proof

1. Sep 8, 2011

### mcspammle

1. The problem statement, all variables and given/known data
Let r,s,t and v be integers with r>0. If st=r+v and gcd(s,t)=r, then gcd(v,t)=r

2. Relevant equations
Just stumped. I am not sure what to do next.

3. The attempt at a solution

There are 2 integers d and e such that S=dR and T=eR, and 2 integers a and b such that Sa+Tb=R. I know I have to end with something like V(integer)+T(integer)=R to show the gcd(v,t)=r.

2. Sep 8, 2011

### lanedance

s=dr
t=er
worth noting that e and d here have no common factors
st = derr = r+v

so clearly v=a.r for some a
st = derr = r(1+a)

which becomes
der = (1+a)

3. Sep 8, 2011

### mcspammle

I see how you did that but we usually can only do those "clearly" moments when we have a theorem or lemma to reference to, yet there is none for that. I still can't work from der=(1+a) anyway... I dont see how the "a" is going to help in anyway.

I feel like I need to just get V*(any variable)=(any variables) so that I can use V into my formulas.

Last edited: Sep 8, 2011
4. Sep 8, 2011

### lanedance

can you explain what what step you don't understand? (and why - there could always be a mistake - never assume everything is correct unless you can justify it)

derr is divisible by r, so r+v is divisible by r (tempted not to say derr ;)

I'm guessing (haven't worked it) but from the following
der=(1+a)

You should be able to make a conclusion about common factors between a and d,e,r.

Maybe try assuming a and d have a common factor and see if you can generate a contradiction

5. Sep 8, 2011

### mcspammle

I understand what you did. V is some random integer times A. I just didn't see how that could play out to my advantage later. This is only my second homework and we only learned the division theorem (AKA. f divides c so, f=cx) and the GCD theorem which I did below. I am sure you are heading down the right path but I am not advanced enough to do it. I don't want to do things we haven't learned. All his proofs were much simpler than this, I must be just missing something. Thank you though :/

6. Sep 8, 2011

### mcspammle

If r+v=r(1+a) couldn't I do r+v=v(1+c) saying r=vc instead. With that r=v+vc-v. Sa+Tb=r... (dr)a+Tb=r... dv(c)a+Tb=r... So V(other int)+T(other int)=r so gcd(v,t)=r. Was that possible?

7. Sep 8, 2011

### lanedance

V isn't some random integer times A

v=r.a
v is r multiplied an unknown integer, a, which you can relate to the factors d.e.r.

8. Sep 8, 2011

### lanedance

no the fact that "v" has "r" as a factor means |v|>r as they are both integers

9. Sep 8, 2011

### lanedance

the point i was trying to make here is:

d.e.r.r is divisible by d,e,r by definition

d.e.r.r = r+v, shows (r+v) must also be divisible by those terms

Clearly r is divisible by r.

For (r+v) to be divisible by r, then v must be divisible by r

Hence
v=a.r for some integer a

10. Sep 8, 2011

### lanedance

going back to your first post to see if i can clear any initial misconceptions

This is a good place to start, as you know S & T both have factor of r
not sure where you get this statement? in fact I would say it is in contradiction with you last