# Show $\mathrm{gcd}(7a+5,4a+3)=1$.

I have been trying to do this problem for a couple of days for better or worse.

I suppose that $d = \mathrm{gcd}(7a+5,4a+3)$. Since $4a+3=2(2a+1)+1$ it must be that $d$ is odd. I know that $d|(7a+5)$ and $d|(4a+3)$ so $d|(11a+8)$. I also know that $\mathrm{gcd}(a,b) \leq \mathrm{gcd}(a+b,a-b)$ but I haven't been able to get anything useful out of that yet.

I have just been trying to find some kind of contradiction assuming that $d>1$ but I haven't found anything definite.

• Maybe you could use the Euclidean algorithm – Chris Brooks Feb 7 '13 at 6:53
• True, thank you. We have gone over the Euclicean Algorithm but that was before this homework was given. I imagine I could use it though to glean information or at worst just get my solution that way thank you. – name Feb 7 '13 at 6:56

Do you know about the Bezout identity? $$7(4a+3)-4(7a+5)=1$$ The choice of $7$ and $4$ as coefficients is guided by the fact that you need the $a$'s to cancel exactly.

• I do know about the identity. For some reason I just assumed it would be too difficult to find number satisfying the equation. I suppose if I actually thought about it for a moment it wouldn't have seemed that bad. Thank you =/ – name Feb 7 '13 at 6:58

The Euclidean algorithm, and ideas based on it, are frequently the best method for common divisor problems.

In this situation, we have a conundrum: we can't tell which number is larger and how many times the smaller one goes into the larger one! So, we have to decide on some other approach.

We could treat $a$ as being "big" so that we always try to cancel it out:

\begin{align} \gcd(4a+3, 7a+5) &= \gcd(4a+3, 3a+2) \\&= \gcd(a+1, 3a+2) \\&= \gcd(a+1, a) \\&= \gcd(1, a) \\&= 1 \end{align}

Things turned out nicely; we might have been left with something like $\gcd(3,a)$; even if that doesn't give us the answer, it is still a much simpler expression than the origina.

We could have treated $a$ as "small" instead, so that each step is designed to reduce the constant term, rather than the coefficient of $a$. Unfortunately, this problem doesn't make for a good example of the difference between the approaches since it results in exactly the same steps.

And as an aside, don't be intimidated by variables! They can make things a little bit more complicated, but $a$ is just as much of a number as $7$ is, and much of what you learn to deal with numbers works equally well for decimals as they do for variables, and a lot of the rest still works just to a lesser and more complicated extent.

Hint $\rm\,\ d\mid 7a\!+\!5,4a\!+\!3\:$ becomes a linear system of equations modulo $\rm\,d,$ with determinant $= 1.\,$ But Cramer's rule works over any commutative ring when the determinant $=1\,$ (or invertible).

$$\rm mod\ d\!:\ \bigg\lbrace\begin{array}{c} 7a+ 5\equiv 0 \\ \rm 4a+3\equiv 0\end{array}\bigg\rbrace \Rightarrow \left[\begin{array}{cc} 7 & 5 \\ 4 & 3\end{array}\right] \left[\begin{array}{c}\rm a \\ 1\end{array}\right]\equiv \left[\begin{array}{c}\rm 0 \\ 0\end{array}\right]\Rightarrow \left[\begin{array}{c}\rm a \\ 1\end{array}\right]\equiv \left[\begin{array}{c}\rm 0 \\ 0\end{array}\right]\Rightarrow 1\equiv 0\,\Rightarrow\, d\mid 1\!-\!0$$

• +10 This is wonderful, particularly the part you noted the Cramer's rule.... I Favorited it. I am very glad, if you left me any references about this method. – Mikasa Feb 9 '13 at 20:38