PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] example of gcd (Example)

If one calculates values of the polynomial

$\displaystyle 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\cdot31$
$ 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:

$\displaystyle 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. 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,\,...,\,6\}$, we see that

$\displaystyle n^2\!-\!n\!+\!1 = 49k^2\!+\!14kr\!-\!7k\!+\!r^2\!-\!r\!+\!1 \,\,\overline{\equiv}\,\, r^2\!-\!r\!+\!1 \pmod{7},$
$\displaystyle 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 sides 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 (http://www.research.att.com/˜njas/sequences/).



"example of gcd" is owned by pahio.
(view preamble)

View style:

See Also: divisibility, greatest common divisor, congruence, polynomial congruence, grouping method for factoring polynomials


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: sequence, divisible, polynomial congruences, right, sum, difference, clear, divisor, number, factor, greatest common divisor, prime factor, odd, consecutive, integers, positive, polynomial, calculates

This is version 13 of example of gcd, born on 2005-08-10, modified 2007-09-04.
Object id is 7307, canonical name is ExampleOfGcd.
Accessed 1810 times total.

Classification:
AMS MSC: 11A51 (Number theory :: Elementary number theory :: Factorization; primality)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy
Do other people see entries? by pahio on 2005-08-10 16:03:26
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
[ reply | up ]
Interact
post | correct | update request | add example | add (any)