1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Abstract Algebra Proof

  1. Sep 8, 2011 #1
    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. jcsd
  3. Sep 8, 2011 #2


    User Avatar
    Homework Helper

    how about this as a start:
    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)
  4. Sep 8, 2011 #3
    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
  5. Sep 8, 2011 #4


    User Avatar
    Homework Helper

    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

    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
  6. Sep 8, 2011 #5
    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 :/
  7. Sep 8, 2011 #6
    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?
  8. Sep 8, 2011 #7


    User Avatar
    Homework Helper

    V isn't some random integer times A

    v is r multiplied an unknown integer, a, which you can relate to the factors d.e.r.
  9. Sep 8, 2011 #8


    User Avatar
    Homework Helper

    no the fact that "v" has "r" as a factor means |v|>r as they are both integers
  10. Sep 8, 2011 #9


    User Avatar
    Homework Helper

    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

    v=a.r for some integer a

  11. Sep 8, 2011 #10


    User Avatar
    Homework Helper

    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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook