mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-05-10, 05:00   #1
Trejack
 

52608 Posts
Post Unit Differences for Primality Proving

Since I'm on the forum anyway (most of the time I am not here) I decided to bring up an argument as weather or not Unit Differences (form (a+1)^p-a^p) can prove primality efficiently. I think so, and I want to imply a new proof of infinite primes of the form (a+1)^p-a^p (for all primes p). First, how am I able to show that for every prime p, there is a prime of the form (a+1)^p-a^p. Any reasons to go with this? Thanks for helping.
  Reply With Quote
Old 2016-05-10, 06:07   #2
axn
 
axn's Avatar
 
Jun 2003

144316 Posts
Default

Since these do not have the required special form (k*b^n+c), it will be slow to PRP test them. And since N+/-1 doesn't have easy factorization, it will be hard to prove the primality.

I think that there should be infinite number of primes, both for a fixed p (a la GFN), as well as for a fixed (a+1, a) pair (a la Mersenne).
axn is online now   Reply With Quote
Old 2016-05-10, 09:52   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts
Default

Quote:
Originally Posted by Trejack View Post
...form (a+1)^p-a^p ... can prove primality efficiently.
These are quite popular among searchers. There is no primality proof for them (above certain relatively small size) (as axn mentioned already), so they stay PRPs. There is an OEIS sequence A058013 with 25 a values a < 1000 without a known prime.

No (PR)primes are known for a=139, 194, 198 ... (among the smallest) for p>2. Would you like to try to find one?

The factors (both prime and composite) for a (a+1)^p-a^p number have 2kp+1 form.
Just like with Mersenne screening, sieving devolves into pre-factoring.
One can use simple oneliners pre-generated into a shell script file, like this:
../../pfgw64s -N -k -f200"{20386}" -l -q140^10193-139^10193
../../pfgw64s -N -k -f200"{20422}" -l -q140^10211-139^10211
../../pfgw64s -N -k -f200"{20446}" -l -q140^10223-139^10223
../../pfgw64s -N -k -f200"{20486}" -l -q140^10243-139^10243
...

Last fiddled with by Batalov on 2016-05-11 at 00:40 Reason: OEIS has some good links!
Batalov is offline   Reply With Quote
Old 2016-05-10, 10:10   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

I got the impression from reading the post that he was talking theoretical advances rather than an actual search.
Dubslow is offline   Reply With Quote
Old 2016-05-10, 18:06   #5
Trejack
 

57578 Posts
Post

As a matter of fact, I have two primality tests, (one being easy and hard, the other being long and less hard):

Theorem 1: Let a | p = (a+1)^p-a^p.

If every prime factor of a | p has the form kp+1, then p is prime.

Theorem 2: Let a | p = (a+1)^p-a^p

For a prime factor of the form kp+1 divides both a | p and a+m | p, (m > 1), and

kp ≠ 0 or k (mod m), then p *is* prime.

The Theorem 2 I have yet to find a proof for, would make an easy primality test for some primes (often random) by first finding PRPs (p, and kp+1, k(p+n)+1, etc.). If the first step is completed, the second step is very easy.
  Reply With Quote
Old 2016-05-10, 18:44   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

What? p is prime to begin with.
Batalov is offline   Reply With Quote
Old 2016-05-10, 19:00   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by Trejack View Post
As a matter of fact, I have two primality tests, (one being easy and hard, the other being long and less hard):

Theorem 1: Let a | p = (a+1)^p-a^p.

If every prime factor of a | p has the form kp+1, then p is prime.
If I understand properly, you are claiming:
Theorem 1: Let f(a, p) = (a+1)^p - a^p. If every prime factor of f(a, p) has the form kp+1, then p is prime.
This requires a full factorization of a number around a^p, and proving primality of many (large) primes, in order to prove the primality of a small number.

For example, let a = 1 and p = 3833. To prove that 3833 is prime, you need to factor the 1154-digit number 2^3833-1, prove that its prime factors 14193959303, 340789152474053904109001, and 1456746763573933161067575873279902386296729622201833612245757...206132486593909178923032732857568066773972967378787366186497 (where the ... represent 1000 missing digits) are in fact prime, and then verify their remainder mod 3833. This seems like a lot of work, compared to (say) trial division of 3833 up to 61.

