Prime Numbers

A prime number is a natural number greater than or equal to 2 that has exactly two distinct positive divisors: $ 1 $ and itself.

Mathematically, an integer $ p $ is prime if $ p \ge 2 $ and its only positive divisors are 1 and $ p $.

Prime numbers have several fundamental properties. First, there are infinitely many prime numbers. Euclid proved this more than 2000 years ago: if a list contained all the prime numbers $ p_1, p_2, \ldots, p_n $, the number $ N = p_1 \times p_2 \times \ldots \times p_n + 1 $ would not be divisible by any of the $ p_i $, because dividing by each of them would leave a remainder of 1. Therefore, $ N $ would either be prime itself or have a prime factor not included in the list, which leads to a contradiction.

Prime numbers also become less frequent as integers grow larger. If $ \pi(x) $ denotes the number of prime numbers less than or equal to $ x $, the prime number theorem gives: $ \pi(x) \sim \frac{x}{\ln(x)} $. In other words, the proportion of integers close to $ x $ that are prime is approximately $ 1/\ln(x) $.

However, the distribution of prime numbers is neither periodic nor described by a simple elementary formula. More advanced results and conjectures, particularly the Riemann Hypothesis, seek to better understand this distribution and the deviations from the approximations given by the prime number theorem.

There are several notable families of prime numbers.

— Mersenne numbers are numbers of the form $ 2^p - 1 $, where $ p $ is a prime integer in the cases generally studied when searching for prime numbers. When such a number is itself prime, it is called a Mersenne prime.

— Fermat numbers are numbers of the form $ F_n = 2^{2^n}+1 $. The only Fermat numbers known to be prime are: $ 3,\ 5,\ 17,\ 257,\ 65537 $, corresponding to $ n=0,1,2,3,4 $. To date, no known Fermat number with $ n \ge 5 $ is prime.

— Twin primes are pairs of prime numbers that differ by 2, such as $ (3,5) $, $ (5,7) $ and $ (11,13) $. The twin prime conjecture states that there are infinitely many such pairs, but this statement has not yet been proved.

— A Sophie Germain prime is a prime number $ p $ such that $ 2p+1 $ is also prime.

— A Wieferich prime is an odd prime $ p $ satisfying $ p^2 \mid 2^{p-1}-1 $. The first two known examples are $ 1093 $ and $ 3511 $, and no others are currently known in the published and catalogued research.

— Palindromic primes are prime numbers whose representation in a given base is a palindrome, such as 2, 3, 5, 7, 11, 101 or 131.

— A circular prime is a prime number for which all circular rotations of its digits are also prime in the same base.

Prime numbers play an important role in several areas of mathematics and computer science.

— In cryptography, they are notably used in RSA: two large prime numbers $ p $ and $ q $ are multiplied to form the number $ n=pq $. The security relies in particular on the difficulty for an attacker of recovering the prime factors $ p $ and $ q $ from their product $ n $.

— The Diffie-Hellman protocol uses the discrete logarithm problem in a cyclic group. A classical construction uses the multiplicative group of a finite field of prime order, which directly involves modular arithmetic and prime numbers.

— In computer science, the properties of prime numbers are also used in certain hashing algorithms, pseudo-random number generation, algorithm theory and modular arithmetic.

— In biology, periodical cicadas of the genus Magicicada are a famous example: some species emerge every 13 or 17 years. The primality of these cycles could reduce certain coincidences with other biological cycles, but several evolutionary mechanisms are being studied, and no single explanation is sufficient on its own.

The number 1 is not prime because it has only one positive divisor: itself. This convention is essential for the fundamental theorem of arithmetic, which states that every integer greater than or equal to 2 has a unique factorization, up to the order of the factors, into prime numbers.

If 1 were considered prime, this uniqueness would disappear: for example, $ 6 = 2 \times 3 $ could also be written as $ 6 = 1 \times 2 \times 3 $, $ 6 = 1 \times 1 \times 2 \times 3 $, and so on. The number 1 therefore plays a special role: it is the multiplicative identity, not a prime number.