## Open Questions: Number Theory

[Home] [Up] [Glossary] [Topic Index] [Site Map]

### Introduction

If you've already had a look at the rest of this page, you will probably have noticed something interesting: Some of the open questions in the field of number theory are very easy to state and understand. But others are difficult to state, and even more difficult to understand. And this doesn't even consider how difficult the problems are to solve (excedingly difficult in all cases).

Number theory has been studied since the time of the Greeks. (It was especially interesting to Pythagoras and his followers. Euclid proved there are infinitely many primes and invented the "Euclidean algorithm" for finding the greatest common divisor of a pair of numbers.) For most of that time, the unsolved problems were easy to state. This has contributed greatly to the popularity of number theory.

It is only relatively recently that some of the open questions in number theory have become difficult for non-mathematicians to even understand -- perhaps 150 years, since the time of Riemann, when analytic methods came into use for studying number theoretic problems. A similar process has occurred in physics, over about the same period of time.

This may well be characteristic of scientific fields which have "matured" in some sense. In biology, for instance, most of the open questions are still not difficult to state clearly. Although we wouldn't go so far as to say biology isn't a "mature" science, one sure sign that it has made substantial progress may appear when many of its open questions become more difficult for non-specialists to understand. (And of course, in a field like psychology, which definitely isn't mature, the questions are quite simple to state, though it isn't clear that they are posed in a way that is amenable to scientific analysis, or even especially precise.)

It would be a mistake to view this tendency in the development of a science as a negative thing -- that the "interesting" questions have all been resolved, and that the remaining problems are of interest only to specialists. Instead, what it usually indicates is that the science has developed powerful technical machinery which is capable of, and probably necessary for, making progress towards solving the more easily understood open questions in the field.

In any case, you should not feel dismayed if/when you find that some of the significant open questions in number theory are decidedly not something that could be explained in an elementary way. This is a sign of progress!

### Prime numbers

One learns about prime numbers very early in the study of mathematics -- usually in elementary school. The Greeks were very familiar with them. Euclid, for instance, proved that there are infinitely many primes. A prime number is defined as a (positive) integer that is divisible only by 1 and itself. 1 is, by convention, not considered a prime, because it would spoil what is known as the "fundamental theorem of arithmetic", which is that every integer can be expressed in a unique way as a product of primes (except for order which, of course, is irrelevant).

Euclid's Elements, in fact, contains results about primes and the divisibility properties of numbers that are as important for the foundations of arithmetic as are its corresponding results in the foundations of geometry. Three books of the Elements deal with the theory of numbers. Among other things, it gave us the "Euclidean algorithm" for computing the greatest common divisor of two numbers. It also proved the fundamental theorem of artithmetic. (If there is any (positive) integer that does not have a unique factorization, there is a smallest one. Let N be that integer. Suppose a prime p divides N. Then N can be written as paN1 where a ≥ 1 and p doesn't divide N1. Suppose there is a different factorization N = pbN2, where b ≥ 1 and p doesn't divide N2. We can assume a ≥ b (switch them if not). Then pa-bN1 = N2. We must have a = b, otherwise p would divide N2. So N1 = N2. But this number has a unique factorization, because it is smaller than N. Hence N itself must have a unique factorization. This contradicts the assumption it was the smallest number without unique factorization, and this contradiction proves no such number exists.)

Unique factorization is a very important property of the integers. For one thing, it makes relatively easy the deduction of many of their properties, because such properties often can be proven by expressing the numbers involved as a (unique) product of primes -- the primes are elementary building blocks of all (whole and fractional) numbers. There are natural generalizations of the integers, called "algebraic integers" which are studied in the theory of "algebraic numbers" -- numbers which are solutions of polynomial equations. Uniqueness of factorization is usually not the case with these more general algebraic numbers, and it makes their theory much more challenging. (This fact was not realized for quite some time after mathematicians started to study algebraic numbers, leading to more than a few fallacious proofs.)

But that's getting ahead of the story, because even the study of "ordinary" primes among the integers led to the large and fascinating theory that is ("elementary") number theory. We can't even begin to summarize that theory here, except to say that a great deal of it concentrates on two sorts of questions:

