- 16^137-1 == 16*u^8-1, if we choose u == 16^17 == 2^68.

16*u^8-1 == (2*u^2-2*u+1)(2*u^2-1)(2*u^2+1)(2*u^2+2*u+1).

Substitute back u == 2^68, we get:

(2^137-2^69+1)(2^137-1)(2^137+1)(2^137+2^69+1)

The two middle terms factor algebraically and we end up with

the complete algebraic factorization of 16^137-1 into 6 factors,

one of which is unfortunately the trivial unit factor (1), so

of no use for numerical factorization:

(2^137-2^69+1)

(2-1)

(2^136+2^135+2^134+...+2+1)

(2+1)

(2^136-2^135+2^134-...-2+1)

(2^137+2^69+1)

On 2/1/2011 10:10 AM, Jane Sullivan wrote:

> djbroadhurst wrote:

>> --- In primenumbers@yahoogroups.com,

>> "djbroadhurst"<d.broadhurst@...> wrote:

>>

>>>> Surely the largest algebraic factor of 16^137-1 is

>>>> 4^137+1 which has 83 digits

>>>

>>> Not so, Jane. According to Léon-François-Antoine

>>> the largest algebraic factor has 42 digits.

>>> Try googling him; he is rather useful in this case :-)

>

> In that case, I'm afraid Léon-François-Antoine is wrong.

> (4^137+1)(4^137-1) = 4^274-1 = 4^(2x137)-1 = (4^2)^137-1 = 16^137-1.

> If you say that is not an algebraic factorization, then I'm sorry,

> you're wrong. It is a simple difference of two squares factorization

> (a^2-b^2) = (a+b)(a-b).

>

> We may be talking at cross purposes here: I think you are looking at

> Aurifeuillian factorizations, but there are algebraic factors that are

> not Aurifeuillian.

>

>>

>> Here is a really big hint; try googling:

>>

>> "Léon-François-Antoine" -Fleury

>>

>> /exactly/ as written above.

>

> Yes I googled that, but I can't find anything relating to 137. Maybe I

> gave up too easily.

>

>>

>> David

>

> Best wishes - --- In primenumbers@yahoogroups.com,

"mikeoakes2" <mikeoakes2@...> wrote:

> > ABC2 if($a>$b,($a^137+$b^137)/($a+$b),0) & ($a^137-$b^137)/($a-$b)

It seems that no-one spotted the Aurifeuillian method for

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

> Exercise 4: Find integers (a,b) with min(a,b) > 46225 and

As previously remarked, the trivial Ansatz

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

(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