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

Re: [PrimeNumbers] Re: Algebraic factoring

Expand Messages
  • Jack Brennen
    Actually, the original number 16^137-1 is equal to 2^548-1, correct? x^548-1 is easily seen to be divisible by x^4-1, which is divisible by x^2+1. So 2^548-1
    Message 1 of 45 , Feb 2 3:20 PM
    • 0 Attachment
      Actually, the original number 16^137-1 is equal to 2^548-1, correct?

      x^548-1 is easily seen to be divisible by x^4-1, which is divisible
      by x^2+1.

      So 2^548-1 is divisible by 2^2+1.



      On 2/2/2011 3:08 PM, kraDen wrote:
      > Hi David,
      > --- In primenumbers@yahoogroups.com, "djbroadhurst"<d.broadhurst@...> wrote:
      >>
      >>
      >>
      >> --- In primenumbers@yahoogroups.com,
      >> "kraDen"<kradenken@> wrote:
      >>
      >>> My question is how does one know algebraically
      >>> (or at least without trial dividing) that
      >>> 2^2+1 divides 2^137+2^69+1
      >>
      >> We want to show that y = 2^2 + 1 divides N = 2^137 + 2^69 + 1.
      >> Let u = 2^68. Then
      >> N - y = 2*u^2 + 2*u - 2^2 = 2*(u-1)*(u+2).
      >> But y divides u - 1 = (y-1)^34 - 1. Hence y divides N - y.
      >> Hence y divides N and we are done.
      > Thankyou.
      > However this seems to be proving it is after already knowing it is (hopefully that statement is understandable).
      > However this still doesn't explain to to me how you (algebraically) knew that 2^2+1 was a divisor.
      > Instead it looks like you have achieved the factor by trial division and then proved it algebraically.
      >
      > cheers
      > Ken
      >
      >
      >> Note that we do not need to compute the value of 2^2+1.
      >> I believe that I can do that in my head, but fortunately
      >> it is not necessary for this algebraic exercise :-)
      >>
      >> David
      >>
      >
      >
      >
      >
      > ------------------------------------
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      > The Prime Pages : http://www.primepages.org/
      >
      > Yahoo! Groups Links
      >
      >
      >
      >
      >
    • djbroadhurst
      ... It seems that no-one spotted the Aurifeuillian method for ... As previously remarked, the trivial Ansatz (a,b) = (x^2,y^2) cannot solve Exercise 4.
      Message 45 of 45 , Feb 7 8:56 PM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "mikeoakes2" <mikeoakes2@...> wrote:

        > > ABC2 if($a>$b,($a^137+$b^137)/($a+$b),0) & ($a^137-$b^137)/($a-$b)
        > > a: from 216 to 262
        > > b: from 216 to 262
        > > does not give a double hit, as Mike has probably checked.
        > Your intuition is spot on, as per usual, good Sir:
        > they were pfgw jobs of precisely this form that I ran.

        It seems that no-one spotted the Aurifeuillian method for

        > Exercise 4: Find integers (a,b) with min(a,b) > 46225 and
        > N(a,b) = (a^137 - b^137)/(a - b) equal to the product of
        > two primes, each with less than 330 decimal digits.

        > Comment: This may solved, systematically, in less than
        > 30 seconds, including the time for primality proofs.

        As previously remarked, the trivial Ansatz
        (a,b) = (x^2,y^2) cannot solve Exercise 4.

        Solution: Aurifeuillian algebraic factorization results from
        (a,b) = (x^2,137*y^2), with min(x,sqrt(137)*y) > 215. Since
        max(x,sqrt(137)*y) < 10^(329/136) < 263, we have x in the
        range [216,262] and y in the range [19,22], yielding a pair
        of PRPs in 0.27 seconds and a proof in 26 seconds:

        {g=factor((z^274-137^137)/(z^2-137))[,1]~;
        for(x=216,262,for(y=19,22,if(gcd(x,y)==1,
        f=abs(y^136*subst(g,z,x/y));
        if(ispseudoprime(f[1])&&ispseudoprime(f[2]),F=f;
        print1([[x,y],[#Str(F[1]),#Str(F[2])]]" in "gettime" ms. ")))));
        if(isprime(F)==[1,1],print("Proof in "round(gettime/10^3)" sec."));}

        [[220, 21], [323, 329]] in 270 ms. Proof in 26 sec.

        Hence we have the solution N(a,b) = P323*P329,
        with (a,b) = (220^2,137*21^2) = (48400,60417).

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.