- Characteristics of prime numbers
- How to know if a number is prime
- Ways to find a prime number
- Euler's formula
- The sieve of Eratosthenes
- Exercises
- - Exercise 1
- Solution
- - Exercise 2
- Solution to
- Solution b
- References
The prime numbers, also called prime absolute, are those natural numbers which are only divisible by themselves and 1. This category numbers like 2, 3, 5, 7, 11, 13, 17, 19, 23 and many plus.
Instead, a composite number is divisible by itself, by 1, and at least one other number. We have, for example, 12, which is divisible by 1, 2, 4, 6 and 12. By convention, 1 is not included in the list of prime numbers or in the list of compounds.
Figure 1. Some prime numbers. Source: Wikimedia Commons.
Knowledge of prime numbers dates back to ancient times; the ancient Egyptians already used them and they were surely known long before.
These numbers are very important, since any natural number can be represented by the product of prime numbers, this representation being unique, except in the order of the factors.
This fact is fully established in a theorem called the fundamental theorem of arithmetic, which states that numbers that are not prime are necessarily made up of products of numbers that are prime.
Characteristics of prime numbers
Here are the main characteristics of prime numbers:
-They are infinite, since no matter how large a prime number is, you can always find a greater one.
-If a prime number p does not exactly divide another number a, then it is said that p and a are prime to each other. When this happens, the only common divisor that both have is 1.
It is not necessary for a to be an absolute prime. For example, 5 is prime, and although 12 is not, both numbers are prime to each other, since both have 1 as a common divisor.
-When a prime number p divides a power of the number n, it also divides n. Let's consider 100, which is a power of 10, specifically 10 2. It happens that 2 divides both 100 and 10.
-All prime numbers are odd except for 2, therefore its last digit is 1, 3, 7 or 9. 5 is not included, because although it is odd and prime, it is never the final figure of another prime number. In fact all the numbers that end in 5 are multiples of this and therefore they are not prime.
-If p is a prime and divisor of the product of two numbers ab, then p divides one of them. For example, the prime number 3 divides the product 9 x 11 = 99, since 3 is a divisor of 9.
How to know if a number is prime
Primality is the name given to the quality of being prime. Well, the French mathematician Pierre de Fermat (1601-1665) found a way to verify the primality of a number, in the so-called small theorem of Fermat, which says:
"Given a prime natural number p and any natural number a greater than 0, it is true that a p - a is a multiple of p, as long as p is prime".
We can corroborate this using small numbers, for example suppose that p = 4, which we already know is not prime and already = 6:
6 4 - 6 = 1296 - 6 = 1290
The number 1290 is not exactly divisible by 4, therefore 4 is not a prime number.
Let's do the test now with p = 5, which is prime and ya = 6:
6 5 - 6 = 7766 - 6 = 7760
7760 is divisible by 5, since any number that ends in 0 or 5 is. In fact 7760/5 = 1554. Since Fermat's little theorem holds, we can ensure that 5 is a prime number.
The proof through the theorem is effective and direct with small numbers, in which the operation is easy to perform, but what to do if we are asked to find out the primality of a large number?
In that case, the number is successively divided among all the smaller prime numbers, until an exact division is found or the quotient is less than the divisor.
If any division is exact, it means that the number is composite and if the quotient is less than the divisor, it means that the number is prime. We will put it into practice in solved exercise 2.
Ways to find a prime number
There are infinitely many prime numbers and there is no single formula to determine them. However, looking at some prime numbers like these:
3, 7, 31, 127…
It is observed that they are of the form 2 n - 1, with n = 2, 3, 5, 7, 9… We make sure of this:
2 2 - 1 = 4 - 1 = 3; 2 3 - 1 = 8 - 1 = 7; 2 5 - 1 = 32 - 1 = 31; 2 7 - 1 = 128 - 1 = 127
But we cannot ensure that in general 2 n - 1 is prime, because there are some values of n for which it does not work, for example 4:
2 4 - 1 = 16 - 1 = 15
And the number 15 is not prime, since it ends in 5. However, one of the largest known primes, found by computer calculations, is of the form 2 n - 1 with:
n = 57,885,161
Mersenne's formula assures us that 2 p - 1 is always prime, as long as p is prime as well. For example, 31 is prime, so it is certain that 2 31 - 1 is also prime:
2 31 - 1 = 2,147,483,647
However, the formula allows you to determine only some prime numbers, not all.
Euler's formula
The following polynomial allows finding prime numbers provided that n is between 0 and 39:
P (n) = n 2 + n + 41
Later in the solved exercises section there is an example of its use.
The sieve of Eratosthenes
Eratosthenes was a physicist and mathematician from Ancient Greece who lived in the 3rd century BC. He devised a graphic method of finding the prime numbers that we can put into practice with small numbers, it is called the Eratosthenes sieve (a sieve is like a sieve).
-The numbers are placed in a table like the one shown in the animation.
-The even numbers are then crossed out, except for 2 that we know is prime. All the others are multiples of this and therefore are not prime.
-The multiples of 3, 5, 7 and 11 are also marked, excluding all of them because we know they are prime.
-The multiples of 4, 6, 8, 9 and 10 are already marked, because they are compound and therefore multiples of some of the indicated primes.
-Finally, the numbers that remain unmarked are prime.
Figure 2. Animation of the Eratosthenes sieve. Source: Wikimedia Commons.
Exercises
- Exercise 1
Using the Euler polynomial for prime numbers, find 3 numbers greater than 100.
Solution
This is the polynomial that Euler proposed to find prime numbers, which works for values of n between 0 and 39.
P (n) = n 2 + n + 41
By trial and error we select a value of n, for example n = 8:
P (8) = 8 2 + 8 + 41 = 113
Since n = 8 produces a prime number greater than 100, then we evaluate the polynomial for n = 9 and n = 10:
P (9) = 9 2 + 9 + 41 = 131
P (10) = 10 2 + 10 + 41 = 151
- Exercise 2
Find out if the following numbers are prime:
a) 13
b) 191
Solution to
The 13 is small enough to use Fermat's little theorem and the help of the calculator.
We use a = 2 so that the numbers are not too large, although a = 3, 4 or 5 can also be used:
2 13 - 2 = 8190
8190 is divisible by 2, since it is even, therefore 13 is prime. The reader can corroborate this by doing the same test with a = 3.
Solution b
191 is too big to prove with the theorem and a common calculator, but we can find the division between each prime number. We omit dividing by 2 because 191 is not even and the division will not be exact or the quotient less than 2.
We try to divide by 3:
191/3 = 63,666…
And it does not give exact, nor is the quotient less than the divisor (63,666… is greater than 3)
We continue thus trying to divide 191 between the primes 5, 7, 11, 13 and the exact division is not reached, nor the quotient less than the divisor. Until it is divided by 17:
191/17 = 11, 2352…
Since it is not exact and 11.2352… is less than 17, the number 191 is a prime.
References
- Baldor, A. 1986. Arithmetic. Editions and Distributions Codex.
- Prieto, C. The prime numbers. Recovered from: paginas.matem.unam.mx.
- Properties of prime numbers. Recovered from: mae.ufl.edu.
- Smartick. Prime numbers: how to find them with the Eratosthenes sieve. Recovered from: smartick.es.
- Wikipedia. Prime number. Recovered from: es.wikipedia.org.