You are not logged in.
#1 2009-06-08 20:16:05
- noobard
- Member
Offline
Prime Numbers!!!
Wilson's theorem can be used by programmers to check whether a number is prime or not
It is :
If n is prime then (n-1)!+1 should be divisible by n
Last edited by noobard (2009-06-08 20:16:38)
Everything that has a begining has an EnD!!!
#2 2009-06-08 20:20:37
- bobbym
- Administrator
Offline
Re: Prime Numbers!!!
Hi noobard;
Theoretically yes but only for small numbers.
Supposing you wanted to test whether the repunit 1111111111111111111 were prime. You would have to compute 1111111111111111110! + 1 a number with 19568292231841581432 digits and mod it by 1111111111111111111.
Last edited by bobbym (2009-06-08 20:32:17)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#3 2009-06-09 13:46:24
- noobard
- Member
Offline
Re: Prime Numbers!!!
ya bobbym ... true as u say.............................
The factorial becomes sad for large numbers...that is why i wrote this algorithm is for the programmers ......and i found this pretty amusing when i saw a question quoted as
If n is a number such that (n-1)!+1 is divisible by n...Find the number of n (between 1-100) satisfying this ............so the answer was at hand 25 ....
Everything that has a begining has an EnD!!!
#4 2009-06-10 07:39:44
- Avon
- Full Member
Offline
Re: Prime Numbers!!!
I think bobbym's point is that, even for computers, the calculation of large factorials is not a very good way of testing if numbers are prime.
At university, if I type Factorization(1111111111111111111); into Magma I can't even tell that there is a delay before it prints [ <1111111111111111111, 1> ] confirming that 1111111111111111111 is indeed a prime.
If I type Factorial(1111111111111111111); instead it refuses to do the calculation because 1111111111111111111 is too large.
#5 2009-06-10 19:10:59
- bobbym
- Administrator
Offline
Re: Prime Numbers!!!
Hi Avon and noobard;
Maxima might be able to evaluate that factorial but not in its entirety, of course. Just for curiosity sake here it is:
Last edited by bobbym (2009-06-10 19:11:28)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#6 2009-06-14 00:56:33
- RickIsAnIdiot
- Novice
Offline
Re: Prime Numbers!!!
For Avon
Quote:
I think bobbym's point is that, even for computers, the calculation of large factorials is not a very good way of testing if numbers are prime.
At university, if I type Factorization(1111111111111111111); into Magma I can't even tell that there is a delay before it prints [ <1111111111111111111, 1> ] confirming that 1111111111111111111 is indeed a prime.
If I type Factorial(1111111111111111111); instead it refuses to do the calculation because 1111111111111111111 is too large.
RickIsAnIdiot
Can you type Factorization(1111111111111111111); into Magma ? And it shows all the digit,s ?
#7 2009-06-15 07:27:44
- Avon
- Full Member
Offline
Re: Prime Numbers!!!
RickIsAnIdiot wrote:
Can you type Factorization(1111111111111111111); into Magma ? And it shows all the digit,s ?
If I type Factorization(1111111111111111111); into Magma the output is [ <1111111111111111111, 1> ]. You'll have to tell me if this is showing all the digits.
#8 2009-06-15 15:28:43
- bobbym
- Administrator
Offline
Re: Prime Numbers!!!
Hi Avon;
Magma is telling you that it is prime because it has the factors of itself and 1.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#9 2009-06-15 21:27:56
- Avon
- Full Member
Offline
Re: Prime Numbers!!!
It is telling me that 1111111111111111111 is prime. However, the 1 in [ <1111111111111111111, 1> ] means that the prime factor 1111111111111111111 has multiplicity 1.
For instance, Factorization(20); will output [ <2, 2>, <5, 1> ].
I'm still unsure what RickIsAnIdiot means by "shows all the digits".
#10 2009-06-15 22:01:40
- bobbym
- Administrator
Offline
Re: Prime Numbers!!!
Me too.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#11 2009-06-15 22:34:45
- ganesh
- Moderator
Offline
Re: Prime Numbers!!!
Is
divisible by 7?
Character is who you are when no one is looking.
#12 2009-06-16 01:28:52
- bobbym
- Administrator
Offline
Re: Prime Numbers!!!
Hi ganesh;
Yes, 721/7 = 103. Wilson's theorem works. That's a proof that 7 is prime. For larger primes the computation of the factorial mod n makes the idea unfeasible.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.