Primality issue

[DrJones]

I love math, but my math is rusty. Could someone please help me?

I was designing a naïve iterative algorithm for finding primes, based on the following idea:

Being N>1 an integer, N is said to be prime iff it is coprime with every integer A <= sqrt(N)", that implies that N is prime iff it is coprime with the number M resulting of multiplying every number from 1 to the first number greater than sqrt(N) (However, I will use (N-1)! instead of mul(sqrt(N)), as it looks easier to explain).

By Bézout's identity, we have that there exist integers X and Y such that xN + y(N-1)! = 1.
This implies that (N-1)! = (1-Nx)/y (for y!=0).

Now, I was interested in knowing which values of N satisfy that, for N prime, (1 + N!) is prime.

Using Bézout's identity again, I get u(1+N!) + v(N!) = 1.
Replacing (N-1)!... u(1+N(1-Nx)/y) + v(N(1-Nx)/y) = 1.
Cleanup step... u + (Nu - N^2ux)/y + Nv/y - N^2xv/y = 1.
After multiplying by y... uy + Nu - N^2ux + Nv - N^2xv = y.

Which is a mess. I was resolved in getting something from that equation, though, so I started assigning values to the variables:

For u=0 --> Nv - N^2xv = y (y != 0)
For x=1 --> Nv - N^2v = y (y != 0)

However, the last equation always work for any N distinct of 0 or 1, which has to be wrong because (1 + 5!) = 121 = 11^2, and therefore it's not prime.

I must have made a mistake somewhere.

[extro...*]

[old grey mare*]

Yes. Bezout's Identity says that for A, B coprime there exists u,v such that uA+vB=1. It does NOT say that for all u there exists a v such that uA+vB=1. Maybe that is your confusion.

[DrJones]

Thank you!

I thought I could use Bezout's Identity to start finding big primes soon. It seems that it won't work.

[CrystyB]

Factoris says that:

[DrJones]

Cool! Thank you very much

I've been testing the Program that calculates the Bezout Relation.

From what I've seen, it looks that for N>2 prime, the Bezout Relation

"Nx + (N-1)!y = 1"

has always a solution for "y = (-1)"
I have no way to prove this, of course. If it were true, it would simplify my equation a lot.

(N-1)! = Nx - 1 where x is in Z, for N prime.

In other words, there exists a number x in Z such that:

x = (N-1)!/N + 1/N for N prime. (this shows that x > 0)

Which is true if (N-1)! mod N = N-1 for every N prime. I can't prove if this is true, either.

Finally, to know if for N prime, (1+N!) is prime, I have to test if (1+N!) is coprime with... ((N!)!) (gosh!)

u(1+N!) - (N!)! = 1.
u(1+Nx-1)) - (Nx-1)! = 1.
uNx - (Nx-1)! = 1.
uNx = 1 + (Nx-1)!.
u = 1/Nx + (Nx-1)!/Nx.

If I name "Nx = z" then,

u = 1/z + (z-1)!/z.

So, u will be an integer if "(z-1)! mod z = z-1" for z prime.

EDIT: This equals to "(z-2)! mod z = 1" for z prime.

I can only say... Wow!!

[old grey mare*]

[extro...*]

[extro...*]

[DrJones]

Yeah, it can't find primes over 2209 with just 64 bit integers.

However, to test if 523 is prime, for example, it has to perform just 6 mod operations:

(223092870 = 2x3x5x7x11x13x17x19x23 has been calculated in previous steps)
223092870 mod 523 = 421 (this is the only operation involving big numbers)
523 mod 421 = 102
421 mod 102 = 13
102 mod 13 = 11
13 mod 11 = 2
11 mod 2 = 1 (this step proves 523 is prime)
2 mod 1 = 0 (this step is superfluous)
Greatest common divisor = 1 --> 523 is prime.

while the classic sieve has to perform 8 mod operations and 8 additional reads from arrays/files (it can avoid doing 8 comparations with sqrt(523) if it searchs the list backwards, though):

23 > sqrt(523)
19 < sqrt(523)
523 mod 19 = 10
read previous
523 mod 17 = 13
read previous
523 mod 13 = 3
read previous
523 mod 11 = 6
read previous
523 mod 7 = 5
read previous
523 mod 5 = 3
read previous
523 mod 3 = 1
read previous
523 mod 2 = 1
Stop. 523 is prime.

So, yes. My algorithm becomes soon impractical for standard integers, and it is still a naive method, which is not a good way for finding primes. The doubt is if it is faster in time than old sieve. The euclidean algorithm has time O(n^2) for two consecutive Fibonacci numbers, but that is not likely to happen except at the very beginning. On average, it takes O(12 ln 2/pi^2 ln n) == O(0.843 ln n).

Erathostenes sieve takes O(N log log N), as seen on http://portal.acm.org/citation.cfm?id=62072.