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?
3
$\begingroup$
$\endgroup$
2
$\begingroup$
$\endgroup$
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?
-
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
