20160510, 05:00  #1 
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)^pa^p) can prove primality efficiently. I think so, and I want to imply a new proof of infinite primes of the form (a+1)^pa^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)^pa^p. Any reasons to go with this? Thanks for helping.

20160510, 06:07  #2 
Jun 2003
2·3^{2}·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). 
20160510, 09:52  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
47·197 Posts 
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)^pa^p number have 2kp+1 form. Just like with Mersenne screening, sieving devolves into prefactoring. One can use simple oneliners pregenerated into a shell script file, like this: ../../pfgw64s N k f200"{20386}" l q140^10193139^10193 ../../pfgw64s N k f200"{20422}" l q140^10211139^10211 ../../pfgw64s N k f200"{20446}" l q140^10223139^10223 ../../pfgw64s N k f200"{20486}" l q140^10243139^10243 ... Last fiddled with by Batalov on 20160511 at 00:40 Reason: OEIS has some good links! 
20160510, 10:10  #4 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 
I got the impression from reading the post that he was talking theoretical advances rather than an actual search.

20160510, 18:06  #5 
Apr 2016
32_{8} 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)^pa^p. If every prime factor of a  p has the form kp+1, then p is prime. Theorem 2: Let a  p = (a+1)^pa^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. 
20160510, 18:44  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
47×197 Posts 
What? p is prime to begin with.

20160510, 19:00  #7  
Aug 2006
1749_{16} Posts 
Quote:
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 1154digit number 2^38331, 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:
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. 

20160511, 04:56  #8 
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)^pa^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 p1, 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. 
20160511, 17:03  #9  
Aug 2006
1749_{16} Posts 
Quote:
Quote:
Quote:
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. 

20160511, 18:05  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
47·197 Posts 
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!"

20160511, 19:01  #11  
Aug 2006
5961_{10} Posts 
Quote:


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  20160403 22:27 
Primality proving of DB factors?  jasonp  FactorDB  3  20111017 18:04 
Primality proving  CRGreathouse  Software  13  20110130 14:30 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
fastest general number primalityproving algorithm?  ixfd64  Math  3  20031217 17:06 