Generalized wilson's theorem

[bouayoun]

I found that (1) <==> (2)

(1) p is prime and p>=k and gcd(a,p)=1
(2) p divide (k-1)!(p-k)!a^(p-1) - (-1)^k

(1) ==> (2) is it true ?
(2) ==> (1) is it true ?

Can any one help me if this theorem exist ?

and can you prove or disprove this theorem ?

Let A(p,a) = ((p-1)!a^(p-1) +1)/p and p is prime

can any one find prime p such that A(p,11) or A(p,16) are prime ?


Thanks

[juergen]

Originally Posted by bouayoun

I found that (1) <==> (2)

(1) p is prime and p>=k and gcd(a,p)=1
(2) p divide (k-1)!(p-k)!a^(p-1) - (-1)^k

(1) ==> (2) is it true ?
(2) ==> (1) is it true ?

Can any one help me if this theorem exist ?

and can you prove or disprove this theorem ?

Let A(p,a) = ((p-1)!a^(p-1) +1)/p and p is prime

can any one find prime p such that A(p,11) or A(p,16) are prime ?

Hi,

I just read this and maybe I am wrong with what I think, so please correct me.
a^(p-1)-1 for gcd(a,p)=1

is always dividable by p. That is what fermats little theorem says.


((p-1)!a^(p-1) +1)

should be divisable by a prime p it means that:


(p-1)! (a^(p-1) - 1) + (p-1)! + 1

The first part is divisable and can be ignored. So you just need to check

p divides (p-1)! + 1

I am not sure but I think that this has already been proofed (by Gauss I think).
Maybe somebody could catch up here

[juergen]

Originally Posted by juergen

Hi,

should be divisable by a prime p it means that:


(p-1)! (a^(p-1) - 1) + (p-1)! + 1

The first part is divisable and can be ignored. So you just need to check

p divides (p-1)! + 1

I am not sure but I think that this has already been proofed (by Gauss I think).
Maybe somebody could catch up here

Sorry I think thats exactliy how you derived this term?!
Okay and of course there is a proof for the term above from wilson.

There is a proof by wilson which states that

p divides (p-1)! + 1 <=> p is prime

this means that your term is dividable for prime numbers but that doesn't necessarily mean that it is only dividable for prime numbers.
I can't proof that but I guess that it is not guaranteed that a divisor of your term is a prime number.
Anyway it seems that you don't really win something here by combining fermat with wilson as you did it, because Wilson is much stronger than fermat.
The only problem with the wilson "method" is that it is hard to compute. I guess you would be even faster in proofing a number to be prime by trying all possible divisors than with this "method".
I think it is only interesting for theoretical considerations and proofs.
But you wouldn't really have a big advantage if you combine it with another check since it has been proofed to be accurate unlike the FLT.

[Maybeso]

Originally Posted by bouayoun

I found that (1) <==> (2)

(1) p is prime and p>=k and gcd(a,p)=1
(2) p divide (k-1)!(p-k)!a^(p-1) - (-1)^k
...

I reached the same conclusion as juergen,

if p is prime,
a^(p-1) == 1 (mod p), ..... and ..... (p-1)! == (p-1) (mod p), ..... so
[(p-1)! (mod p)][a^(p-1) (mod p)] + 1 ..... == (p-1) (1) + 1 (mod p) ..... == 0 (mod p).

So back to (2), are there any restrictions on k other than p>=k?
I built a spreadsheet to generate n! (mod p), and I didn't find any pairs (k-1)!,(p-k)! whose product was +/-1 (mod p), for the (-1)^k to make it divisible by p. To check the complete expression, I'll have to write a program.

Also, similar to what juergen stated, it is much easier to determine if n is prime with:
s = sqrt(n), ..... gcd(s# (mod n), n) = 1 <=> n prime
-- or --
s = sqrt(n), ..... Product[p prime, p <= s, p^log_p(n) (mod n)] = 0 <=> n composite.