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

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

Online

### 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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

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

Online

### 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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

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

Online

### 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 have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

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

Online

### Re: Prime Numbers!!!

Me too.

In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

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

Online

### 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 have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.