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