Results 1 to 3 of 3

Math Help - Number Theory GCD Problem

  1. #1
    Newbie
    Joined
    Oct 2006
    Posts
    4

    Number Theory GCD Problem

    I have been struggling on this question for way too long, and I just can't figure out what to do. I have tried all of my textbooks already, so I thought someone here might be able to help

    The question is as follows:
    [note (x,y) denotes GCD]


    Let a,b in the integers with (a,b)=1. Find all possible values of (a+3b, b+3a)

    All I think I figured out so far is to start by letting d= (a+3b,b+3a) and from there realizing that d|a+3b and d|3a+b .. but i dont know what to do from there. Please help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by SKooT1027 View Post
    I have been struggling on this question for way too long, and I just can't figure out what to do. I have tried all of my textbooks already, so I thought someone here might be able to help

    The question is as follows:
    [note (x,y) denotes GCD]


    Let a,b in the integers with (a,b)=1. Find all possible values of (a+3b, b+3a)

    All I think I figured out so far is to start by letting d= (a+3b,b+3a) and from there realizing that d|a+3b and d|3a+b .. but i dont know what to do from there. Please help!
    Note we can write,
    gcd[a+3b,a+3b-(2b-2a)]=d
    Then,
    d|(a+3b) and d|(a+3b-(2b-2a)|
    By rules of divisibility,
    d|(2b-2a) thus, d|2(b-a)
    If d is odd then,
    d|(b-a)
    But then, d|(a+3b+b-a) thus, d|4a thus, d|a
    But then from d|(b-a) we have d|b thus, d=1
    Thus, the only odd value that can be is d=1

    Say d is even and larger then 2.
    Then d|2(b-a) yields d'|(b-a) that is d'=d/2
    Using the same argument we see that d'|b and d'|a thus, d'=1

    Thus, the only possible values are d=1,2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2006
    Posts
    4
    Quote Originally Posted by ThePerfectHacker View Post
    Note we can write,
    gcd[a+3b,a+3b-(2b-2a)]=d
    Then,
    d|(a+3b) and d|(a+3b-(2b-2a)|
    By rules of divisibility,
    d|(2b-2a) thus, d|2(b-a)
    If d is odd then,
    d|(b-a)
    But then, d|(a+3b+b-a) thus, d|4a thus, d|a
    But then from d|(b-a) we have d|b thus, d=1
    Thus, the only odd value that can be is d=1

    Say d is even and larger then 2.
    Then d|2(b-a) yields d'|(b-a) that is d'=d/2
    Using the same argument we see that d'|b and d'|a thus, d'=1

    Thus, the only possible values are d=1,2
    Thank you very much. I did not see the rearrangement when I looked at it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: June 29th 2010, 09:04 AM
  2. Number Theory Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 28th 2009, 03:44 PM
  3. number theory problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 11th 2009, 08:43 AM
  4. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 30th 2008, 01:07 PM
  5. Replies: 2
    Last Post: December 18th 2008, 06:28 PM

Search Tags


/mathhelpforum @mathhelpforum