8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – lulu Sep 24 '18 at 15:23
  • $\begingroup$ 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? $\endgroup$ – Jr Antalan Sep 24 '18 at 15:27
  • 2
    $\begingroup$ Is there a typo in (4), i.e. shouldn't 35 be multiplied by $a$? $\endgroup$ – user431008 Sep 24 '18 at 15:28
  • 2
    $\begingroup$ 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. $\endgroup$ – lulu Sep 24 '18 at 15:28
  • $\begingroup$ I agree @marmot. Thank you for pointing it out. $\endgroup$ – Jr Antalan Sep 24 '18 at 15:29
3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jr Antalan Sep 24 '18 at 15:41
  • 1
    $\begingroup$ @JrAntalan Concerning the second proof, I only meant that you have to think about it in a case-by-case basis. $\endgroup$ – José Carlos Santos Sep 24 '18 at 15:43
  • $\begingroup$ Noted Prof. and Thank you again. $\endgroup$ – Jr Antalan Sep 24 '18 at 15:44
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.