1. Questions about divisibility properties of integers, which depends essentially on factorization into primes, and questions about how primes are distributed among non-prime ("composite") numbers.
2. Questions about solving equations (usually polynomial equations) with numbers that are either integers or ratios of integers ("rational numbers"), i. e. fractions. Such equations are called "Diophantine equations".
Most of the questions of the first type have been solved -- some in antiquity, others only recently. But a few questions about prime numbers still remain, and they have defied efforts to solve them over several hundred years. We'll consider some of the best known of them in this section. As for questions of the second type, many of them were solved by ad hoc methods in antiquity, but the beginnings of a general theory have emerged only in the last century. Perhaps the best known question about Diophantine equations -- Fermat's Last Theorem -- was answered only within the last decade and only by the application of an awesome arsenal of modern mathematical techniques. Answers to many additional questions, as well as a respectable general theory still belong to the future. We'll go into that a little later.

#### Goldbach's conjecture

Goldbach's conjecture says that every integer larger than 2 can be expressed (perhaps in many ways) as a sum of two primes.

Other topics:

• Distribution of primes
• Primes in arithmetic progressions
• Twin primes
• Gaps between primes
• Mersenne numbers
• Fermat numbers

### Diophantine equations

There are two main topics that everyone who has any knowledge of number theory is aware of: prime numbers and Diophantine equations. Prime numbers are learned about early in the study of elementary arithmetic, but there are deep and fascinating questions connected with their distribution, and an elegant existing theory dealing with such questions, so let's defer that. Diophantine equations, on the other hand, provoke a multitude of special questions, but relatively little organized theory has developed to deal with them.

Diophantine equations get their name from Diophantos of Alexandria. Diophantos flourished in the 3rd century CE and wrote a highly regarded treatise he called the Arithmetica. Much of this dealt with solving algebraic equations in several unknowns, with the added restriction that solutions had to be rational or integral. This was especially important to the Greeks because of the discovery by Pythagoreans centuries earlier that many solutions of algebraic equations, even something as simple as the square root of 2, were not rational numbers. Then, as now, the term "irrational" had very negative connotations (though no longer in modern times as regards numbers).

In any case, early mathematicians were very interested in finding solutions of simple algebraic equations that are rational or integral numbers. This is often a very natural condition to impose on a particular problem. The equation, for example, may apply to things which ordinarily occur in whole number amounts, such as living animals.

A Diophantine equation, then, is an algebraic equation for which rational or integral solutions are sought. (Systems of such equations are also considered.) An algebraic equation is one that involves only polynomial expressions in one or more variables. What makes the equation "Diophantine" is that the coefficients of the polynomials should be rational numbers (or often, integers), and further that only rational (or integer) solutions are sought. Since these are the only conditions, not much in the way of a general theory has developed, though a lot is known about many more specialized cases.

The closest thing to a general theory is to be found in algebraic geometry, which deals with the geometric properties of solution sets of algebraic equations, usually over an "algebraically closed" field of numbers, such as the complex numbers. Algebraic geometry, indeed, turns out to be very helpful in solving problems with Diophantine equations, and a great deal of very deep and beautiful theory has been developed. However, a general theory that can deal with finding integral or rational solutions of arbitrary algebraic equations, or even with determining whether such solutions exist, is still a long way off.

In 1970 Yuri Matiyasevich gave a negative solution of the so-called 10th Hilbert problem by showing that there is no general decision procedure to determine whether solutions of an arbitrary Diophantine equation exist. Subsequently Matiyasevich showed that equations with as few as 9 variables lack a decision procedure. It is possible there may be equations with even fewer variables that lack such a procedure. However, the methods used in Wiles' proof of Fermat's Last Theorem indicate that all equations in 3 variables should be decidable. It is at present an open question what the least number of variables of an undecidable equation might be.

Nevertheless, we do have some very illuminating theory. For instance, there is a very celebrated conjecture stated by Louis Mordell in 1922 which says, roughly, that if P(x,y) is a polynomial with rational coefficients, then the equation P(x,y)=0 has only finitely many rational solutions (provided P(x,y) also has a "genus" greater than 1). This was an open problem until a proof was finally given by Gerd Faltings in 1983. The result can be interpreted geometrically as saying that a surface which contains all complex number solutions of the equation has only finitely many points on it with rational coordinates.

The most famous Diophantine equation of all, of course, is Fermat's equation: xn + yn = zn. Andrew Wiles finally proved in 1995 that, if n is 3 or more, this equation has no nonzero integral solutions -- even though Fermat had conjectured as much more than 350 years earlier. The final solution turned out to require extremely sophisticated tools from algebraic number theory, algebraic geometry (such as the theory of elliptic curves), and much more besides from a great deal of the remainder of modern mathematics.

Note that Fermat's problem is really about solutions of an infinite set of equations (one for each value of n). Technically speaking, if n were regarded as one of the variables in the equation, it would no longer be algebraic. Many other famous Diophantine problems have this feature, where one of the "variables" occurs as an exponent.

