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

Re: [PrimeNumbers] Cubes + 1

Expand Messages
  • Paul Leyland
    ... 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
    • 0 Attachment
      On Thu, 2004-12-02 at 14:53, mikeoakes2@... wrote:
      >
      > 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.

      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
    • cino hilliard
      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
      • 0 Attachment
        Hi,

        >From: Paul Leyland <pcl@...>
        >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.

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