# Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$.

I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = gcd(a+cb,b). So I can do things like decide that $\gcd(n^3 + 1, n^2 + 2) = \gcd((n^3+1) - n(n^2+2),n^2+2) = \gcd(1-2n,n^2+2)$ and then using Bezout's theorem I can get $\gcd(1-2n,n^2+2)= r(1-2n) + s(n^2 +2)$ and I can expand this to $r(1-2n) + s(n^2 +2) = r - 2rn + sn^2 + 2s$ However after some time of chasing this path using various substitutions and factorings I've gotten nowhere.

Can anybody provide a hint as to how I should be looking at this problem?

-
Just a quick comment on the formatting: \gcd() will make $gcd$ look like: $\gcd$. –  JavaMan Feb 16 '12 at 4:41
Quick tip in general ; it is not very useful to switch to Bezout's theorem to compute $\gcd$'s ; one often just uses the Euclidean algorithm or work with divisors/congruences, but rarely this. –  Patrick Da Silva Feb 16 '12 at 4:52

As you note, $\gcd(n^3+1,n^2+2) = \gcd(1-2n,n^2+2)$.

Now, continuing in that manner, \begin{align*} \gcd(1-2n, n^2+2) &= \gcd(2n-1,n^2+2)\\ &= \gcd(2n-1, n^2+2+2n-1)\\ &= \gcd(2n-1,n^2+2n+1)\\ &= \gcd(2n-1,(n+1)^2). \end{align*}

Consider now $\gcd(2n-1,n+1)$. We have: \begin{align*} \gcd(2n-1,n+1) &= \gcd(n-2,n+1) \\ &= \gcd(n-2,n+1-(n-2))\\ &=\gcd(n-2,3)\\ &= 1\text{ or }3. \end{align*} Therefore, the gcd of $2n-1$ and $(n+1)^2$ is either $1$, $3$, or $9$. Hence the same is true of the original gcd.

-
so I just didn't chase it far enough down the rabbit hole? –  AvatarOfChronos Feb 16 '12 at 4:53
@AvatarOfChronos: Pretty much; I noticed we could get a perfect square using $n^2+2$ and $1-2n$ (which immediately signaled how we would get "$1$ or $3$ or $9$"); from there, everything flowed easily. –  Arturo Magidin Feb 16 '12 at 4:55

Playing around along the lines you were exploring should work. Let's do it somewhat casually, aiming always to reduce the maximum power of $n$.

If $m$ divides both $n^3+1$ and $n^2+2$, then $m$ divides $n(n^2+2)-(n^3+1)$, so it divides $2n-1$. (You got there.)

But if $m$ divides $n^2+2$ and $2n-1$, then $m$ divides $2(n^2+2)-n(2n-1)$, so it divides $n+4$. (This move is slightly risky. In some cases this kind of move could introduce spurious common divisors. But (i) In this case it doesn't; and (ii) We will be checking at the end anyway whether our list of candidates is correct.)

But if $m$ divides $n+4$ and $2n-1$, then $m$ divides $2(n+4)-(2n-1)$, so it divides $9$.

We did not work explicitly with greatest common divisors, so we are not finished. We must show that $1$, $3$ and $9$ are all achievable. For $\gcd$ $1$, let $n=0$. For $\gcd$ $3$, let $n=2$. For $\gcd$ $9$, let $n=4$.

-
gcd(ca,b)|cg(a,b), so the only spurious factor that could be added to gcd(n^2+2,2*n-1) by calculating (2*(n^2+1),2*n-1) instead of, is therefore 2. But 2 will not be added because 2*n-1 is odd. –  miracle173 Feb 16 '12 at 7:20
i think it is not necessary to schow for each of the numbers 1,3,9 that there is an appropriate n. this is not part of the question. if an arbitrary common divisor of n^3+1 and n^2+2 divides 9 than you have shown that gcd(n^3+1,n^2+2) is 1,3 or 9 –  miracle173 Feb 16 '12 at 7:30
@miracle173: Indeed the only possible spurious factor is $2$, which cannot happen. As to your second comment, it is a matter of interpretation. To me, the "$1$, $3$, or $9$" carries the connotation that each can happen. We can then either work with $\gcd$ all the way, or do like we often do with equations: transform freely, and check at the end that we have not introduced "extraneous roots." –  André Nicolas Feb 16 '12 at 8:01

I'm carrying out a congruence procedure, so that you have different approaches.

If $p \, | \, n^3 + 1$ and $p \, | \, n^2 + 2$, then $2n \equiv 1 \pmod p$, which means $$-8 \equiv 8n^3 = (2n)^3 \equiv 1^3 \equiv 1 \pmod p,$$ hence $9 \equiv 0 \pmod p$ and assuming $p$ is a prime means $p = 3$. This means the $\gcd$ is a power of $3$. Now I'm checking powers of $3$ by hand using congruences.

EDIT : As miracle's comment says, I got far too carried away by liking primes so much : a good way to say that this proof is done is that $9 \equiv 0 \mod p$ means $p \, | \, 9$, hence getting examples is enough to get our answer.

If $n \equiv 0 \pmod 3$, this $\gcd$ is clearly $1$.

If $n \equiv 1 \pmod 3$, $n^3 + 1 \equiv 1 \pmod 3$ so that the $\gcd$ is again $1$.

If $n \equiv 2 \pmod 3$, then $9 \, | \, n^3 + 1$ and $3 \, | \, n^2 + 2$. But letting $n = 3k+2$ we notice that \begin{align*} (3k+2)^3 + 1 & = (3k)^3 + 3 \cdot (3k)^2 \cdot 2 + 3 \cdot 3k \cdot 2^2 + 2^3 +1 \\& \equiv 9(k+1)\pmod{27} \end{align*} which is $0$ if and only if $k \equiv 2 \pmod 3$. Carry on! We get $$(3k+2)^2 + 2 \equiv (3k)^2 + 2 \cdot (3k) \cdot 2 + 2^2 + 2 = 9k^2 + 12k + 6 \equiv 0 \pmod{27}$$ if and only if $$3k^2 + 4k + 2 \equiv 0 \pmod 9$$ but reading this $\bmod 3$, we get $k \equiv 1 \pmod 3$, a contradiction.

I must say it is a little longer than the $\gcd$ proof : I expected people to put up to $\gcd$ proof, so I've shown this one instead. I like those proofs because they're mechanical ; I didn't have to think much to write it, I just chose to go this way and things always go as expected (assuming the question asks something that's true, obviously)... Now I've only proven that the $\gcd$ divides $9$ : again, to show that the $3$ possibilities actually happen, pull off examples like Andre Nicolas.

