Question

If gcd(x, y)=d, find gcd(18x+3y, 3x) in terms of d.

Are we allowed to do this:
Since d=gcd(x,y), then d|x and d|y, Hence d|(xs+yt) for any integers s,t by the Divisibility of Interger combinations. Setting s=18, t=3, then d|(18x+3y). Setting s=3, t=0, then d|3x.

Since d is a positive integer and (18x+3y) and (3x) are integers, we can find (18x+3y)a + (3x)b = d for intergers x,a. Hence d = (18x+3y, 3x) by the GCD Characterization Theorem.
??

Answer 1

And just so you know, our GCD Cahracterization theorem states:
"If d is a positive common divisor of integers a and b and there exists integers x and y such that ax+by=d, then d=gcd(a,b)

Answer 2

i have another technique.....x=da, y=db;
18x+3y=3d(6a+b); and 3x=3da;
so gcd(18x+3y,3x)=3d.

Answer 3

I'm not exactly sure how you ended up on the last line :(

Answer 4

gcd means greatest common divisor so we can see that 18x+3y, and 3x has a common factor 3d, and as we assume that x=da and y=db so a and b has no common factor. so 6a+b and a has no common factor. so the greatest factor is 3d thus the gcd is 3d

Answer 5

oh ok interesting technique
:)

Answer 6

:)