Re: [PrimeNumbers] Re: Algebraic factoring
- View Sourcedjbroadhurst wrote:
> --- In firstname.lastname@example.org,Surely the largest algebraic factor of 16^137-1 is 4^137+1 which has 83
> "j_chrtn" <j_chrtn@...> wrote:
>> "djbroadhurst" <d.broadhurst@> 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.
There are twelve prime factors of 16^137-1 (=2^548-1), which are
3 5 1097 15619 189061 168434085820849 32127963626435681
105498212027592977 32032215596496435569 5439042183600204290159
- View Source--- In email@example.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 andAs 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:
print1([[x,y],[#Str(F),#Str(F)]]" 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).