# Definition of elementary number theory

It seems that most authors use the phrase "elementary number theory" to mean "number theory that doesn't use complex variable techniques in proofs."

I have two closely related questions.

1. Is my understanding of the usage of "elementary" correct?
2. It appears that advanced techniques from other areas (e.g. algebra) are allowed, just not complex variables. Are there historical reasons for why complex analysis singled out as a tool to avoid?

NB: I'm asking about how "elementary" usually is defined and why, not how it should be defined.

• One more question concerning this discussion is here mathoverflow.net/questions/150895/… – Alexey Ustinov Dec 5 '13 at 6:41
• No, your understanding is not correct or your question is not precise. You confuse or at least mix the notion of an elementary proof in number theory with that of elementary number theory. – user9072 Dec 10 '13 at 12:49

Your usage of "elementary" is correct; your definition is the one that most number theorists would use. You don't have to take my word for it however; just consider the first sentence of Selberg's Elementary Proof of the Prime Number Theorem:

In this paper will be given a new proof of the prime-number theorem, which is elementary in the sense that it uses practically no analysis, except the simplest properties of the logarithm.

Ironically, of the many known proofs of the prime-number theorem, this elementary proof ranks as one of the most complicated.

• I think this is an answer to what is (typically) considered as an elementary proof in number theory. Yet this is a question different from what is elementary number theory. Actually, I think for this question this answer is not correct, as this definition of elementary would include various things in algebraic number theory that are generally not considered as elementary number theory. – user9072 Dec 10 '13 at 12:47

I more or less agree with Kevin; "elementary" to me means "from first principles." Another way I would put this is that if Gauss didn't know it, it's not elementary.

• short and amazing way to define elementary num. theory – Konstantinos Gaitanas Sep 15 '13 at 14:18

Elementary number theory is better defined by its focus of interest than by its methods of proof. For this reason, I rather like to think of it as classical number theory. It deals with integers, rationals, congruences and Diophantine equations within a framework recognizable to eighteenth-century number theorists. Algebraic number theory does not qualify because of its level of abstraction, even though algebraic numbers were sometimes applied to particular problems in number theory before the nineteenth century. Analytic number theory is not only distinguished by the use of complex and harmonic analysis (for many problems these are by no means indispensable), but even more by the modern emphasis on counting the number of solutions to number theoretical problems approximately. In the eighteenth century they also liked to count the number of solutions when they could, but they wanted exact answers, which severely limited the range of counting problems that they could solve. It is true that Dirichlet brought analysis into number theory, but he also counted the number of divisors of integers approximately by averaging, and Gauss before him had done the same for class numbers and genera of binary quadratic forms, as one can see from remarks in article 301 in the Disquisitiones Arithmetica (but he never published his proofs). And Legendre in 1808 published an approximation to the counting function \pi(x) of the primes, which was the start of the line of development that led to the Prime Number Theorem (Gauss had also found an approximation, but this was published only in 1863 in his collected works). The systematic acceptance of approximate answers in number theory really is a nineteenth century development. It is obvious from his interests and techniques that Euler could have found many such results if he had wanted. In 1838 when Dirichlet wrote his first paper on the approximate average number of divisors, the cupboard was so bare that he could only cite the remarks of Gauss in article 301 and Stirling's and allied formulas (!) as prior work to motivate his own.

There is a field that was absolutely central to number theory from its earliest days but for which elementary tools no longer suffice by themselves - Diophantine analysis. Actually, this transition of Diophantine analysis from elementary to non-elementary status began in the nineteenth century with the use of algebraic number theory, and gathered force in the twentieth century. But of course, there is also a huge amount of Diophantine analysis by classical techniques from the nineteenth and twentieth centuries.

This question is formalised to some extent by reverse mathematicians who seek to understand precisely what parts of the foundations of mathematics are required to prove any given result. There is some interesting discussion in this paper by Stephen Simpson. It's quite amazing how much can be proved using elementary mathematics.

For example they discuss the axiom system PRA, primitive recursive arithmetic. At first it appears to be quite elementary. It then discusses a much more powerful seeming system called WKL0 that allows the construction of things like contour integrals allowing the use of the techniques of analytic number theory. But then it turns out that any number theoretical proof in WKL0 can actually be translated to one in PRA. (I suspect that in practice the translated proof is probably usually far to unwieldy to actually be read by a human.)

