Primes of the form a^(2^n)+b^(2^n)

[YuL]

Originally Posted by Batalov

Primo on linux is already doing all the Luhn-ification on N threads. No need for manual interventions anymore.

Also, consider all already known GFNs (e.g. http://www.primenumbers.net/prptop/s...096%2Bb%5E4096 off the top of my head ...and there are other sites, of course) before searching for more of these PRPs.

Very interesting link but all the PRPs listed have more than 10000 digits
and I did not find the "other sites"... Thanks, I'll keep searching...

[R.D. Silverman]

Originally Posted by YuL

OK, so this basically confirms that ECPP using Primo is the way to go, I've already proven a few:
8100^1024+203^1024
78^2048+41^2048
150^2048+7^2048
53^4096+2^4096

but 72^8192+43^8192 is 15216 digits long, I wonder how long would it take to produce the certificate, based on the ones I have already done I estimated it would take 4 months, I'm still thinking whether I will start the fight against that behemoth...

Allow me to add the following elementary observation:

We have a^2^n + b^2^n = p, with p a hypothesized prime.

Note that a^2^n = -b^2^n mod p whence

(a/b)^2^n = -1 mod p and by squaring both sides we get

(a/b)^(2^n+1) - 1 = 0 mod p,

Thus proving primality of these numbers is no different from proving
a (non-base 2) Cunningham number prime. One can use the same methods.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Allow me to add the following elementary observation:

We have a^2^n + b^2^n = p, with p a hypothesized prime.

Note that a^2^n = -b^2^n mod p whence

(a/b)^2^n = -1 mod p and by squaring both sides we get

(a/b)^(2^n+1) - 1 = 0 mod p,

Thus proving primality of these numbers is no different from proving
a (non-base 2) Cunningham number prime. One can use the same methods.

Let me add that this of course is totally impractical. I will offer a hint:
Think about the height/size of ab^-1.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Allow me to add the following elementary observation:

We have a^2^n + b^2^n = p, with p a hypothesized prime.

Note that a^2^n = -b^2^n mod p whence

(a/b)^2^n = -1 mod p and by squaring both sides we get

(a/b)^(2^n+1) - 1 = 0 mod p,

Thus proving primality of these numbers is no different from proving
a (non-base 2) Cunningham number prime. One can use the same methods.

The last step, squaring is superfluous and introduces 'extraneous roots'
of the congruence. One would not want to do this. Instead, just
work with (a/b)^2^n + 1

[literka]

Originally Posted by R.D. Silverman

The last step, squaring is superfluous and introduces 'extraneous roots'
of the congruence. One would not want to do this. Instead, just
work with (a/b)^2^n + 1

Do you hate to use parentheses? I looks for me that it should be
(a/b)^[2^(n+1)].
Two parentheses more and in previous posts the same.

[CRGreathouse]

Originally Posted by literka

I looks for me that it should be
(a/b)^[2^(n+1)].

I don't think so. (a/b)^2^n + 1 should mean ((a/b)^(2^n)) + 1 and it looks like it means just that from the context.

Personally I think that superfluous parentheses harm readability. I wouldn't mind one extra, (a/b)^(2^n) + 1, but two or three extra is surely worse.

[YuL]

Originally Posted by R.D. Silverman

The last step, squaring is superfluous and introduces 'extraneous roots'
of the congruence. One would not want to do this. Instead, just
work with (a/b)^2^n + 1

I think I lack the theoretical background which would allow me to get it...
Maybe if someone is kind enough to explain "how it works" (or "how it would work") on say 3^4+2^4 (or 6^8+5^8) I would be able to get a little bit farther..
By the way, while reading this (quoted from http://books.google.fr/books?id=94DaZuV...generalized+fermat+numbers+riesel...el&f=false)
"Also the numbers a^(2^n)+1 with a odd are slightly easier to examine for primality than are the general Fn(a,b)".
I said to myself maybe we could use the same methods as the one used for proving Pépin's test to get a primality test for those numbers but that would have been done long ago if it were that easy...
I'll keeping working on it...

Meanwhile, 53^4096+48^4096 (7063 digits) now has its primality certificate...

[R.D. Silverman]

Originally Posted by YuL

I think I lack the theoretical background which would allow me to get it...
Maybe if someone is kind enough to explain "how it works" (or "how it would work") on say 3^4+2^4 (or 6^8+5^8) I would be able to get a little bit farther..

(3/2)^4 + 1 mod 97 == (3*48)^4 + 1. (mod 97). Note that 144^4 + 1
is divisible by 97. If 97 is not prime, it must be the product of two SMALLER
factors of 144^4 + 1. Show that there are no smaller factors.....

[YuL]

Originally Posted by R.D. Silverman

(3/2)^4 + 1 mod 97 == (3*48)^4 + 1. (mod 97). Note that 144^4 + 1
is divisible by 97. If 97 is not prime, it must be the product of two SMALLER
factors of 144^4 + 1. Show that there are no smaller factors.....

If I rely on the fact that odd prime divisors of a^{2^n}+1 are of the form k.2ⁿ⁺¹+1 it follows that I only have to check for divisibility
by prime numbers of the form k.2³+1 <= square root of 97 and there are no such primes. Is that it?

So, if i figure this right, in the general case:
if there is no prime p = 1 (mod 2ⁿ⁺¹) such that p <= and then =a^{2^n}+b^{2^n} is prime.

Which means that, basically, we are trial factoring (even if the search is restrained to primes of the form k.2ⁿ⁺¹+1), is it the reason why you said in post #14 that "this of course is totally impractical"?

[R.D. Silverman]

Originally Posted by YuL

is it the reason why you said in post #14 that "this of course is totally impractical"?

Essentially, yes.

[YuL]

Originally Posted by YuL

but 72^8192+43^8192 is 15216 digits long, I wonder how long would it take to produce the certificate, based on the ones I have already done I estimated it would take 4 months, I'm still thinking whether I will start the fight against that behemoth...

It is my pleasure to announce that 72^8192+43^8192 is now a proven prime
It entered the ECPP top 20 at rank 5 (but is already at rank 6).
Certification took 193 days (using 3 cores/6 tasks/CPU=Intel Xeon W3530)...