It’s **not** an **easy task** determine if **a number is prime** or not. Knowing if a number is prime always strongly attracted mathematicians and amateurs who have obtained some **partial results**, but ** no one has yet found an exact mathematical formula with acceptable time and algorithmic structure that resolves this question for all or undefined set of prime numbers.**

A number is prime if it’s not multiple or divisible by another number other than itself and unity.

If you want to know if a number is prime, we can test to **split** by 1,2,3,4 …. up the number, if **none of them** is divisor of the number then the number is **prime**.

This idea is shown in this drawing is known how “the conway machine” (John Horton), English mathematician at the University of Cambridge, shown in Fig pedaling to operate the machine. The group of inspectors check the number that passes the string is divisible by its assigned divisor and if in afirmative case refuses it into the trash.

The problem is that we have to try as many numbers as the large of the number, so that we can **improve the strategy**.

We know that if a number is divisible or multiple of another, then any product of that number is too.

Therefore if we divide by a composite number (which is the product of at least one prime), is also divisible by this prime, so:

To know if a number is prime just look if it is divisible only by some prime to number.

But … Do you need to test all the primes up to the number?

Not too, if We look when where are testing in order the primes, we are discarding by order, so the **next prime** to test multiplied by the previous primes **cannot get the number** as a result, so we will obtain the number **at least** with the next prime by multyplying by**itself**, this means that **the search ends with the prime wich has the nearest square to the number without exceeding it**, in other words:

To know if a number is prime, simply test if the number is divisible by primes up to its square root.

**PRACTICAL CASE**

**Is 149 prime?**

The **square root of 149** is 12,2… so it is only necessary **test the prime numbers up to 12,2..**

We test **2,3,5,7,11**

**149 : 2** = 74,5.. (not divisible by 2)**149 : 3** = 49,6.. (not divisible by 3)**149 : 5** = 29,8.. (not divisible by 5)**149 : 7** = 21,2.. (not divisible by 7)**149 : 11** = 13,5.. (not divisible by 11)

149 can not be divided by these prime ?numbers then **149 is a prime number**.

Is there a formula to tell me exactly if a number is prime?

Yes, the **Wilson theorem:**

A number n is prime if and only if (n-1)! + 1 is a multiple of n

Example:

Is 7 a prime number?

7 is prime if **(7-1)! + 1** is **multiple of 7**

(7-1)! + 1 = 6! + 1 = (6x5x4x3x2x1)+1 = **5040**

Is 5040 multiple of 7?

**5040 : 7** = **720 **(exact division)

yes 5040 is multiple of 7 then **7 is a prime number**.

The problem is when we have **big numbers** it’s more difficult to calculate because the factorial becomes very large and in last case **is not a practical method**.

There are more complex**tests** to know the primality of a number but are difficult to push on practice if we are not on computer programming:

**PROBABILISTIC**

- Solovay-Strassen Test (SS)

- Miller-Rabin Test

- Elliptic Curve Primality Proving

**DETERMINISTIC**

- Fermat Test(only Mersenne primes)

- Lucas-Lehmer Test(only Mersenne primes)

- Pocklington Prove

- LKL Prove(only Mersenne primes)

In 2002 appeared a deterministic test which ensures a polynomial time if a number is prime or not. It is known as the **AKS test** and it’s the most important discovery recently about prime numbers.