If you read the discussion of finitistic reasoning in that paper it may give some feel for why some mathematicians have felt mistrustful of using complex analysis (say) to prove results in number theory.

• That's a fantastic result! I've never trusted complex analysis and now I have an actual result to cite. – Qiaochu Yuan Nov 7 '09 at 2:44
• I'll reserve my judgement on this. A complex analysis proof rewritten in "elementary" terms might as well be practically inaccessible. – Ilya Nikokoshev Nov 7 '09 at 19:54

To me, "elementary" = in principle can be understood by a person who only knows high school math.

Notes:

• The person can be assumed to be extremely smart or a genius.
• What to mean by high school math can vary from person to person, but derivatives are certainly in and algebraic curves are certainly out.

Actually, this definition essentially coincides with the one in Wikipedia:

Several important discoveries of this field are Fermat's little theorem, Euler's theorem, the Chinese remainder theorem and the law of quadratic reciprocity. The properties of multiplicative functions such as the Möbius function and Euler's φ function, integer sequences, factorials, and Fibonacci numbers all also fall into this area.

The examples they give are exactly things people sometimes teach at schools — that happens only rarely, but the point is that none of these formally uses any "college material".

Elementary means that I know how to reduce it to "counting on fingers", college algebra, and linear algebra. That doesn't mean that other areas are to be avoided at all, though.

This definition works differently for different people, as that "I know how" expression is vague. In my book, probability is elementary but the Stone-Cech compactification $\beta N$ of the naturals is not.

I refine my answer: I think that problems in elementary number theory can be characterized as problems in number theory for which both the problem and its solution can be understood in a fair amount of time by someone with undergraduate mathematical knowledge. The condition that also the solution is elementary and does not involve advanced techniques should not be dropped because there are a lot of elementary problems (Fermat's last theorem) which are very easy to state but are not that easy to solve (that's a slight understatement of course).

And I think that it is wrong to exclude the complex numbers. For example the basic material on cyclotomic fields is what I would definitely call elementary number theory. Even quadratic reciprocity involves complex numbers (okay, perhaps one of the 10^18 proofs does not, I don't know).

I want to add that "elementary" should not be translated as "easy"!

Wikipedia has a definition of elementary number theory, but I don't know how well accepted it is.

To me elementary number theory encompasses those results that can be completely derived starting with the definition of prime and composite within a book of reasonable size (say, a few hundred pages at most) without using any material not found in the first three years of a traditional undergraduate mathematics education (so the level of such a book would be appropriate for the typical junior or senior mathematics major). Therefore, I would not immediately exclude complex numbers (as Arminius mentioned there are some beautiful proofs of quadratic reciprocity using complex numbers), but I probably would exclude very heavy-duty complex analysis that one often finds in proofs of, say, the prime number theorem.

An interesting point is that there are several approaches one can take to developing number theory starting with the very basic definitions. One can take a predominantly algebraic approach, a mostly analytic approach, a computational approach, or one can try to mix these together in some way. The result is that elementary number theory really encompasses several books, each starting from the basic definitions but developing the subject from a different perspective.

I would regard as 'elementary number theory' that what needs no previous mathematical knowledge, esp. no abstract algebra, no Galois theory and no (complex) analysis. 'Elementary number theory' could include what Euler and Gauss did and of course "elementary" means not "simple". I would regard the reducability of statements like the four colour theorem to diophantine ones as belonging to elementary number theory too. BTW, if I remember correctly, Euler wrote an algebra textbook containing the Fermat for exp.=3 case with the help of an uneducated pupil to guarantee it's elementary nature.

Whenever I've heard the term "elementary number theory", the speaker seems to mean "analytic number theory"

I would imagine that the reason for not using complex numbers is at least partially related to the idea that they're going over old results, that were essentially developed before the development of complex analysis.

Hope that helps

Probably there is no correct bounary between elementary and non-elementary number theory. There two possibilities: either we can apply limits or not. It is like the axiom of choice in the set theory.

1) If we have no $\lim$ then we have no $\pi$, no $e$, no little $o$,... Almost nothing.

2) If we have a $\lim$ then we can get any "non-elementary" construction as a limiting case of some "elementary" one. Almost all.

This answer was born after some thinking about "primarily opinion-based" question Is Discrete Fourier Series an elementary object?

In a book i saw a nice answer:
''Elementary Number Theory'' is Number Theory which is based on mathematics you can find in Euclid's ''Elements''