example of gcd

If one calculates values of the polynomial


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

f(1)= 3
f(2)= 21= 37
f(3)= 91= 713
f(4)= 273= 3713
f(5)= 651= 3731
f(6)= 1333= 3143
f(7)= 2451= 31943
f(8)= 4161= 31973
f(9)= 6643= 71373
f(10)= 10101= 371337
f(11)= 14763= 371937
. . .

It seems as if two consecutive values always have at least one common odd prime factor, i.e. they have the greatest common divisorMathworldPlanetmathPlanetmath >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(n)=(n2-n+1)(n2+n+1), (1)

and the next value is

f(n+1)=[(n+1)2-(n+1)+1][(n+1)2+(n+1)+1]=(n2+3n+3)(n2+n+1). (2)

Thus f(n) and f(n+1) have as their common factor at least the number n2+n+1, which is 3.

Moreover, we may show that the greatest common divisor of f(n) and f(n+1) is n2+n+1 except in the case  n3(mod7)  where it is 7(n2+n+1).

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

n2-n+1= 49k2+14kr-7k+r2-r+1¯r2-r+1(mod7),
n2+3n+3= 49k2+14kr+21k+r2+3r+3¯r2+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  n3(mod7).

Note.  The sequenceMathworldPlanetmath 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 CongruencesMathworldPlanetmathPlanetmathPlanetmathPlanetmath
Related topic PolynomialCongruence
Related topic GroupingMethodForFactorizingPolynomials