Loading ...
Sorry, an error occurred while loading the content.

2 to odd powers, factoring

Expand Messages
  • Jay Berg <jberg@eCompute.org>
    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
    • 0 Attachment
      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
    • Phil Carmody
      ... 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
      • 0 Attachment
        --- "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
        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/
      Your message has been successfully submitted and would be delivered to recipients shortly.