Prove for all $n \in N$, $\gcd(2n+1,9n+4)=1$ Question: Prove for all $n \in N$, $\gcd(2n+1,9n+4)=1$
Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear combination.
Euclid's Algorithm states that we let $a,b \in N $. By applying the Division Algorithm repeatedly...then $\gcd(a,b) = r_j$ will be the last non-zero remainder. By the Well Ordering Principle, there is a smallest element of the set of natural numbers less than or equal to $r_j$.
I have used long division, but since I can't get it to show up here, I will type what I've done. 
Starting at $\gcd(2n+1,9n+4)$,
$\frac{2n+1}{9n+4}$
I can multiply $2n+1$ four times and I would have a remainder of $n$ because $(9n+4)-(8n+4) = 9n+4-8n-4=n$
so we have $4 \cdot (2n+1)+n$ if I apply Euclid's Algorithm. 
For $\gcd(2n+1, n)$, 
$\frac{2n+1}{n}$
I can multiply $n$ 2 times and I will have only 1 as the remainder because $(2n+1)-(2n+0) = 2n+1-2n+0=1$
Therefore, we have $2 \cdot (n) +1$
and  $\gcd(n,1)$  which is $1$ 
Since the end result is $1, \gcd(2n+1,9n+4)=1$
I followed an example from this link
http://cms.math.ca/crux/v33/n5/public_page274-276.pdf
Am  I doing this correctly?
 A: One approach can be create a relation eliminating  $n$ as follows :
$$S=9(2n+1)-2(9n+4)=1$$
If integer $d$ divides $\displaystyle 2n+1,9n+4$ it will divide $S=1$
A: It can use this property:
$$GCD(a,b)=GCD(a-qb,b) $$
So:
$$ GCD(2n+1,9n+4)=GCD(2n+1,n)=GCD(1,n)=1$$
A: Your approach is quite correct (As far as I think). Here is a similar but still different one.
Suppose that $\gcd(2n+1,9n+4)\ne1$ and there exist a $d$ such that $\gcd(2n+1,9n+4)=d$.
Now $d|9n+4$,  and $d|2n+1$ $\implies d|9n+4- 4\times (2n+1)$.
$\implies d|n$. 
$d|2n+1 - n\implies d|n+1$.
Again:  $d|n+1-n\implies d|1$.
It is enough I think.
A: There is also the systematic matrix approach:
$$
\begin{pmatrix} a \\ b \end{pmatrix} 
=
\begin{pmatrix} 2 & 1 \\ 9 & 4 \end{pmatrix} 
\begin{pmatrix} n \\ 1 \end{pmatrix} 
\implies
\begin{pmatrix} n \\ 1 \end{pmatrix} 
=
\begin{pmatrix} -4 & \hphantom-1 \\ \hphantom-9 & -2 \end{pmatrix} 
\begin{pmatrix} a \\ b \end{pmatrix} 
$$
In particular, $1=9a-2b$, which implies $\gcd(a,b)=1$.
The key point here is that the first matrix has determinant $-1$ and so is invertible over the integers.
