Query on a Solution to the Problem: $\gcd(5a+2,7a+3)=1$ for all integer $a$. I wish to show that the numbers $5a+2$ and $7a+3$ are relatively prime for all positive integer $a$.
Here are my solutions.
Solution 1. I proceed with Euclidean Algorithm. Note that, for all $a$, $|5a+2|<|7a+3|$. By Euclidean Algorithm, we can divide $7a+3$ by $5a+2$. To have
$7a+3=(5a+2)(1)+(2a+1)$ continuing we have,
$5a+2=(2a+1)(2)+a$
$2a+1=(2)(a)+1$
$2=(1)(2)+0$
Since the last nonzero remainder in the Euclidean Algorithm for $7a+3$ and $5a+2$ is 1, we conclude that they are relatively prime.
Solution 2. Suppose that $d=\gcd(5a+2,7a+3)$. Since $d=\gcd(5a+2,7a+3)$ then the following divisibility conditions follow:
(1) $d\mid (5a+2)$
(2) $d\mid (35a+14)$
(3) $d\mid (7a+3)$
(4) $d\mid (35a+15)$.
Now, (2) and (4) implies that $d$ divides consecutive integers. The only (positive) integer that posses this property is $1$. Thus, $d=1$ and that $7a+3$ and $5a+2$ are relatively prime.
Here are my questions:


*

*Is the first proof correct or needs to be more specific? For instance cases for $a$ must be considered. 

*Which proof is better than the other? 
Thank you so much for your help.     
 A: In the first solution you're not using, strictly speaking, the Euclidean algorithm, but a looser version thereof:

Let $a$, $b$, $x$ and $y$ be integers; if $a=bx+y$, then $\gcd(a,b)=\gcd(b,y)$.

The proof consists in showing that the common divisors of $a$ and $b$ are the same as the common divisors of $b$ and $y$.
There is no requirement that $a\ge b$ or that $y$ is the remainder of the division. Indeed your argument actually has a weakness, because $7a+3\ge 5a+2$ only if $2a\ge-1$, so it doesn't hold for $a\le-2$. But $7a+3\ge 5a+2$ is not really needed for the argument.
Since successive application of the statement above show that $\gcd(2a+1,2)=1$ and the gcd has never changed in the various steps, you can indeed conclude that $\gcd(5a+2,7a+3)=1$.
The second solution is OK as well.
You can simplify it by noting that if $d$ is a common divisor of $5a+2$ and $7a+3$, then it divides also
$$
5(7a+3)-7(5a+2)=1
$$
A: Your first proof is correct. I would perhaps complete it, writing that\begin{align}1&=(2a+1)-2a\\&=2a+1-2\bigl(5a+2-2(2a+1)\bigr)\\&=5(2a+1)-2(5a+2)\\&=5\bigl(7a+3-(5a+2)\bigr)-2(5a+2)\\&=5(7a+3)-7(5a+2).\end{align}
Your second proof also works, but it doesn't generalize easily to other situations.
A: Here is a different rendering of the same arguments.
Let $u=5a+2$, $v=7a+3$. Then
$$
\pmatrix{ u \\ v}
=
\pmatrix{ 5 & 2 \\ 7 & 3}
\pmatrix{ a \\ 1}
$$
and so
$$
\pmatrix{ a \\ 1}
=
\pmatrix{ 5 & 2 \\ 7 & 3}^{-1}
\pmatrix{ u \\ v}
=
\pmatrix{ \hphantom- 3 & -2 \\ -7 & \hphantom-5}
\pmatrix{ u \\ v}
$$
This gives
$$
1 = -7u+5v = -7(5a+2)+5(7a+3)
$$
The key point here is that the matrix has determinant $1$ and so its inverse has integer entries.
