Browse Groups

• ## Re: [PrimeNumbers] Re: Algebraic factoring

(45)
• NextPrevious
• ... Surely the largest algebraic factor of 16^137-1 is 4^137+1 which has 83 digits? There are twelve prime factors of 16^137-1 (=2^548-1), which are 3 5 1097
Message 1 of 45 , Feb 1, 2011
View Source
> "j_chrtn" <j_chrtn@...> wrote:
>
>>> Exercise: Find the algebraic factors of 16^137-1.
>>
>> Same game with 61^73-60^73, 140^71-139^71 and 138^127-137^127.
>
> That looks to me like a very different ball game.
> How might L�on-Fran�ois-Antoine help us to find
> /algebraic/ factors in the cases given by Jean-Louis?
>
> Hints for the exercise:
> The 6 non-unit /algebraic/ factors of
> 16^137-1 = f1*f2*f3*f4*f5*f6
> may be found in one's head; no need for a computer.
> The largest, f6, has 42 digits, yet may be written in 7 characters.
> The next-to-largest, f5, may be written in 12 characters.
>

Surely the largest algebraic factor of 16^137-1 is 4^137+1 which has 83
digits?

There are twelve prime factors of 16^137-1 (=2^548-1), which are
3 5 1097 15619 189061 168434085820849 32127963626435681
105498212027592977 32032215596496435569 5439042183600204290159
206875670104957744917147613 921525707911840587390617330886362701

> David

--
Jane
• ... 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, 2011
View Source
"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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.