I am Michael Peres and welcome to my podcast.

During an interview with Google, writing an algorithm to identify prime numbers is a possibility. Prime number applications go way beyond an interview, like...

- Discovering an evolutionary secret behind Cicada's breeding patterns
- One of mathematics most elegant proofs
- Brilliant methods devised to identify prime numbers,
- The incredibly mysterious relationship between prime numbers and the Riemann hypothesis
- Understanding Diffie-hellman cryptography
- Quantum Applications for detecting prime numbers, and breaking modern day cryptography
- Intelligent methods for sending information across the cosmos

... and much more.

In this 3 part series, I sit down with Landon Noll, 8 time world record holder for the longest prime number.

Discover why prime numbers matter and how it has and will continue to revolutionize our world!

*Keep in touch with me on social media: *

Instagram: @mike.514

Twitter: @mikeyperes

Facebook: @themichaelperes

Linkedin: Michael Peres

#### Curt Landon Noll

Euclid’s Proof Euclid first proved that there exists an infinite number of primes. (300 BC) Assume there are finitely many primes. Let S be the set of all n primes, p 1 p 2 p 3 …p n Let q = p 1 p 2 p 3 …p n + 1. There must exist a prime factorization for q. We claim that this factorization does not contain an element of S. This would imply that q uses a prime outside the set S, thus there are in fact more than n primes. Assume that p i, 1 <= i <= n, is in the prime factorization of q. Then it must divide p 1 p 2 p 3 …p n + 1. Specifically p i | 1. But since primes are greater than 1, this is our contradiction.

#### Palindromic Primes

A **palindromic prime** (sometimes called a **palprime**) is a prime number that is also a palindromic number. Palindromicity depends on the base of the numbering system and its writing conventions, while primality is independent of such concerns. The first few decimalpalindromic primes are

- 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, … (sequence A002385 in the OEIS)

Except for 11, all palindromic primes have an odd number of digits, because the divisibility test for 11 tells us that every palindromic number with an even number of digits is a multiple of 11.

#### Mersenne Primes

In mathematics, a **Mersenne prime** is a prime number that is one less than a power of two. That is, it is a prime number of the form *M _{n}* = 2

^{n}− 1 for some integer

*n*. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century.

The exponents *n* which give Mersenne primes are 2, 3, 5, 7, 13, 17, 19, 31, … (sequence A000043 in the OEIS) and the resulting Mersenne primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, … (sequence A000668 in the OEIS).

If *n* is a composite number then so is 2^{n} − 1. (2^{ab} − 1 is divisible by both 2^{a} − 1 and 2^{b} − 1.) This definition is therefore equivalent to a definition as a prime number of the form *M _{p}* = 2

^{p}− 1 for some prime

*p*.

#### Millenium Problems

Experiment and computer simulations suggest the existence of a “mass gap” in the solution to the quantum versions of the Yang-Mills equations. But no proof of this property is known.

The prime number theorem determines the average distribution of the primes. The Riemann hypothesis tells us about the deviation from the average. Formulated in Riemann’s 1859 paper, it asserts that all the ‘non-obvious’ zeros of the zeta function are complex numbers with real part 1/2.

If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question. Typical of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit, how can one do this without visiting a city twice? If you give me a solution, I can easily check that it is correct. But I cannot so easily find a solution.

This is the equation which governs the flow of fluids such as water and air. However, there is no proof for the most basic questions one can ask: do solutions exist, and are they unique? Why ask for a proof? Because a proof gives not only certitude, but also understanding.

The answer to this conjecture determines how much of the topology of the solution set of a system of algebraic equations can be defined in terms of further algebraic equations. The Hodge conjecture is known in certain special cases, e.g., when the solution set has dimension less than four. But in dimension four it is unknown.

In 1904 the French mathematician Henri Poincaré asked if the three dimensional sphere is characterized as the unique simply connected three manifold. This question, the Poincaré conjecture, was a special case of Thurston’s geometrization conjecture. Perelman’s proof tells us that every three manifold is built from a set of standard pieces, each with one of eight well-understood geometries.

Supported by much experimental evidence, this conjecture relates the number of points on an elliptic curve mod p to the rank of the group of rational points. Elliptic curves, defined by cubic equations in two variables, are fundamental mathematical objects that arise in many areas: Wiles’ proof of the Fermat Conjecture, factorization of numbers into primes, and cryptography, to name three.

#### The Lucas–Lehmer test

The Lucas–Lehmer test works as follows. Let *M*_{p} = 2^{p} − 1 be the Mersenne number to test with *p* an odd prime. The primality of *p* can be efficiently checked with a simple algorithm like trial division since *p* is exponentially smaller than *M*_{p}.

In pseudocode, the test might be written as

// Determine ifM_{p}= 2^{p}− 1 is prime forp> 2Lucas–Lehmer(p)vars = 4varM = 2^{p}− 1repeatp − 2 times: s = ((s × s) − 2) mod Mifs == 0returnPRIMEelsereturnCOMPOSITE

Performing the `mod M`

at each iteration ensures that all intermediate results are at most *p* bits (otherwise the number of bits would double each iteration). The same strategy is used in modular exponentiation.

#### The Lucas test

In computational number theory, the **Lucas test** is a primality test for a natural number *n*; it requires that the prime factors of *n* − 1 be already known.^{[1]}^{[2]} It is the basis of the Pratt certificate that gives a concise verification that *n* is prime.