3
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

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

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$

$\endgroup$

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.