Hope that helps,

-
@Arturo : Oh wow, I had never heard of the \pmod and \bmod command before ; it brings light upon my codes! Thanks a lot for this edit. Greatly appreciated : I used to define a new command to get the ( )'s to pop up correctly... this will help. –  Patrick Da Silva Feb 16 '12 at 5:49
\pmod for P arenthetical mod, \bmod for B inary mod; \mod just gives the wrong spacing all around. –  Arturo Magidin Feb 16 '12 at 5:50
@Arturo : Yes, that's exactly why I was feeling pain while using it. In my codes I redefined the mod command to make it suit better my using, but LaTeX was already smart, I was just not knowing how. –  Patrick Da Silva Feb 16 '12 at 5:53
i think after you have shown that 9=0 (mod p) you are done. you have assumed nothing special about p except that it is a common divisor of n^3+1 and n^2+2. So if you choose p:=gcd(n^3+1,n^2+2) if foolows that gcd is 1,3 or 9 –  miracle173 Feb 16 '12 at 7:36

Let $\:\rm d = (n^3+1,\:n^2+2).\:$ Observe that $\rm \ d \in \{1,\:3,\:9\} \iff\ d\:|\:9\iff 9\equiv 0\pmod d\:.$

mod $\rm (n^3\!-a,n^2\!-b)\!:\ a^2 \equiv n^6 \equiv b^3\:$ so $\rm\:a=-1,\:b = -2\:\Rightarrow 1\equiv -8\:\Rightarrow\: 9\equiv 0\:. \ \$ QED

Or, if you don't know congruence arithmetic, since $\rm\: x-y\:$ divides $\rm\: x^2-y^2$ and $\rm\: x^3-y^3$

$\rm n^3-a\ |\ n^6-a^2,\:\ n^2-b\ |\ n^6-b^3\ \Rightarrow\ (n^3-a,n^2-b)\ |\ n^6-b^3-(n^6-a^2) = a^2-b^3$

Note how much simpler the proof is using congruences vs. divisibility relations on binomials. Similar congruential proofs arise when computing modulo ideals generated by binomials.

-
Words can be useful in an elegant proof. Perhaps you could've added some of those. But nice idea though. –  Patrick Da Silva Feb 16 '12 at 7:41
The fighting of the default math font is also very characteristic. It seems there are at least two of you out there doing that too! –  Mariano Suárez-Alvarez Feb 16 '12 at 8:24
@Mariano The formatting is done by Emacs macros borrowed from a friend. –  Math Gems Feb 16 '12 at 8:31
I imagined as much, as you imagine. –  Mariano Suárez-Alvarez Feb 16 '12 at 8:53