 mersenneforum.org Unit Differences for Primality Proving
 Register FAQ Search Today's Posts Mark Forums Read  2016-05-10, 05:00 #1 Trejack   Apr 2016 2×13 Posts 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.   2016-05-10, 06:07 #2 axn   Jun 2003 2·32·269 Posts 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).   2016-05-10, 09:52   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

47·197 Posts Quote:
 Originally Posted by Trejack ...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!   2016-05-10, 10:10 #4 Dubslow Basketry That Evening!   "Bunslow the Bold" Jun 2011 40 2016-05-10, 18:06 #5 Trejack   Apr 2016 328 Posts 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.   2016-05-10, 18:44 #6 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 47×197 Posts What? p is prime to begin with.   2016-05-10, 19:00   #7
CRGreathouse

Aug 2006

174916 Posts Quote:
 Originally Posted by Trejack 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 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.   2016-05-11, 04:56 #8 Trejack   Apr 2016 2×13 Posts 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.   2016-05-11, 17:03   #9
CRGreathouse

Aug 2006

174916 Posts Quote:
 Originally Posted by Trejack 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 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 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.   2016-05-11, 18:05   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

47·197 Posts Quote:
 Originally Posted by CRGreathouse ...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!"    2016-05-11, 19:01   #11
CRGreathouse

Aug 2006

596110 Posts Quote:
 Originally Posted by Batalov 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.)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post T.Rex Math 12 2016-04-03 22:27 jasonp FactorDB 3 2011-10-17 18:04 CRGreathouse Software 13 2011-01-30 14:30 ewmayer Math 11 2007-04-23 19:07 ixfd64 Math 3 2003-12-17 17:06

All times are UTC. The time now is 22:02.

Tue Jan 19 22:02:24 UTC 2021 up 47 days, 18:13, 0 users, load averages: 2.08, 1.89, 1.77