#### Elementary examples

Diophantine equations need not be limited to equations in only one variable (such as x2-2 = 0). It's frequently more interesting to consider equations with several variables, such as the Fermat equation. Just about the simplest equation with two variables and degree higher than 1 is x2-y2 = 0. (The degree of a single term is the sum of exponents of all variables occuring in the term. The degree of the equation is the largest of the degrees of its terms.) But this equation isn't very interesting, because it can be written as a product of polynomials of first degree: (x+y)(x-y) = 0. When the polynomial in such an equation is a product of factors of degree one having suitable coefficients, the solutions consist of the solutions of any of the factors, and those are trivial.

The next simplest second degree equation in two variables is x2+y2 = 1. (The equation x2+y2 = 0 has only the trivial solution x=y=0 when excluding complex numbers.) You probably recognize that as the equation of a circle of radius 1. Any point on the circle has coordinates satisfying the equation, and vice versa. The polynomial x2+y2-1 does not factor into first degree polynomials with real (i. e., not imaginary) coefficients. Nevertheless, it has solutions for x and y that are rational numbers, and even integers, such as (x,y) = (±1,0) or (0,±1). Clearly these are the only integer solutions, because we must have -1≤x≤1, so x has to be -1, 0, or 1, and so does y.

It was Diophantos himself who discovered all the rational solutions of this equation. He found what is called a parametric solution, obtained via elementary algebra. Namely, if t is any rational number (or even complex number, for that matter), then

x=(1-t2)/(1+t2), y=2t/(1+t2)
gives a point on the circle, and the coordinates are obviously rational if t is. Conversely, suppose (X,Y) is any point on the circle. It also lies on a straight line passing through the point (-1,0), having some slope t. The equation of this line is Y=t(X+1). The line intersects the circle at a unique point besides (-1,0), and if you do the algebra, you see that point must be given by X=(1-t2) and Y=2t/(1+t2). Since t = Y/(X+1), t must be rational if X and Y are. This shows that every rational point (except (-1, 0)) on the circle has the parametric form given, for some rational t. I. e., there's a very tidy 1:1 correspondence between rational numbers and points on the circle with rational coordinates.

This is actually just a special case of a second degree equation in three variables, which was extremely important to Greek mathematicians, namely x2+y2 = z2. Geometrically, this is the equation of a circle of radius z, centered on the origin. But more importantly to the Greeks, if x and y are the lengths of the sides of a right angled triangle, the length of the hypotenuse is z. This equation was discovered by Pythagoras (or someone in his school) some time in the 6th century BCE, and (of course) it was known as the Pythagorean theorem. If the lengths of the sides of the triangle are whole numbers, it is not necessarily true that the so is the length of the hypotenuse, since all we know is z=√(x2+y2). Indeed, the length isn't necessarily even rational – a fact which was considered quite scandalous at the time.

But if the length of the hypotenuse is a whole number, then (x,y,z) is called a Pythagorean triple. Such a triple was held in mystical regard by the Pythagoreans, so the search for such triples assumed a high importance. This search amounted to finding integer solutions of what we now call an instance of a Diophantine equation in 3 variables. Note that any solution in rational numbers also yields an integral solution. This is because if (x,y,z) is a rational triple, then multiplying through by the least common multiple of the denominators gives a triple of integers. (This works because the equation is homogeneous, with all terms having the same degree.)

No lesser a man than Euclid discovered how to describe all solutions in (positive) integers of this equation. Again, this is given in parametric form:

x=(u2-w2)w, y=2uvw, z=(u2+w2)w
It's trivial to check that you get a soution of the equation for any integer u, v, w (including 0 and negative values). The proof that this gives all solutions is harder and we leave that for you to think about.

#### Pell's equation

With the next step up in complexity, we reach some interesting territory that's directly connected with algebraic number theory. This involves an equation of the form x2 - ny2 = 1 for some positive integer n. n is fixed and not an additional variable. Solutions of this equation, however, depend very much on the arithmetic properties of n, and in some sense help us understand these properties.

The name "Pell's equation" was conferred by Leonhard Euler, who mistakenly gave credit for it to the otherwise obscure mathematician John Pell. However, the history of the equation goes all the way back to the Greeks, who were especially concerned with the case n=2, because it shines some light on the number √2. As you recall, √2 was of great interest (or concern) to them, ever since they realized √2 is not a rational number.

