3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Maybe you could use the Euclidean algorithm $\endgroup$ – Chris Brooks Feb 7 '13 at 6:53
  • $\begingroup$ 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. $\endgroup$ – name Feb 7 '13 at 6:56
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 =/ $\endgroup$ – name Feb 7 '13 at 6:58
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ +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. $\endgroup$ – Mikasa Feb 9 '13 at 20:38

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.