# 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)\;=\;3$
$f(2)\;=\;21\;=\;3\cdot 7$
$f(3)\;=\;91\;=\;7\cdot 13$
$f(4)\;=\;273\;=\;3\cdot 7\cdot 13$
$f(5)\;=\;651\;=\;3\cdot 7\cdot 31$
$f(6)\;=\;1333\;=\;31\cdot 43$
$f(7)\;=\;2451\;=\;3\cdot 19\cdot 43$
$f(8)\;=\;4161\;=\;3\cdot 19\cdot 73$
$f(9)\;=\;6643\;=\;7\cdot 13\cdot 73$
$f(10)\;=\;10101\;=\;3\cdot 7\cdot 13\cdot 37$
$f(11)\;=\;14763\;=\;3\cdot 7\cdot 19\cdot 37$
. . .

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

 $\displaystyle f(n)\;=\;(n^{2}\!-\!n\!+\!1)(n^{2}\!+\!n\!+\!1),$ (1)

and the next value is

 $\displaystyle 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\pmod{7}$  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,\,1,\,\ldots,\,6\}$,  we see that

 $n^{2}\!-\!n\!+\!1\;=\;49k^{2}\!+\!14kr\!-\!7k\!+\!r^{2}\!-\!r\!+\!1\;\;% \overline{\equiv}\;\;r^{2}\!-\!r\!+\!1\pmod{7},$
 $n^{2}\!+\!3n\!+\!3\;=\;49k^{2}\!+\!14kr\!+\!21k\!+\!r^{2}\!+\!3r\!+\!3\;\;% \overline{\equiv}\;\;r^{2}\!+\!3r\!+\!3\pmod{7}.$

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\pmod{7}$.

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 ExampleOfGcd 2014-10-25 7:09:30 2014-10-25 7:09:30 pahio (2872) pahio (2872) 19 pahio (2872) Example msc 11A51 Divisibility GreatestCommonDivisor Congruences     PolynomialCongruence GroupingMethodForFactorizingPolynomials