 mersenneforum.org > Math Generalized wilson's theorem
 Register FAQ Search Today's Posts Mark Forums Read 2004-03-10, 17:02 #1 bouayoun   Jan 2004 3 Posts Generalized wilson's theorem 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 Last fiddled with by bouayoun on 2004-03-10 at 17:03   2004-03-11, 19:24   #2
juergen

Mar 2004

29 Posts Quote:
 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 Last fiddled with by juergen on 2004-03-11 at 19:28   2004-03-12, 00:01   #3
juergen

Mar 2004

111012 Posts Quote:
 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.   2004-03-12, 18:24   #4
Maybeso

Aug 2002
Portland, OR USA

2·137 Posts Quote:
 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post R. Gerbicz Computer Science & Computational Number Theory 138 2015-12-26 17:27 Damian Math 16 2007-11-05 14:55 David John Hill Jr Science & Technology 2 2006-05-10 14:10 T.Rex Math 0 2005-03-29 21:16

All times are UTC. The time now is 03:49.

Mon Jul 4 03:49:39 UTC 2022 up 81 days, 1:50, 0 users, load averages: 1.16, 1.22, 1.17