Math Is Fun Forum

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

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.

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

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.

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.

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 ?

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.

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.

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".

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.

Jai Ganesh

Administrator

Registered: 2005-06-28

Posts: 48,404

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.

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.