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: 90,799

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.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

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: 90,799

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.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

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: 90,799

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.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

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: 90,799

Re: Prime Numbers!!!

Me too.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

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

ganesh
Moderator
Registered: 2005-06-28
Posts: 15,209

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: 90,799

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.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

Board footer

Powered by FluxBB