gcd(2a+1, 9a+4) = 1

Question

The question is from Burton's Elementary Number Theory. I want to know if my proof is legible. Proof : Let $$d=gcd(2a+1, 9a+4)$$ Then $$d|2a+1$$ and $$d|9a+4$$ $$2a+1=db$$ and $$9a+4=dc$$ $$ a = \frac{db-1}{2}$$and$$a= \frac{dc-4}{9}$$ Equating both equations : $$ 9db-9=2dc-8 $$ $$ d(9b-2c) = 1 $$ $$ 9b-2c = \frac{1}{d}$$ Now, since b and c are integers, therefore $\frac{1}{d}$ is an integer, i.e d divides 1 and therefore $$gcd(a, b)= d = 1$$.

Answer 1

Seems fine.

Alternatively,

$$9a+4=4(2a+1)+a$$

$$2a+1=2(a)+1$$

Hence,

$$1=(2a+1)-2a=(2a+1)-2(9a+4)+8=9(2a+1)-2(9a+4)$$

That is the greatest common divisor of $2a+1$ and $9a+4$ must divide $1$. Hence the greatest common divisor is $1$.

Answer 2

Divide $2a+1$ into $9a+4$ giving $9a+4 = 9/2\cdot (2a+1) - 1/2$ or $2(9a+4) = 9(2a+1)-1$, or $1= -2(9a+4) + 9(2a+1)$. So each divisor of $9a+4$ and $2a+1$ divides $1$.

Answer 3

Looks good to me. Some nit picks follow:

A bit of formatting may help readability. For much of your answer you have pairs of equations which belong together, but the pairs which belong together aren't the pairs which appear close to one another.

After "therefore $\frac{1}{d}$ is an integer", you can just say "so $d=1$ and we're done". Remember that $d=1$ is the very thing we want to prove, so it's unnecessary to continue with more calculations once you've reached that conclusion.

And personally I would probably have used the Euclidean algorithm instead.

Answer 4

As Siong Thye Goh said, we can use the Euclidean algorithm to guide us to a proof. The Euclidean algorithm is based on the fact that $gcd(x,y)=gcd(x,y-tx)$. If we take $x=2a+1$, $y=9a+4$, and $t=4$, then we get $gcd(2a+1,9a+4)=gcd(2a+1,a)$. Applying it again with $x=a$, $y=2a+1$, $t=2$, we get $gcd(2a+1,a)=gcd(1,a)$. From there, it's easy to see that the gcd is $1$.