Query on a Solution to the Problem: $\gcd(5a+2,7a+3)=1$ for all integer $a$.

Question

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:

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

2. Which proof is better than the other?

Thank you so much for your help.

Answer 1

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 $$

Answer 2

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.

Answer 3

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.