Catálogo de publicaciones - libros

The theory of numbers is concerned with the properties of the integers , that is, the class of whole numbers and zero, 0,±1,±2 .... The positive integers, 1, 2, 3 ..., are called the natural numbers . The basic additive structure of the integers is relatively simple. Mathematically it is just an infinite cyclic group (see Chapter 2). Therefore the true interest lies in the multiplicative structure and the interplay between the additive and multiplicative structures. Given the simplicity of the additive structure, one of the enduring fascinations of the theory of numbers is that there are so many easily stated and easily understood problems and results whose proofs are either unknown or incredibly difficult. Perhaps the most famous of these was Fermat’s big theorem , which was stated about 1650 and only recently proved by A. Wiles. This result said that the equation a ^n+ b ^n = c ^n has no nontrivial ( abc ≠ 0) integral solutions if n > 2. Wiles’s proof ultimately involved the very deep theory of elliptic curves. Another result in this category is the Goldbach conjecture , first given about 1740 and still open. This states that any even integer greater than 2 is the sum of two primes. Another of the fascinations of number theory is that many results seem almost magical. The prime number theorem , which describes the asymptotic distribution of the prime numbers has often been touted as the most surprising result in mathematics.

The theory of numbers is concerned with the properties of the integers , that is, the class of whole numbers and zero, 0, ±1,±2 .... We will denote the class of integers by ℤ. The positive integers, 1, 2, 3..., are called the natural numbers , which we will denote by ℕ. We will assume that the reader is familiar with the basic arithmetic properties of ℤ, and in this section we will look at the abstract algebraic properties of the integers and what makes ℤ unique as an algebraic structure.

The two most striking characteristics of the sequence of primes is that there are many of them but that their density is rather slim. From Euclid’s theorem (Theorem 2.3.1) there are infinitely many primes; in fact, there are infinitely many in any nontrivial arithmetic sequence of integers. This latter fact was proved by Dirichlet and is known as Dirichlet’s theorem . As mentioned before, if x is a natural number and π ( x ) represents the number of primes less than or equal to x , then asymptotically this function behaves like the function x /ln x . This result is known as the prime number theorem . Besides being a startling result, the proof of the prime number theorem, done independently by Hadamard and de la Vallée Poussin, became the genesis for analytic number theory. In this chapter we will discuss various aspects of the infinitude of primes. The prime number theorem will be introduced in the next chapter.

As we have seen, and proved in many different ways, there are infinitely many primes. In fact, as Dirichlet’s theorem shows, there are infinitely many primes in any arithmetic progression an + b with ( a, b ) = 1. However, an examination of the list of positive integers shows that the primes become scarcer as the integers increase. This statement was quantified in Theorem 2.3.2, where we proved that there are arbitrarily large spaces or gaps within the sequence of primes. As a result of these observations the question arises concerning the distribution or density of the primes. The interest centers here on the prime number function π ( x ) defined for positive integers x by π ( x ) = number of primes ≤ x .

In the previous two chapters we have seen that there are infinitely many primes and showed that as we move through larger and larger integers the density of primes thins out. In particular, we proved that $$ \frac{{\pi (x)}} {x} \sim \frac{1} {{1n x}}as x \to \infty , $$ where π ( x ) represents the number of primes less than the positive real number x . This result, the prime number theorem, could be interpreted as saying that the probability of randomly choosing a prime number less than or equal to a positive real number x is approximately 1/ln x as x gets large. In this chapter we consider the question of determining whether a particular given positive integer n is prime or not prime. The methods concerning this problem are called primality testing and consist of algorithms to determine whether an inputted positive integer is prime. Primality testing has become extremely important and has been of great interest in recent years due to its close ties to cryptography and especially public key cryptography . Cryptography is the science of encoding and decoding secret messages. Many of the most powerful and secure encoding methods depend on number theory, especially on the computational difficulty of factoring large integers. It turns out, somewhat surprisingly, that relative to ease of computation, determining whether a number is prime is easier than actually factoring it.

The final major area within the theory of numbers is algebraic number theory . In this last chapter we present an overview of the major ideas in this discipline. In line with the theme of these notes we will concentrate on primes and prime decompositions.