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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**noobard****Member**- Registered: 2009-06-07
- Posts: 28

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,408

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.****No great discovery was ever made without a bold guess. **

Offline

**noobard****Member**- Registered: 2009-06-07
- Posts: 28

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

**Avon****Member**- Registered: 2007-06-28
- Posts: 80

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,408

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.****No great discovery was ever made without a bold guess. **

Offline

**RickIsAnIdiot****Member**- Registered: 2009-06-13
- Posts: 5

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

**Avon****Member**- Registered: 2007-06-28
- Posts: 80

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,408

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.****No great discovery was ever made without a bold guess. **

Offline

**Avon****Member**- Registered: 2007-06-28
- Posts: 80

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,408

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.****No great discovery was ever made without a bold guess. **

Offline

**ganesh****Moderator**- Registered: 2005-06-28
- Posts: 21,730

Is

divisible by 7?

It is no good to try to stop knowledge from going forward. Ignorance is never better than knowledge - Enrico Fermi.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,408

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.****No great discovery was ever made without a bold guess. **

Offline

Pages: **1**