If y=0, then x=±1, so let's exclude that trivial solution. Then we can rewrite the equation as (x/y)2 = n+1/y2. Suppose there exist infinitely many solutions of the equation (as is in fact the case). Taking one with y large enough, 1/y2 can be arbitrarily small. And therefore, a solution (x,y) gives us a rational number x/y as close as we like to √n. This fact was already known implicitly to the Greeks, who also understood limit arguments. So they were pleased to know that even though √2 isn't rational, it can be approximated arbitrarily well by rational numbers. And the same is true of √n if n isn't a perfect square, so that √n is not rational.

Rather than pursue the details of Pell's equation, we need to look at how it's related to algebraic number theory. Recall that the set of all rational numbers is usually denoted by Q. Mathematically, this set has the structure known as a ring, in that it has the arithmetic operations of addition, subtraction, and multiplication, which observe certain rules. In fact, Q also has the structure of a field, which also allows for division by any of its elements other than 0. We will say much more about rings and fields in the next installment, so let's dispense with the formalities for now. It's safe, for present purposes, to think of the arithmetic operations of rings and fields as the ones you are already quite familiar with.

The integers, Z, also form a ring. Let Z[√n] stand for the set of all polynomials in powers of √n with coefficients in Z, and likewise for Q[√n] (with coefficients in Q). If n is a perfect square, these sets are just Z and Q, so let's assume n isn't a prefect square. It's obvious that these are rings also. But they are not necessarily fields, since 1/√n isn't rational if √n isn't.

What may be surprising, however, is that some elements of the form a+b√n may have inverses in these rings even if b≠0 and a≠±1. For instance, let n=2, and consider the number α=3+2√2 in Z[√2]. Observe that (3+2√2)(3-2√2) = 1. Hence 1/α = 1/(3+2√2) = 3-2√2, which is also an element of Z[√2]. Thus α has an inverse in Z[√2]. Such an element is called a unit. The only units of Z itself are ±1. But it turns out that for any positive n that's not a perfect square, the ring Z[√n] has infinitely many units.

What do these units look like? Well, first we need to define one more thing. If a+b√n is in Z[√n], define the function N(a+b√n) to be the number (a+b√n)(a-b√n) = a2-nb2. (This is the same definition as the square of the norm of a complex number, where n=-1.) Clearly, N(α) is also an integer for any α∈Z[√n]. It's simple algebra to show that if α,β∈Z[√n], then N(αβ)=N(α)N(β).

Given all this, if α∈Z[√n] is a unit, with inverse 1/α, so α(1/α)=1, we must have N(α)=1/N(1/α) is an integer, so N(α) is a unit of Z, which means it must be ±1. Conversely, if N(&alpha) = N(a+b√n) = (a+b√n)(a-b√n) = ±1, then α is a unit because it has an inverse. Hence the units α of Z[√n] are precisely the α such that N(α)=±1.

This is what allows us to show that Pell's equation has an infinite number of solutions, if there are any at all besides ±1 (which we haven't actually shown here). This is because every solution of Pell's equation a2-nb2 = 1 gives us a unit α = a+b√n with N(α)=1. For any such α, N(±αk)=1 too, for any k∈Z by the above, hence all ±αk are units, and give solutions of Pell's equation. Moreover, these are all distinct, because the only rational numbers that are units are ±1 (when b=0). For any irrational unit α the absolute value |α|≠1. We may assume |α|>1 (otherwise use 1/α). Then αk are distinct numbers for all positive k∈Z because the absolute values |αk|=|α|k are all distinct.

