Euclid’s theorem tells us in principle that there are arbitrarily large primes out there, but does not give a recipe to find them. Indeed, the prime numbers seem to be so “randomly” distributed that it is often difficult to establish what patterns exist within them. The Greeks were certainly aware of the importance of prime numbers, and several key results and conjectures about primes come to us from the ancient Greeks. Much of this is captured in Euclid's Elements.
Very little is known about the Greek mathematician Euclid. The date and place of his birth, and the date and circumstances of his death are unknown; we have only a rough idea based on contemporary references. There were no likenesses or descriptions made of him during his lifetime. The few historical references to Euclid (as opposed to his books) were made centuries after his death. In spite of the scarcity of the historical record, Euclid's Elements are without question the most influential works in mathematics, serving as one of the main texts for the teaching of mathematics from its creation until the early 20th century. Euclid's rigorous approach to mathematical proof remains central to modern mathematics; in many ways Euclid set the standard for a proof. While many, possibly all, of the mathematical results in the Elements originated with other mathematicians, Euclid's impressive accomplishment was to capture the breadth of the mathematics of his day and present it all in a single, logically coherent framework, a feat that was never before accomplished, and never repeated.
After the Greeks, there were relatively few results on prime numbers until the 1600's, when the French monk Marin Mersenne studied primes of the form 2p-1 , with p prime (called Mersenne primes today). Mersenne was a French monk who, in addition to dabbling with prime numbers made great strides in music theory, earning the nickname the “father of acoustics.” In 1640, Pierre de Fermat, perhaps the greatest amateur mathematician of all time, conjectured that ap-a is divisible by p, where a is any integer and p is prime; this is Fermat's Little Theorem, which, like so many of Fermat's theorems, he himself did not prove. Two other luminaries, Leibniz and Euler, tackled this problem much later. Fermat also conjectured that all numbers of the form 22n+1 is prime; he verified this to n=4 , but was proven wrong; the next Fermat number is composite, and no others are known to be prime.
In the 1700's, number theory had fallen out of fashion, prior to tackling Fermat's little theorem and conjecture, Leonard Euler tackled the zeta function, which more than 100 years later was again studied by (and eventually named after) Bernhard Riemann:
 |
| Euler's Zeta Function |
For s>1, this series is finite. Euler showed that this infinite series has a deep connection to the prime numbers, and the zeta function equals the infinite product:
 |
| The Zeta Function and Prime Numbers |
Since Euclid's time, it was known that even perfect numbers, numbers that are the sum of their prime factors, have the form 2p-1(2p-1). In 1747 Euler showed that an odd perfect number would have the form:
 |
| Odd Perfect Numbers |
While we know what they would have to look like, we don't know if there are any. It is believed no odd perfect numbers exist, but there is no proof. Thus far, it has been shown that no odd perfect numbers exist less than 10300.
The primes behave so randomly that we have no useful exact formula for the nth prime. But we do have an important approximate formula in the Prime number theorem. One of the most important results about prime numbers, it was a long time coming. In the 19th century Legendre and Gauss, conjectured that as x tends to infinity, the number of primes is asymptotic to x/ln(x). In 1859, Riemann described his hypothesis about zeta function, which has become one of the great unsolved problems in mathematics. In his paper, Riemann outlined an approach in this paper that would lead to proof of Legendre and Gauss' conjecture. It was two mathematicians, Jacques Salomon Hadamard and Charles-Jean Étienne Gustave Nicolas de la Vallée Poussin who independently proved Legendre and Gauss' conjecture in 1896.
The prime number theorem shows that the primes have some large-scale structure, even though they can behave quite randomly at smaller scales. The proof of the theorem is a remarkable work of multidisciplinary mathematics, using arithmetic functions (Von Mangoldt function), distribution theory (Mellin transforms), and complex analysis.
 |
| Von Mangoldt Function |
A prime number’s only divisors are 1 and itself. The fundamental theorem of arithmetic says that every number is either prime or has a unique factorization of prime divisors. This is a powerful result, and it tells us that prime numbers are the building blocks of the integers. However, finding the prime factors of a large integer is hard. Many asymmetric cryptography schemes rely on this difficulty, and make use of it by essentially multiplying extremely large prime numbers together. Knowing only the product and not the primes, factoring is extremely difficult, especially when the numbers are large. With large enough numbers finding the prime factorization is, practically speaking, impossible.
The fundamental nature of prime numbers has been known since the time of the ancient Greeks, but their role in cryptography is relatively recent. What is fascinating is that something decidedly modern such as e-commerce, which requires secure communications for online transactions, makes use of number theoretic results that have been around for more than thousands of years. Despite having studied them since the dawn of mathematics, prime numbers still hold many secrets.
No comments:
Post a Comment