- On Thu, 2004-12-02 at 14:53, mikeoakes2@... wrote:
>

We can say even more than that. All primes of the form (a^q + 1) are

> In a message dated 02/12/2004 14:46:19 GMT Standard Time,

> shawns_email_address@... writes:

>

>

> >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.

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,

>From: Paul Leyland <pcl@...>

By Ohakm's Razor, the long division (x^n+1)/(x+1) is the best proof that x+1

>Reply-To: pcl@...

>To: mikeoakes2@...

>CC: shawns_email_address@..., primenumbers@yahoogroups.com

>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,

> > shawns_email_address@... writes:

> >

> >

> > >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.

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

have already been shown

to be div by x+1 and the last term contains the term with factor x+1.

obviously if x+1 divides any of

the other facters, kx^a, in the terms, the statement still holds. Thus,

knowing we can work backwards to the point where n=3 that x+1 divides x^n+1,

x+1 must divide x^n+1 for all n.

CLH