There may be other units as well, satisfying a2-nb2 = -1. For example, if n=5, we have N(2+√5)=-1, so 2+√5 is a unit of Z[√5]. If there exists a unit β = a+b√n with N(β)=-1, then there are also an infinite number of solutions of a2-nb2 = -1, corresponding to the units βk for odd integers k. (If k is even, we get solutions of Pell's equation.)

#### Catalan's conjecture

Catalan's conjecture can be stated as saying: the only consecutive whole numbers that have powers which differ by just one is the pair (2,3) -- where 32 - 23 = 1. Stated in the form of a Diophantine equation, the conjecture says there is only one solution of the equation xp - yq = 1, where x, y, p, and q are each more than 1, and x and y are consecutive (either y=x+1 or vice versa). Note that, like the Fermat problem, this is an assertion about an infinite set of possible equations.

To be sure, this problem sounds rather specialized, but it's still rather surprising to imagine that only one set of numbers meeting the stated conditions can exist. There are, after all, infinitely many pairs of consecutive numbers, and we ask only that there be two different powers of them which differ by one.

It's still an open question, but there has been recent progress. In 1976 it was shown that there can be at most finitely many exponents p, q for which any solution can be found. In other words, there is some (probably very large) number M for which all solutions have p and q less than M. Theoretical studies have discovered suitable values of M. (1017 will do.)

Then in 2000 Preda Mihailescu found that, except for 2 and 3, p and q must be what are called "double Wieferich primes", i. e. p(q-1) must be congruent to 1 modulo q2 and q(p-1) must be congruent to 1 modulo p2. Wieferich primes turn up in other number theoretical problems, but this is obviously a rather restrictive condition. (2 and 3 do not fit this criterion, but as often happens, very small primes are a special case.)

Given this result, Catalan's conjecture could be decided by computation alone, if all pairs of double Wieferich primes below the known limits can be identified. But a purely theoretical solution also seems tantalizingly close.

#### Beal's conjecture

Beal's conjecture is:
There are no positive integers x, m, y, n, z, r satisfying the equation

xm + yn = zr

where m, n, r > 2 and x, y, z are co-prime (have no prime factors in common).

### The ABC conjecture

Now that Fermat's problem has been solved, one might wonder whether there are any interesting generalizations to consider, or in fact any other problems in the area of Diophantine equations that are similarly important and challenging. And the answer is: Yes, definitely.

The so-called ABC conjecture, which was formulated in the mid-1980s by Joseph Oesterlé and David Masser, is both a generalization of Fermat's Last Theorem (in the sense that it imples FLT), and also of extreme importance for Diophantine equations in general.

The ABC conjecture is easy enough to state in elementary terms, though on the surface it has little relevance to Diophantine equations. A number is said to be "square-free" if it is not divisible by the square of any prime number. We then just need to define the "square-free part" of an integer N (denoted by sfp(N)) as the largest square-free divisor of N. Clearly, sfp(N) is just the product of all primes that divide N. Now suppose A and B are two numbers which have no prime factors in common (they are said to be "relatively prime), and C + A + B.

Masser proved that the ratio sfp(ABC)/C can be arbitrarily small for some choice of A and B. However, if n is an integer greater than 1, the ABC conjecture states that the ratio sfp(ABC)n/C can't be arbitrarily small. That is, there is some positive (non-zero) lower bound for it, no matter what A and B are.

How on Earth is this related to Fermat's equation or other Diophantine problems? For this you need to know a little about how FLT was proven. A very important part involved the construction of an "elliptic curve" called the Frey curve (after Gerhard Frey). This curve is defined by the equation y2 = x(x-A)(x-B). Two important quantities related to this equation are its "discriminant", which is (ABC)2, and its "conductor", which is sfp((ABC)2), where C + A + B. It turns out (which is the difficult part to show), that if there were a solution of Fermat's equation, then a contradiction could be derived, related to a property of elliptic curves known as "modularity". The contradiction shows that a solution of the Fermat equation can't exist.

The ABC conjecture enters, because if it were known to be true, then the proof of FLT would be easier, and many other Diophantine equations could be analyzed in a similar way by looking at elliptic curves and their conductors and discriminants.

This is a very active area of research at the present time.

### Perfect numbers, aliquot sequences

For a positive integer n, let s(n) denote the sum of the divisors of n (including 1, but less than n). (Note that s(n) = 1 if n is prime. A similar function σ(n) is defined to include n as well as 1, so that σ(n) = s(n) + n. This function has the additional property that it is "multiplicative": σ(mn) = σ(m)σ(n).) A number is said to be "perfect" if s(n) = n. Euclid showed that 2k-1(2k - 1) is perfect if 2k - 1 (the kth Mersenne number) is prime for some positive integer k. Euler showed that all even perfect numbers are of this form. It is a long-standing unproven conjecture there are no odd perfect numbers.

Two positive integers m, n are said to be "amicable" if s(m) = n and s(n) = m. So if you consider iterates of the s(n) function, you get a cycle of length 2. It is possible to have longer cycles. A finite set of numbers that consist of the iterates of s(n) is said to consist of "sociable numbers. Another long-standing unproved conjecture, known as the Catalan-Dickson conjecture, says that any sequence of iterates of s(n) either repeats after a finite number of steps (giving a set of sociable numbers) or else reaches the value 1 (when the next-to-last value is prime).

### Recommended references: Web sites

#### Site indexes

Number Theory Web
Extensive collection of general resources and links for number theory, by Keith Matthews. See especially the Things of Interest to Number Theorists, and in particular, Descriptions of areas/courses in number theory, lecture notes.
Mathematics Archives - Number Theory
Extensive annotated list of links.
Open Directory Project: Number Theory
Categorized and annotated number theory links. A version of this list is at Google, with entries sorted in "page rank" order.
Math Forum Internet Mathematics Library: Number Theory
Alphabetized list of links with extensive annotations.
Galaxy: Number Theory
Categorized site directory. Entries usually include descriptive annotations. Has subcategories for open problems, Diophantine equations, factoring, and prime numbers.
Number Theory
Links at an Italian site called the "Mathematical BBS".
Yahoo: Number Theory
Very short list.

#### Sites with general resources

As últimas do mundo da Matemática
Site contains notes (mostly in English, some Portugese) on topics and problems in number theory, and a few external links.

#### Surveys, overviews, tutorials

Number theory
Article from Wikipedia.
Introduction to Number Theory
A complete online course, by X.-D. Jia. Covers factorization, congruences, quadratic residues, and continued fractions.
Mathematical Atlas: Number Theory
Good overview, with references to books, software, and other sites.
Unsolved Problems
Part of the Sci.Math Frequently Asked Questions in Mathematics site with brief descriptions of the odd perfect number problem, the Collatz problem, Goldbach's conjecture, and the twin prime conjecture.
Some Simple Unsolved Problems
Brief remarks on the Goldbach conjecture, twin primes, and perfect numbers, with some related pages. By Peter Alfeld.
Number Theory Glossary
Provided by Robert Campbell.
MathPages: Number Theory
Many brief articles on a wide variety of topics, mostly elementary, at Kevin Brown's MathPages.
Number Theory: A Lightning Course
Very brief overview, by Jeremy T. Teitelbaum.

#### Prime numbers and factorization

Galaxy: Mersenne primes
Categorized site directory. Entries usually include descriptive annotations.
The Prime Pages
An excellent site dealing with prime numbers, by Chris Caldwell. Includes descriptions of prime conjectures and open questions, Mersenne primes, and the Riemann Hypothesis. There's also an extensive glossary of terms related to primes and number theory.
Prime Numbers
Part of the The MacTutor History of Mathematics archive. Lists a number of unsolved problems involving primes.
Prime number
Article from Wikipedia.
The Great Internet Mersenne Prime Search
A cooperative distributed computing project to identify Mersenne primes. The four largest known primes have been found by this project. Also has information on other distributed compting projects.
Landon Curt Noll's Prime Pages
Links to information on prime numbers, Mersenne primes, perfect numbers, etc. Provided by Landon Curt Noll.
Mersenne Prime Digits and Names
Table of known Mersenne primes and useful related links. Provided by Landon Curt Noll.
243112609-1 is prime
Information on the Mersenne prime 243112609-1 discovered in August 2008. Also has useful links about Mersenne primes and prime numbers in general. Provided by Landon Curt Noll.
Luke's Marin Mersenne Page
Large list of links on Marin Mersenne and Mersenne primes -- probably more than you ever thought possible. By Luke Welsh.
Mersenne Primes Web Ring
Yes, a Web ring just for Mersenne primes. Who would have thought?
Will Edgington's Mersenne Page
Contains databases of Mersenne factorizations and primes, proofs of various propositions, external links.
FactorWorld
All about algorithms for factoring integers. Site includes papers on the subject, downloadable code, and external links. By Scott Contini.
Jim Howell's Math Page
Includes external links, downloadable software for factoring, and pages about prime numbers, Mersenne numbers, and Fermat numbers, factoring algorithms, and aliquot sequences.
Primal Surge
March 2005 Math Trek article by Ivars Peterson about Mersenne primes and the discovery of the 42nd Mersenne prime.
Priming Upward
June 2004 Math Trek article by Ivars Peterson about Mersenne primes and the discovery of the 41st Mersenne prime.
Megaprime Champion
December 2003 Math Trek article by Ivars Peterson about Mersenne primes and the discovery of the 40th Mersenne prime.
Mersenne Megaprime
July 1999 Science News article by Ivars Peterson about Mersenne primes and the discovery of the 39th Mersenne prime.
Lucky choice turns up world-record prime
September 1997 Science News article by Ivars Peterson about Mersenne primes and the discovery of the 36th Mersenne prime.

#### Twin prime conjecture

Twin prime conjecture
Article from Wikipedia.
Prime Twins
June 2, 2001 article from Science News, by Ivars Peterson. Reports on new data about the distribution of twin primes.
Gaps Between Consecutive Primes
Describes computational work by Tomás Oliveira e Silva.
Prime Finding: Mathematicians mind the gap
March 29, 2003 news story from Science News about what would be, if correct, a very significant advance in the theory of the distribution of prime numbers. The new result says that there are infinitely many pairs of primes which are closer together than any nonzero fraction of the average spacing between primes. [Part of the proof appears to be incorrect, so the result is still in question.]

#### Goldbach's conjecture

Galaxy: Goldbach Conjecture
Categorized site directory. Entries usually include descriptive annotations.
Goldbach's conjecture
Article from Wikipedia.
Goldbach Conjecture Verification
Describes computational work by Tomás Oliveira e Silva.
Verifying Goldbach's Conjecture up to 4 × 1014
Describes computational work by Jörge Richstein. Includes a good bibliography.

#### Analytic number theory

Galaxy: Analytic Number Theory
Categorized site directory. Entries usually include descriptive annotations.
Math Forum Internet Mathematics Library: Analytic Number Theory
Alphabetized list of links with extensive annotations.
Analytic number theory
Article from Wikipedia.
An Introduction to Analytic Number Theory
Excellent summary of several important basic results: Dirichlet's theorem, the prime number theorem (showing how the zeta function is related to the distribution of primes), and Chebyshev's bias. By Noam Elkies.

#### Perfect numbers, aliquot sequences

Galaxy: Perfect Numbers
Categorized site directory. Entries usually include descriptive annotations.
Perfect number
Article from Wikipedia.
Aliquot sequences
Short introduction by Wieb Bosma.
Aliquot sequences
A longer page on the subject by Wolfgang Creyaufmueller. Includes basic definitions, summary and databases of computational results, external links, bibliographic information, factorization, downloadable software.
Aliquot sequences
Short page by Jim Howell.
Perfect, Amicable and Sociable Numbers
Long page by David Moews. Includes overview, related and generalized problems, bibliography, technical appendix.
The Multiply Perfect Numbers Page
A "multiply perfect" number (also called "k-fold perfect", "multiperfect", "abundant", etc.) is one where the sum of its divisors (including the number itself) is a multiple of the number. This page by Achim Flammenkamp presents computational results and external links.
Amicable Numbers
Expository survey by Hisanori Mishima.
MacTutor History of Mathematics: Perfect Numbers
Long article on the history of perfect numbers.

#### Catalan's conjecture

Galaxy: Catalan Conjecture
Categorized site directory. Entries usually include descriptive annotations.
Catalan's conjecture
Article from Wikipedia.
Catalan's Conjecture Research
Catalan's conjecture is that 8 and 9 are the only two consecutive integral powers.
Preda Mihailescu
Personal homepage. Contains unpublished drafts of his work on Catalan's conjecture.
Conquering Catalan's Conjecture
June 24, 2002 article by Ivars Peterson on Preda Mihailescu's results.
Zeroing In on Catalan's Conjecture
Science News article from December 2, 2000. Preda Mihailescu has proved a result that may lead to a solution of Catalan's conjecture.

#### The ABC conjecture

Galaxy: ABC Conjecture
Categorized site directory. Entries usually include descriptive annotations.
By Abderrahmane Nitaj. Includes explanation and links.
Abc conjecture
Article from Wikipedia.
Juliusz Brzezinski's ABC Conjecture Page
Articles available in TeX, DVI, and PostScript form.

#### Beal's conjecture

The Beal Conjecture
Short page by Andrew Beal with a history and statement of the problem.
Beal's Conjecture: A Search for Counterexamples
A page with Python code to search for counterexamples to Beal's conjecture, by Peter Norvig.
The Beal Conjecture and Prize
A \$100,000 prize is offered for a proof or counterexample to Beal's Conjecture.
Prize offered for solving number conundrum
November 15, 1997 article from Science News.

#### The Collatz Problem

Galaxy: Collatz Problem
Categorized site directory. Entries usually include descriptive annotations.
Collatz conjecture
Article from Wikipedia.
3x+1 Problem and Related Problems
Page by Jeffrey C. Lagarias dealing with the Collatz problem. Lagarias has a published paper on The 3x+1 problem and its generalizations. Also an annotated bibliography (in PostScript format).
On the 3x+1 Problem
A long page by Eric Roosendaal with computational results, some theorems, and external links. Roosendaal has also organized a search for non-terminating sequences.
Computational Verification of the 3x+1 Conjecture
Describes an extensive computational search by Tomás Oliveira e Silva. See also his work on a generalization of the problem.
Collatz 3n+1 Problem Structure
Some observations on the Collatz problem and generalizations, by Ken Conrow.
Papers on the 3x + 1 Problem
Several papers by Peter Schorer on the 3x+1 problem, in the form of PDF files.

#### Other problems

Least Primitive Root of Prime Numbers
A primitive root of a given prime p is defined as a positive integer (mod p) that generates the multiplicative group of Z/pZ. Artin's conjecture gives an asymptotic formula for N(x,a): the number of primes less than x for which a is a primitive root of p. This page by Tomás Oliveira e Silva presents some computational results.

### Recommended references: Magazine/journal articles

Prime Pursuit
Ivars Peterson
Science News, October 16, 2002, pp. 266-267
A surprisingly simple polynomial time algorithm for testing primality of numbers has just been discovered.
Pi à la Mode
Ivars Peterson
Science News, September 1, 2001, pp. 136-137
A potential link between number theory and chaotic dynamics may make it possible to prove that the digits of π are random.
Surprisingly Square
Ivars Peterson
Science News, June 16, 2001, pp. 382-383
In 1996 Stephen Milne announced the discovery of new formulas for enumerating representations of numbers as sums of squares. Since then, other mathematicians have offered simpler proofs of some of the results, as well as simpler formulas.
[References]
Questions about Powers of Numbers
Barry Mazur
Notices of the AMS, February 2000, pp. 195-216
Along with questions about prime numbers, questions about integer solution of equations involving pure powers of numbers play a major role in classical number theory. The ABC conjecture, if true, would provide answers to many questions about Diophantine equations involving powers of integers -- including the Fermat equation and the Catalan equation. Heuristic arguments show how the conjecture arises.
[Article in PDF format]
A Generalization of Fermat's Last Theorem: The Beal Conjecture and Prize Problem
R. Daniel Mauldin
Notices of the AMS, December 1997, pp. 1436-1437
Along with a statement of Beal's conjecture there are brief descriptions of similar and related problems, such as the ABC conjecture and the Fermat-Catalan conjecture.
[Article in PDF format]
A Tale of Two Sieves
Carl Pomerance
Notices of the AMS, December 1996, pp. 1473-1485
Some of the most powerful methods of factoring large numbers are based on the based on the "sieve of Eratosthenes", though much more sophisticated. The best currently known sieve methods are the "quadratic sieve" and the "number field" sieve. Though factoring methods based on elliptic curves are generally better, an overview of these two sieves illustrates current factoring technology.
[Article in PDF format]
Beyond the Last Theorem
Dorian Goldfeld
The Sciences, March/April 1996, pp. 34-40
The recent proof of Fermat's Last Theorem reveals a close relationship to another important conjecture, known as the ABC conjecture. This conjecture is easy to state, and if verified would vastly simplify the analysis of Diophantine equations.
The 3x+1 Problem and its Generalizations
J. C. Lagarias
American Mathematical Monthly, January 1985, 3-23
Good overview of the problem.

### Recommended references: Books

John Stillwell – Elements of Number Theory
Springer-Verlag, 2003
Although the properties of the rational integers have been studied by mathematicians for hundreds of years, as a result of the work of people like Kummer and Dedekind the subject became understood in terms of what is now called abstract algebra. Stillwell provides an introduction to the subject that emphasizes algebraic concepts like rings and ideals.
Paul Erdős; János Surányi – Topics in the Theory of Numbers
Springer, 2003
Erdős, of course, is famous as one of the most prolific and unconventional mathematicians of all time. His favorite subject was number theory, and this book is an unconventional introduction to the subject. Although it covers the important basic topics, it also discusses recent discoveries, interesting methods, and unsolved problems. As such, it shows why number theory remains endlessly fascinating to maththematicians.
David Bressoud; Stan Wagon – A Course in Computational Number Theory
Key College Publishing, 2000
Number theory is largely the study of properties of the rational integers and algebraic integers. As such, it is quite amenable to investigation using computers. Indeed, questions about prime numbers and Diophantine equations were among the first scientific applications of computers more than 50 years ago. This book discusses basic algorithms used in number theory and provides a good introduction to the subject.
Richard K. Guy -- Unsolved Problems in Number Theory
Springer-Verlag, 1994
Here is the definitive book on the subject. At least, as far as problems which can be stated in "elementary" terms are concerned. (It doesn't deal with algebraic number theory or analytic questions like the Riemann hypothesis, the Langlands program, etc.) Almost every problem listed here can be explained in terms of high school algebra, at most. Solutions are another matter, however.
David M. Bressoud -- Factorization and Primality Testing
Springer-Verlag, 1989
Bressoud's book could be used as a good introduction to elementary number theory, as it covers many of the standard topics. The mathematical background required is little more than high school algebra. But it explains the basic primality testing and factorization algorithms, including the application of elliptic curves. Many samples of computer code are included.