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.

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).

[QUOTE=Trejack;433464]...form (a+1)^p-a^p ... can prove primality efficiently.[/QUOTE]
These are [URL="http://www.primenumbers.net/prptop/searchform.php?form=x^n-y^n&action=Search"]quite popular[/URL] 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 [URL="https://oeis.org/A058013"]OEIS sequence A058013[/URL] with [URL="https://oeis.org/A058013/a058013_4.txt"]25 a values[/URL] 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 [B][COLOR=DarkRed]2[/COLOR]kp+1[/B] form.
Just like with Mersenne screening, sieving devolves into [I]pre-factoring[/I].
One can use simple oneliners pre-generated into a shell script file, like this:
[c]../../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
...[/c]

I got the impression from reading the post that he was talking theoretical advances rather than an actual search.

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.

What? p is prime to begin with.

[QUOTE=Trejack;433531]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.[/QUOTE]

If I understand properly, you are claiming:[INDENT]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.[/INDENT]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=Trejack;433531]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.[/QUOTE]

You are proposing:
[INDENT]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.[/INDENT]
This seems to have similar issues to the first.

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.

[QUOTE=Trejack;433531]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]

[QUOTE=CRGreathouse;433541]You are proposing:
[INDENT]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.[/INDENT][/QUOTE]

[QUOTE=Trejack;433591]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.[/QUOTE]

So let p = 9, a = 1, q = 73, k = 8, and m = 20. Substituting these into your conjecture, I get:
[INDENT]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.[/INDENT]

[QUOTE=CRGreathouse;433641]...then 9 is prime.[/QUOTE]
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 -- [B]all odd numbers are prime[/B]!" :rolleyes:

[QUOTE=Batalov;433650]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 -- [B]all odd numbers are prime[/B]!" :rolleyes:[/QUOTE]

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.)