# 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:

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.

• I think both approaches are good. Nor are they that different really...in both cases you are trying to find smaller and smaller multiples of $d$.
– lulu
Sep 24 '18 at 15:23
• Thank you very much for the kind comment @lulu. Got a follow up question. By "you are trying to find smaller and smaller multiples of $d$, you mean the process of continously dividing the divisor to remainder so that $r$ decreases? Sep 24 '18 at 15:27
• Is there a typo in (4), i.e. shouldn't 35 be multiplied by $a$?
– user431008
Sep 24 '18 at 15:28
• I meant something less precise than that. Euclid provides a somewhat systematic way to find new numbers that $d$ divides...the second method is less systematic, but faster as you seek out convenient expressions. Working by hand, I prefer the second method...were I trying to automate the process, I'd prefer the systematic approach.
– lulu
Sep 24 '18 at 15:28
• I agree @marmot. Thank you for pointing it out. Sep 24 '18 at 15:29

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

• Thanks for the clarification in solution 1 and by giving a simplified version for solution 2. It is very clear to me now. @egreg Sep 24 '18 at 15:35

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.

• Thank you very much for completing the proof of solution 1 Prof. I am interested in a case that solution 2 wont work. Thank you Prof. Sep 24 '18 at 15:41
• @JrAntalan Concerning the second proof, I only meant that you have to think about it in a case-by-case basis. Sep 24 '18 at 15:43
• Noted Prof. and Thank you again. Sep 24 '18 at 15:44

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.