The first sequence of last week is completed by the numbers 25, 35 and 49, since they are all the possible products of two one-digit prime numbers, that is, 2, 3, 5 and 7, ordered from least to greatest: 2×2, 2×3, 3×3, 2×5, 2×7, 3×5, 3×7, 5×5, 5×7 and 7×7.
The second sequence is analogous to the previous one, except that now it is the products of two factors of the two-digit primes less than 20, that is, 11, 13, 17 and 19, so the numbers that complete the sequence they are 289, 323 and 361 (17×17, 17×19 and 19×19).
As for the numbers to be broken down into two prime factors, they are factored as follows:
2117 = 29×73
4087 = 61×67
7387 = 83×89
9167 = 89×103
Whoever has tried to decompose them “barely” will have realized the difficulty of this type of factorization even in relatively simple cases.
Primes of more than one digit (which excludes the outliers 2 and 5) can only end in 1, 3, 7 or 9, so the product of any two of them will also end in one of these four numbers.
Mersenne numbers
The suitability of prime numbers for encryption tasks has to do with the difficulty -if not the impossibility- of approaching them through simple formulas or algorithms: they only succumb -when they do- to the brute force of exhaustive checks and calculations. But, given the enormous calculation capacity of modern computers, only very large cousins still resist them.
And how big are the prime numbers that we have? Huge, far above the needs of current cryptography, which handles primes of “only” a few hundred digits, when we already know of several million.
The largest known prime numbers are Mersenne numbers, that is, of the form 2ⁿ – 1, named after their discoverer, the French mathematician and philosopher Marin Mersenne (1588-1648). The largest known Mersenne prime is the one where n = 82589933, which is a number with almost 25 million digits.
Mersenne numbers are usually expressed in the form Mn, where n is the exponent of 2 in the formula 2ⁿ – 1. Until the middle of the last century, the largest known prime (discovered in 1876) was M₁₂₇, a 39-digit number. In 1951 one of the two known great primes was found that is not exactly a Mersenne number, although it is based on the previous one: 180x(M₁₂₇)² – 1, a 79-digit number. The other known non-M great prime is 391581×2²¹⁶¹⁹³ – 1, a number with 65087 digits.
The sequence of Mersenne numbers, for n = 0, 1, 2, 3, 4, 5, 6…, is: 0, 1, 3, 7, 15, 31, 63…
Obviously, they are not all cousins. As among the first seven there are only two composite numbers (15 and 63), one might suspect that many are, but in reality the vast majority of Mersenne numbers are not primes (so much so that it was believed that primes of Mersenne were finite). I invite my astute readers to investigate for what values of n the expression 2ⁿ – 1 may or may not give rise to a prime number.
Addendum: How many Mersenne primes are there under 100? And under 200?
You can follow MATTER in Facebook, Twitter and Instagramor sign up here to receive our weekly newsletter.
#great #cousins