14
$\begingroup$

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?

  • 0
    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.2012-02-16

6 Answers 6

15

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.

  • 0
    @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.2012-02-16
4

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$.

  • 0
    @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."2012-02-16
4

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,

  • 0
    @miracle : Hm. Actually I thought about it but I didn't feel very comfortable with it for some reason. But yeah, since $-8 \equiv 1 \pmod p$, this means $p \, | \, 9$. Damn it.2012-02-16
2

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.

  • 0
    I imagined as much, as you imagine.2012-02-16
0

Let $d=\gcd(n^3+1,n^2+2)$ then we have: $d|n^3+2n\Rightarrow\ d|2n-1\Rightarrow\ d|2n^2-n\Rightarrow\ d|2n^2+4\Rightarrow\ d|n+4\Rightarrow\ d|2n+8\Rightarrow\ d|9\Rightarrow\ d=1,3,9$

0

The extended Euclidean algorithm gives $ 9 = (2 n + 1)(n^3+1)+(-2 n^2 - n + 4)(n^2+2) $ and so $\gcd(n^3 + 1, n^2 + 2)$ divides $9$.