0
$\begingroup$

$n$ is just a natural number. I've been scratching my head over this one for a while, so, I thought I'd seek a little help. My line of thinking is $8n + 3$ is always an odd number, which means, only an odd number can divide it. Thus the only overlapping divisors of $8n + 3$ and $5n + 2$ are odd numbers. But, I can't seem to make the next logical jump as to what this implies. Any help would be great. Thanks!

$\endgroup$
  • 1
    $\begingroup$ You can use the Euclidean algorithm on polynomials. I would start there. $\endgroup$ – ml0105 Mar 23 '14 at 22:43
1
$\begingroup$

Hint: $8\cdot(5n+2)-5\cdot(8n+3)=1$

$\endgroup$
1
$\begingroup$

Hint $\ 8(5n+2)-5(8n+3) = 1 \ $ is divisible by any common divisor of $\ 5n+2,\ 8n+3.\, $ This Bezout Identity can be found by eliminating $\,n,\,$ or by the Extended Euclidean Algorithm.

For the latter, using the verson of the Extended Euclidean Algorithm described here yields

$$\begin{array}{rrr} 8n+3 & 1 & 0\\ 5n+2 & 0 & 1\\ 3n+1 & 1 & -1\\ 2n+1 &-1 & 2\\ n & 2 & -3\\ 1 &\color{#c00}{-5} & \color{#0a0}8\\ \end{array}\qquad\quad$$

where above lines $\,\ a\ \ b\ \ c\ \,$ mean $\ a = b(8n+3) + c(5n+2).\ $ So the Bezout identity is

$$ 1 \,=\, \color{#c00}{-5}(8n+3)+ \color{#0a0}{8}(5n+2)\quad $$

The linked post describes the algorithm in great detail, in a way that is easy to remember.

$\endgroup$
  • $\begingroup$ The bezout identity is gcd = ax + by. Now, if that's the case and the gcd is 1, then that's the only common divisor they share, correct? $\endgroup$ – zachary Mar 23 '14 at 23:00
  • $\begingroup$ Yes, that is correct. $\endgroup$ – Bill Dubuque Mar 23 '14 at 23:05
  • $\begingroup$ Okay, but, I'm not sure how to use the extended euclidean algorithm with those two equations. I googled it, but not luck. Do I just divide the two equations? $\endgroup$ – zachary Mar 23 '14 at 23:14
  • $\begingroup$ @zachary See the edited answer. $\endgroup$ – Bill Dubuque Mar 23 '14 at 23:25
  • $\begingroup$ Thanks for the detailed link! It all makes sense now :) $\endgroup$ – zachary Mar 23 '14 at 23:33

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.