## Re: [PrimeNumbers] Cubes + 1

Expand Messages
• ... We can say even more than that. All primes of the form (a^q + 1) are either 2 (i.e. a=1) or of the form (b^{2^n}+1) where b and n are integers. When
Message 1 of 5 , Dec 2, 2004
On Thu, 2004-12-02 at 14:53, mikeoakes2@... wrote:
>
> In a message dated 02/12/2004 14:46:19 GMT Standard Time,
>
>
> >Better yet, is any number of the form (a^q)+1 prime where q is a
> >prime other than 2?
>
> No.
>
> If q is any odd number > 2, then
> a^q + 1 = (a+1) * (a^(q-1) - a^(q-2) + ... +1)
> and so has (a+1) as a factor.

We can say even more than that. All primes of the form (a^q + 1) are
either 2 (i.e. a=1) or of the form (b^{2^n}+1) where b and n are
integers. When b=2 these are the Fermat numbers which are prime for
0<=n<=4. No others are known and no more are believed to exist.

It's quite easy to show, and a nice simple exercise, that if x has an
odd factor p, then a^x+1 is divisible by (a^{x/p} + 1). The case p=1
is clearly trivial.

Paul
• Hi, ... By Ohakm s Razor, the long division (x^n+1)/(x+1) is the best proof that x+1 divides. However We also can also argue as follows using Baconian
Message 2 of 5 , Dec 3, 2004
Hi,

>From: Paul Leyland <pcl@...>
>To: mikeoakes2@...
>Subject: Re: [PrimeNumbers] Cubes + 1
>Date: 02 Dec 2004 16:46:51 +0000

> > In a message dated 02/12/2004 14:46:19 GMT Standard Time,
> >
> >
> > >Better yet, is any number of the form (a^q)+1 prime where q is a
> > >prime other than 2?
> >
> > No.
> >
> > If q is any odd number > 2, then
> > a^q + 1 = (a+1) * (a^(q-1) - a^(q-2) + ... +1)
> > and so has (a+1) as a factor.
>
>We can say even more than that. All primes of the form (a^q + 1) are
>either 2 (i.e. a=1) or of the form (b^{2^n}+1) where b and n are
>integers. When b=2 these are the Fermat numbers which are prime for
>0<=n<=4. No others are known and no more are believed to exist.

By Ohakm's Razor, the long division (x^n+1)/(x+1) is the best proof that x+1
divides. However We
also can also argue as follows using Baconian Induction for n odd x an
integer.

(x+1)^3 = x^3 + 1 + 3x^2 + 3x

1. x^3 + 1 = (x+1)^3 - 3x(x+1)
div by x+1

(x+1)^5 = x^5 + 1 + (5!/4!1!)x^4 + (5!/3!2!)x^3 + (5!/2!3!)x^2 + (5!/1!4!)x

2. x^5 + 1 = (x+1)^5 - 5x(x^3+1) - 10x^2(x+1)
div by x+1

3. x^7 + 1 = (x_1)^7 - 7x(x^5+1) - 21x^2(x^3+1) - 35x3(x+1)
div by x+1

4. x^9 + 1 = 9x(x^7+1) - 36x^2(x^5+1) - 84x^3(x^3+1) - 126x^4(x+1)
div py x+1
...

since binomial(n,a) = binomial(n,n-a) for a = 1,2..(n-1)/2. The subtracted
terms with these
coefficients can be factored to binomial(n,a)(x^(n-a) + x^a). Now these
terms can be further
fsactored to t_i = binomial(n,a)x^a(x^(n-2a)+1). i = 1,2..(n-1)/2

For n = 3
a = 1, t_1 = 3x(x+1)

For n = 5
a= 1, t_1 = 5x(x^3+1)
a= 2, t_2 = 10x^2(x+1)

For n = 7
a=1, t_1 = 7x(x^5+1)
a=2, t_2 = 21x^2(x^3+1)
a=3, t_3 = 35x^3(x+1)

For n = 9
a=1, t_1 = 9x(x^7+1)
a=2, t_2 = 36x^2(x^5+1)
a=3, t_3 = 84x^3(x^3+1)
a=4, t_4 = 126x^4(x+1)

Continuing this process we get for any odd n, an (n-1)/2 term series to
subrtact from (x+1)^n.
The first (n-1)/2-1 terms of this series contains factors (x^m+1) m<n that