Prime numbers are a subset of natural numbers that are used daily (virtually) to protect our sensitive data. In fact, the cryptography used in banking security is mainly based on these numbers. So far there are open speculations about these numbers. You can make a lot of money if you solve one.

### Definition of prime numbers

A** prime number** $p$ is a natural number greater than $1$ which is divisible only by itself and by $ 1 $, equivalently if it cannot be formed by multiplying two smaller natural numbers. A **composite** number $n$ is a positive integer $ n> 1 $ which is not a prime number.

Also, we recall that any prime number is an odd number; of the forme $2k+1$ with $k\ge 1$. This property makes them important for security purposes. However, not all odd numbers are prime, for example, $9$ is not odd. This is because it is the product of two natural numbers $9=3\times 3$.

Let us show how one can determine if a number is prime or composite. For instance, consider the big number of $1000001$. We show that it is not a prime number (it is an opposite number). In fact, recall that for a number $a$, we have $a^3+1=(a+1)(a^2-a+1)$. By applying this formula, we get

\begin{align*} 1000\,001&=1000\,000+1= 10^6+1=(10^2)^3+1\cr &= (10^2+1)((10^2)^2-10^2+1)\cr &= 101 \times 9901. \end{align*} Hence $1000\,001$ is not prime, then it is a composite number.

### Prime numbers are used on the decomposition of numbers

Any natural number $a\ge 0$ can have the following decomposition

\begin{align*} a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_N^{\alpha_N}, \end{align*}where $p_1,p_2,\cdots,p_N$ are prime numbers such that $p_i\neq p_j$ for $i\neq j,$ and $\alpha_1,\alpha_2,\cdots,\alpha_N$ are non nul natural numbers. We notice that this decomposition is unique.

This property is called the **prime factorization** of numbers. Let us give a mathematical application of this property and then determine the natural number $n$ satisfying $4^n+3\times 2^n=88$. On one hand, decompose $88=2^3\times 11$. On the other hand, as $4^n=(2^2)^n=2^{2n}$, then $4^n+3\times 2^n=2^{2n}+3\times 2^n=2^n(2^n+3)$. This shows that

\begin{align*}2^n(2^n+3)=2^3\times 11. \end{align*}We first remark that $n\neq 0$ because $2^0(2^0+3)\neq 88$. Hence $2^n$ is an even number, and then $2^n+3$ is an odd number, so that the decomposion of $2^n+3$ exclude $2$ and the powers of $2$. Now by using the uniqness of the prime factorization we deduce that $n=3$.

We also mention that prime factorization is very helpful if the computation of the greatest common divisor and least common multiple.

According to the properties cited above, prime numbers constitute the most important category of numbers.

What is the greatest prime number? We do not know, mathematicians are still working on this problem, and it is a difficult problem even if today we are equipped with powerful computers.

### The algorithm producing the security codes

You can use this class of numbers for encrypted messages and the PIN code for account banking. As already mentioned above, any natural number greater than $ 2$ is decomposed into a factor of prime numbers. This is why all the codes are mainly based on prime numbers. An algorithm delivering codes using prime numbers is called **RSA**. The latter is a word made up of the names of the authors of the algorithm: Ron **R**ivest, Adi **S**hamir, and Leonard **A**dleman.