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.
Best Answer
In the first solution you're not using, strictly speaking, the Euclidean algorithm, but a looser version thereof:
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 $$