## You are here

Homeexample of gcd

## Primary tabs

# 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 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:

$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\;\;(\mathop{{\rm mod}}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. 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\;\;(\mathop{{\rm mod}}7),$ |

$n^{2}\!+\!3n\!+\!3\;=\;49k^{2}\!+\!14kr\!+\!21k\!+\!r^{2}\!+\!3r\!+\!3\;\;% \overline{\equiv}\;\;r^{2}\!+\!3r\!+\!3\;\;(\mathop{{\rm mod}}7).$ |

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

Note. The sequence formed by the successive values of $\gcd(f(n),f(n\!+\!1))$ is number A111002 in Sloane’s register (http://www.research.att.com/ njas/sequences/).

## Mathematics Subject Classification

11A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Do other people see entries?

Today I do not see many entries except their TeX sources. Is there some defect in the system now? Do other people see all entries?

Jussi

## Re: Do other people see entries?

Same problem here.

Since yesterday afternoon,

any time I author something new or revise,

there is no html/page image output.

## Re: Do other people see entries?

They should show up again now... I migrated some things on the server yesterday and stuff broke. Apologies.

apk

## Re: Do other people see entries?

They still do not appear though.

Even the old entries are slowly rotting away...

## Re: Do other people see entries?

Ah yes I viewed some "random" entries and saw many were blank.

I tracked the problem down to another loose end from the running instance migration... missing link to the "latex2html" executable =)

I've fixed this and will get all the broken entries re-rendering...

Thanks!

apk

## Re: Do other people see entries?

Page images still seem to come up blank.

Were they supposed to have been fixed

by that same correction too?

## Re: Do other people see entries?

I missed those... I just invalidated the page image cache for the same set of entries. Let me know if you see any other missing content.

apk