# Given that $a$ is an odd multiple of $1183$, find the greatest common divisor of $2a^2+29a+65$ and $a+13$.

Given that $a$ is an odd multiple of $1183$, find the greatest common divisor of $2a^2+29a+65$ and $a+13$.

I know there exists some slick technique to simplify this problem. Any hints are greatly appreciated.

We can use Euclid's algorithm for a few steps: $$\gcd(2a^2 + 29a + 65, a + 13) = \gcd(2a^2 + 29a + 65 - 2a(a+13), a+13)\\ = \gcd(3a + 65, a+13) = \gcd(3a+65 - 3(a + 13), a + 13)\\ = \gcd(26, a+13)$$ which is necessarily $1, 2, 13$ or $26$, just by looking at the first term. By factoring $1183$, and considering that $a$ is an odd multiple, you should be able to conclude.

• I'm not sure I'm able to see what $a$ is from this. Nov 11 '17 at 20:41
• I know that $1183=7*13^2$ Nov 11 '17 at 20:41
• And an odd multiple of that, plus $13$, is an even multiple of $13$. Nov 11 '17 at 21:30
• What does that imply? That $a=1183$ since the $gcd(26, 1183+13)=26$ Nov 11 '17 at 21:36
• Isee. The answer is $26$ since the $gcd(26, a+13)=26$ when $a=1183k$ where $k=1,3,5,7,9,...$. Nov 11 '17 at 22:03

HINT

let $d=(2a^2+29a+65,a+13)$. We notice that $-13$ is a root of $2a^2+29a+39$. Another root is $-\frac32$

So we have $2a^2+29a+65=(a+13)(2a+3)+26$

Thus $d=((a+13)(2a+3)+26,a+13)\Rightarrow$ $d|(a+13)(2a+3)+26, d|a+13\Rightarrow d|(a+13)(2a+3)\Rightarrow d|26$