## 2 to odd powers, factoring

Expand Messages
• 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
Message 1 of 2 , Mar 3, 2003
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
• ... Yup, that s a real pattern you re seeing. It applies to more than just powers of 2 plus or minus 1. The first thing to do is to break 2^n+1 or 2^n-1 into
Message 2 of 2 , Mar 3, 2003
--- "Jay Berg <jberg@...>" <jberg@...> wrote:
> 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.

Yup, that's a real pattern you're seeing. It applies to more than just
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
> 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)

(x^p+1)/(x+1) is the 2p-th cyclotomic polymonial, Phi(2p, x), and x+1=3.
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
> 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)

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

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

For a proof of this for P a power of 2 see my old sci.math posting
(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
> 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.

This pattern has resulted in David Broadhurst, and then in his footsteps
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?
> 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.

It was known somewhat even back in Fermat's day, a quarter of a millennium
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

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/
Your message has been successfully submitted and would be delivered to recipients shortly.