Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#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
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

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
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

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!!!

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.

Offline

#8 2009-06-14 17:28:43

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

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
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: Prime Numbers!!!

Me too.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#11 2009-06-15 00:34:45

ganesh
Moderator
Registered: 2005-06-28
Posts: 14,528

Re: Prime Numbers!!!

Is


divisible by 7?


Character is who you are when no one is looking.

Offline

#12 2009-06-15 03:28:52

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Board footer

Powered by FluxBB