mersenneforum.org > Math Generalized wilson's theorem
 User Name Remember Me? Password
 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

 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