3
$\begingroup$

A problem I found yesterday says to prove $\gcd(n^3+3n+1, 7n^3+18n^2-n-2)=1$ for all integers $n\ge 1$. To begin, I used the Euclidean algorithm to observe that $7n^3+18n^2-n-2=7\left(n^3+3n+1\right)+\left(18n^2-22n-9\right)$, so $$\gcd(n^3+3n+1, 7n^3+18n^2-n-2)=\gcd(n^3+3n+1, 18n^2-22n-9).$$ From here, I got stuck however, since the next step of polynomial division involves rational numbers. I observed that the GCD cannot be a multiple of $3$, since if $3$ divides the term on the right, then $3\mid n$, however, then $3\nmid n^3+3n+1$. Similarly, by a parity argument, both terms are odd. Any suggestions for how to finish the problem from here?

$\endgroup$
1
$\begingroup$

It appears the problem fails for $n=309$. WolframAlpha says so here. See discussion on AoPS here on how to find $n=309$.

$\endgroup$
2
$\begingroup$

HINT: Because both terms are odd, you know that $$\gcd(n^3+3n+1,18n^2-22n-9)=\gcd(2(n^3+3n+1),18n^2-22n-9).$$ A similar argument works for the prime $3$, and perhaps for $3^2$. Can you take it from here?

$\endgroup$
  • 1
    $\begingroup$ Then,$$\gcd(n^3+3n+1, 18n^2-22n-9)=\gcd(18(n^3+3n+1), 18n^2-22n-9)=\gcd(18n^3+54n+18, 18n^2-22n-9).$$ Using the Euclidean Algorithm again, $$\gcd(18n^3+54n+18, 18n^2-22n-9)=\gcd(18n^3+54n+18-(n+1)(18n^2-22n-9), 18n^2-22n-9)=\gcd(4n^2+95n+37, 18n^2-22n-9).$$ At this point, more repeated use of the Euclidean Algorithm reveals $$\gcd(18n^2-22n-9-4(4n^2+95n+37), 4n^2+95n+37)=\gcd(2n^2-402n-157, 4n^2+95n+37).$$ Once again, $$\gcd(4n^2+95n+37, 2n^2-402n-157)=\gcd(899n+351, 2n^2-402n-157).$$ This approach seems very computational however, any ideas for an easier method involving linear combinations? $\endgroup$ – Justin Stevens Nov 14 '17 at 22:06
  • 1
    $\begingroup$ Exactly. Mind the case $9\mid n$ though. $\endgroup$ – Servaes Nov 14 '17 at 22:10

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.