# Thread: Number Theory GCD Problem

1. ## 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!

2. Originally Posted by SKooT1027
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

3. Originally Posted by ThePerfectHacker
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.