Quote:
Originally Posted by Trejack View Post
Theorem 2: Let a | p = (a+1)^p-a^p

For a prime factor of the form kp+1 divides both a | p and a+m | p, (m > 1), and

kp ≠ 0 or k (mod m), then p *is* prime.

The Theorem 2 I have yet to find a proof for, would make an easy primality test for some primes (often random) by first finding PRPs (p, and kp+1, k(p+n)+1, etc.). If the first step is completed, the second step is very easy.
You are proposing:
Conjecture 2: Let f(a, p) = (a+1)^p - a^p. If a prime q = kp+1 divides both f(a, p) and f(a+m, p) with m > 1, and kp ≠ 0 or k (mod m), then p is prime.
This seems to have similar issues to the first.
CRGreathouse is offline   Reply With Quote
Old 2016-05-11, 04:56   #8
Trejack
 

798310 Posts
Post

The for the first one, has already been proven to be true, but hard to compute. The second one, not proven could be easy for *some* primes, but not all. (Like the way the classical tests are only easy for a few primes, but not all). Here is a so called *easier* version of the first theorem (already proven to be true):

Let a | p = (a+1)^p-a^p. If a | p is a semiprime (or proven to be one), then p is prime or p is a perfect square.

Sounds simple, right?

The second one (not proven, but likely to be true), can be shown to prove large primes p by knowing a few other PRPs of the form kp+1, and with modular exponentiation and quick evaluations of expressions, to see weather or not one of these PRPs divides a unit difference a | p and a+m | p. The third part should be easy if the first two are completed. You could primality test a small factor of p-1, and have *p* written of the form kp+1, for this theorem making only the second step complicated! (As this implies the first theorem)

Sorry if it seems confusing, and I will try to show you a (slightly large) example.
  Reply With Quote
Old 2016-05-11, 17:03   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by Trejack View Post
Theorem 2: Let a | p = (a+1)^p-a^p

For a prime factor of the form kp+1 divides both a | p and a+m | p, (m > 1), and

kp ≠ 0 or k (mod m), then p *is* prime.
Quote:
Originally Posted by CRGreathouse View Post
You are proposing:
Conjecture 2: Let f(a, p) = (a+1)^p - a^p. If a prime q = kp+1 divides both f(a, p) and f(a+m, p) with m > 1, and kp ≠ 0 or k (mod m), then p is prime.
Quote:
Originally Posted by Trejack View Post
The for the first one, has already been proven to be true, but hard to compute. The second one, not proven could be easy for *some* primes, but not all.
So let p = 9, a = 1, q = 73, k = 8, and m = 20. Substituting these into your conjecture, I get:
Conjecture 2 (special case): If a prime 73 = 8*9+1 divides both f(1, 9) = 7*73 and f(21, 9) = 19 * 73 * 109 * 163 * 16759 with 20 > 1, and 8*9 ≠ 0 or 8 (mod 20), then 9 is prime.
CRGreathouse is offline   Reply With Quote
Old 2016-05-11, 18:05   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts
Wink

Quote:
Originally Posted by CRGreathouse View Post
...then 9 is prime.
This conjecture is as good as the conjecture from the anecdote that compares a mathematician to a physicist and a technologist. One of them goes "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime, 13 is prime... there we have it -- all odd numbers are prime!"
Batalov is offline   Reply With Quote
Old 2016-05-11, 19:01   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Batalov View Post
This conjecture is as good as the conjecture from the anecdote that compares a mathematician to a physicist and a technologist. One of them goes "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime, 13 is prime... there we have it -- all odd numbers are prime!"
I also have proofs, subject to the same conjecture, of the primality of 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, 169, 171, 175, 177, 183, 185, 187, 195, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, 255, 259, 261, 265, 267, 273, 275, 279, .... (I didn't think it was sporting to include the even primes it found.)
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Primality proving of DB factors? jasonp FactorDB 3 2011-10-17 18:04
Primality proving CRGreathouse Software 13 2011-01-30 14:30
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
fastest general number primality-proving algorithm? ixfd64 Math 3 2003-12-17 17:06

All times are UTC. The time now is 13:03.


Fri Dec 3 13:03:45 UTC 2021 up 133 days, 7:32, 0 users, load averages: 1.83, 1.35, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.