- Please bear with me if I use the wrong language or get into something

that is already "well known". Being a HS dropout leaves me short on

theory.

The idea that Fermat Number factors always follow the same form got

me to wondering if the same is true for other powers of two. As part

of my investigation, I stumbled on something that appears

rather "odd" to me, so I decided to run it past the group.

It appears that all powers of two follow a similar form to that of

Fermat Number factors. But odd powers and even powers have slightly

different form (rules). The most interesting (to me) are odd powers

of two and especially prime powers.

In the case of 2^P+1 where P is prime and greater than 2. All odd P's

will produce a value that is divisible by 3. Once this is extracted,

all remaining factors (when using a prime P) follow the form of K*P+1.

2^P+1 = 3*(A*P+1)*(B*P+1)

When using an odd non-prime P, all factors are either 3, a prime less

than P, or follow the form K*X+1 where X is a product of a subset of

factors of P.

2^P+1 = 3*(A*X+1)*(B*X+1)

When using an even value of P, all factors are of the form of K*2^

(P+2)+1. This is the same as the form used for Fermat Number factors.

2^P+1 = (A*2^(P+2)+1)*(B*2^(P+2)+1)

This has resulted in a test program that can easily factor 2^P+1, if

the factors are small enough. Naturally if the size of the factors

exceeds 15-20 digits, it takes too long to incrementally test

potential K values.

So the question arises, has anyone run across this curious behavior?

The idea that all powers of 2 should follow this form, strikes me as

odd. However my lack of math background leaves me unable to explain

why it works.

Here are a pair of examples (using prime P values) produced by my

test program to illustrate the concept I'm attempting to describe.

Example: 2^113+1

- - -

2^113+1 is divisible by 3

2^113+1 is divisible by 113*2+1

2^113+1 is divisible by 113*432+1

2^113+1 is divisible by 113*5630000+1

2^113+1 is divisible by 113*4345162560572216+1

Example: 2^211+1

- - -

2^211+1 is divisible by 3

2^211+1 is divisible by 211*22+1

2^211+1 is divisible by 211*46816+1

2^211+1 is divisible by 211*25330536+1

2^211+1 is divisible by 211*943419750+1 - --- "Jay Berg <jberg@...>" <jberg@...> wrote:
> It appears that all powers of two follow a similar form to that of

Yup, that's a real pattern you're seeing. It applies to more than just

> Fermat Number factors. But odd powers and even powers have slightly

> different form (rules). The most interesting (to me) are odd powers

> of two and especially prime powers.

powers of 2 plus or minus 1.

The first thing to do is to break 2^n+1 or 2^n-1 into _algebraic_ factors.

(this works for all bases, not just 2.)

rule 1: If m|n, then a^m-1|a^n-1

rule 2: If m|n and n/m is odd, then a^m+1|a^n+1.

E.g. Let's look at x^30+1

x^10+1, x^6+1, and x^2+1 divides x^30+1,

However, x^2+1 divides x^6+1 and also divides x^10+1, so these don't

directly give us the factorisation of x^30+1.

Grab a symbolic algebra package (gp/pari, Maxima, Maple, Oxygen,

Mathematica, etc.) and see how these expressions split.

Once you've split the power sums (1 is an nth power, so x^n+1 is the sum of

two nth powers) into primitive parts (the irreducible polynomials), then

you'll be left with what's called cyclotomic polynomials. Each one of them

has the property you've noticed, not just x^p+1 and x^(2^n)+1.

> In the case of 2^P+1 where P is prime and greater than 2. All odd P's

(x^p+1)/(x+1) is the 2p-th cyclotomic polymonial, Phi(2p, x), and x+1=3.

> will produce a value that is divisible by 3. Once this is extracted,

> all remaining factors (when using a prime P) follow the form of K*P+1.

> 2^P+1 = 3*(A*P+1)*(B*P+1)

Note that x^p+1 | x^(2p)-1, and divides no other x^q-1 for any q<(2p), and

basically that's why it's the 2p-th cyclotomic polynomial.

The q-th cyclotomic polynomial only has primitive factors of the form 2kq+1.

This is the pattern you're seeing.

> When using an odd non-prime P, all factors are either 3, a prime less

2^P+1 will factor algebraically using rule 2 above. Each part can be treated

> than P, or follow the form K*X+1 where X is a product of a subset of

> factors of P.

> 2^P+1 = 3*(A*X+1)*(B*X+1)

separately.

> When using an even value of P, all factors are of the form of K*2^

For a proof of this for P a power of 2 see my old sci.math posting

> (P+2)+1. This is the same as the form used for Fermat Number factors.

> 2^P+1 = (A*2^(P+2)+1)*(B*2^(P+2)+1)

(now without the typos, I think!)

http://fatphil.org/maths/phi/proof.txt

> This has resulted in a test program that can easily factor 2^P+1, if

This pattern has resulted in David Broadhurst, and then in his footsteps

> the factors are small enough. Naturally if the size of the factors

> exceeds 15-20 digits, it takes too long to incrementally test

> potential K values.

myself and a band of merry men (and HPPA clusters), finding tens of

thousands of factors of 10^10^100+10. The results of this can be found on

Dario Alpern's Factors of Numbers Near a Googolplex web-page.

> So the question arises, has anyone run across this curious behavior?

It was known somewhat even back in Fermat's day, a quarter of a millennium

> The idea that all powers of 2 should follow this form, strikes me as

> odd. However my lack of math background leaves me unable to explain

> why it works.

ago! However some advances were more recent, and are only about a century

old. In one manuscript, Edoard Lucas wrote a comment deriding those who'd

gone before him for missing some of the tricks, the cheeky bugger! Gauss was

a mover and a shaker in the field, and by the time Lucas and Aurefeuille

had worked their wizardry on the field 99% of everything you'd ever need

to know had been discovered.

A good resource for this kind of stuff is Riesel's Prime Numbers and

Computer Methods for Factorisation. It's a bit dear, but worth picking up

2nd hand, and definitely worth a few days in the library.

These are covered in one of the appendices, IIRC (I daren't pull my copy out

of the pile of stuff on my desk, or I'll be playing Texas Pickup).

Phil

=====

"Only an admission that he does possess weapons of mass destruction

would do, sources said: 'The rest is just gesture politics." -- Hoon

"Are you still bombing your wife?" -- Winjer

__________________________________________________

Do you Yahoo!?

Yahoo! Tax Center - forms, calculators, tips, more

http://taxes.yahoo.com/