mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-03-10, 17:02   #1
bouayoun
 
Jan 2004

3 Posts
Exclamation 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
bouayoun is offline   Reply With Quote
Old 2004-03-11, 19:24   #2
juergen
 
Mar 2004

29 Posts
Default

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
juergen is offline   Reply With Quote
Old 2004-03-12, 00:01   #3
juergen
 
Mar 2004

111012 Posts
Default

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.
juergen is offline   Reply With Quote
Old 2004-03-12, 18:24   #4
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

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.
Maybeso is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Wilson-prime search practicalities R. Gerbicz Computer Science & Computational Number Theory 138 2015-12-26 17:27
I generalized the fundamental theorem of calculus Damian Math 16 2007-11-05 14:55
Genetics and Wilson's theorem David John Hill Jr Science & Technology 2 2006-05-10 14:10
Generalized Pell Numbers 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.

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