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 particularly deep.  It is easily understood if we can factorize 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 values of  $\gcd (f(n),f(n+1))$ is number A111002 in Sloane’s register (https://oeis.org/A111002http://www.research.att.com/ njas/sequences/).

Title	example of gcd
Canonical name	ExampleOfGcd
Date of creation	2014-10-25 7:09:30
Last modified on	2014-10-25 7:09:30
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	19
Author	pahio (2872)
Entry type	Example
Classification	msc 11A51
Related topic	Divisibility
Related topic	GreatestCommonDivisor
Related topic	Congruences
Related topic	PolynomialCongruence
Related topic	GroupingMethodForFactorizingPolynomials