Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 2009-06-07 22:16:05
- noobard
- Member
- Registered: 2009-06-07
- Posts: 28
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-07 22:16:38)
Everything that has a begining has an EnD!!!
Offline
#2 2009-06-07 22:20:37
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
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-07 22:32:17)
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#3 2009-06-08 15:46:24
- noobard
- Member
- Registered: 2009-06-07
- Posts: 28
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!!!
Offline
#4 2009-06-09 09:39:44
- Avon
- Member
- Registered: 2007-06-28
- Posts: 80
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.
Offline
#5 2009-06-09 21:10:59
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
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-09 21:11:28)
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#6 2009-06-13 02:56:33
- RickIsAnIdiot
- Member
- Registered: 2009-06-13
- Posts: 5
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 ?
Offline
#7 2009-06-14 09:27:44
- Avon
- Member
- Registered: 2007-06-28
- Posts: 80
Re: Prime Numbers!!!
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.
Offline
#8 2009-06-14 17:28:43
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#9 2009-06-14 23:27:56
- Avon
- Member
- Registered: 2007-06-28
- Posts: 80
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".
Offline
#10 2009-06-15 00:01:40
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Prime Numbers!!!
Me too.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#11 2009-06-15 00:34:45
- Jai Ganesh
- Administrator
- Registered: 2005-06-28
- Posts: 48,425
Re: Prime Numbers!!!
Is
divisible by 7?
It appears to me that if one wants to make progress in mathematics, one should study the masters and not the pupils. - Niels Henrik Abel.
Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.
Offline
#12 2009-06-15 03:28:52
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Pages: 1