# All common divisors of $8n + 3$ and $5n + 2$

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

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

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

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.

• 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? – zachary Mar 23 '14 at 23:00
• Yes, that is correct. – Bill Dubuque Mar 23 '14 at 23:05
• 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? – zachary Mar 23 '14 at 23:14
• @zachary See the edited answer. – Bill Dubuque Mar 23 '14 at 23:25
• Thanks for the detailed link! It all makes sense now :) – zachary Mar 23 '14 at 23:33