example of gcd

If one calculates values of the polynomial

$$f(x):=x^4+x^2+1$$

on the successive positive integers $n$, one may observe an interesting thing when factoring the values:

$f(1)=\mathrm{\hspace{0.33em}3}$
$f(2)=\mathrm{\hspace{0.33em}21}=\mathrm{\hspace{0.33em}3}\cdot 7$
$f(3)=\mathrm{\hspace{0.33em}91}=\mathrm{\hspace{0.33em}7}\cdot 13$
$f(4)=\mathrm{\hspace{0.33em}273}=\mathrm{\hspace{0.33em}3}\cdot 7\cdot 13$
$f(5)=\mathrm{\hspace{0.33em}651}=\mathrm{\hspace{0.33em}3}\cdot 7\cdot 31$
$f(6)=\mathrm{\hspace{0.33em}1333}=\mathrm{\hspace{0.33em}31}\cdot 43$
$f(7)=\mathrm{\hspace{0.33em}2451}=\mathrm{\hspace{0.33em}3}\cdot 19\cdot 43$
$f(8)=\mathrm{\hspace{0.33em}4161}=\mathrm{\hspace{0.33em}3}\cdot 19\cdot 73$
$f(9)=\mathrm{\hspace{0.33em}6643}=\mathrm{\hspace{0.33em}7}\cdot 13\cdot 73$
$f(10)=\mathrm{\hspace{0.33em}10101}=\mathrm{\hspace{0.33em}3}\cdot 7\cdot 13\cdot 37$
$f(11)=\mathrm{\hspace{0.33em}14763}=\mathrm{\hspace{0.33em}3}\cdot 7\cdot 19\cdot 37$
. . .

It seems as if two consecutive values always have at least one common odd prime factor, i.e. they have the greatest common divisor $>2$.

It is indeed true.  The reason of this fact is not particularlydeep.  It is easily understood if we canfactorize this polynomial (http://planetmath.org/GroupingMethodForFactoringPolynomials):

$$f(x)=(x^2-x+1)(x^2+x+1)$$

Then

$f(n)=(n^2-n+1)(n^2+n+1),$(1)

and the next value is

$f(n+1)=[{(n+1)}^2-(n+1)+1][{(n+1)}^2+(n+1)+1]=(n^2+3n+3)(n^2+n+1).$(2)

Thus $f(n)$ and $f(n+1)$ have as their common factor at least the number $n^2+n+1$, which is $\geqq 3$.

Moreover, we may show that the greatest common divisor of $f(n)$ and $f(n+1)$ is $n^2+n+1$ except in the case  $n\equiv 3(mod7)$  where it is $7(n^2+n+1)$.

Let $d$ be a common divisor, greater than 1, of the first factors $n^2-n+1$ and $n^2+3n+3$ of (1) and (2).  It’s clear that $d$ is odd (http://planetmath.org/OddNumber).  Then $d$ must divide the difference  $(n^2+3n+3)-(n^2-n+1)=2(2n+1)$  and the sum  $(n^2+3n+3)+3(n^2-n+1)=4n^2+6$  and hence also the difference  $2(2n+1)+(4n^2+6)-{(2n+1)}^2=7$.  It means that  $d=7$.  Thus the only possible common prime factor of $n^2-n+1$ and $n^2+3n+3$ is 7.  If we denote  $n=7k+r$  where  $r\in \{0,\mathrm{\hspace{0.17em}1},\mathrm{\dots },\mathrm{\hspace{0.17em}6}\}$,  we see that

$$n^2-n+1=\mathrm{\hspace{0.33em}49}{k}^2+14kr-7k+r^2-r+1\overline{\equiv }{r}^2-r+1(mod7),$$

$$n^2+3n+3=\mathrm{\hspace{0.33em}49}{k}^2+14kr+21k+r^2+3r+3\overline{\equiv }{r}^2+3r+3(mod7).$$

It’s easy to check that the right hand of these polynomial congruences are divisible by 7 only if  $r=3$,  i.e. if  $n\equiv 3(mod7)$.

Note.  The sequence formed by the successive valuesof  $\gcd (f(n),f(n+1))$ is number A111002 in Sloane’sregister (https://oeis.org/A111002http://www.research.att.com/ njas/sequences/).