|
|
|
| Don't ask to ask, just ask | |
| PerlMonks |
Re: Re: Finding Primes : Fermat's "small" theoremby Foggy Bottoms (Monk) |
| on Aug 14, 2003 at 09:17 UTC ( [id://283858]=note: print w/replies, xml ) | Need Help?? |
This is an archived low-energy page for bots and other anonmyous visitors. Please sign up if you are a human and want to interact.
The following theorem might help :
Fermat, a French mathematician, once proved that : " If p is a prime number whilst GCD(p,a)==1 then ap-1 is congruous to 1 modulo p." But actually this theorem isn't enough, it helps you prove a number is not prime, not the other way round... Lucas, another French dude, came up with yet another theorem which looks for Mersenne's prime numbers : Given p an odd number, the number M=2p-1 is prime if and only if 2p-1 divides S(p-1) where S(n+1)=S(n)2 - 2, and S(1) = 4. Further down the road, Indian scientists came up with a very interesting paper you may want to check out : they probably have an answer to your problem : <a href=http://www.cse.iitk.ac.in/news/primality.pdf>primality.pdf</a>... Hopefully, I've been of some help - maths are really interesting and I always enjoy digging into them...
In Section
Seekers of Perl Wisdom
|
|
||||||||||||||||||||||||