Elementary number theory

The branch of number theory that investigates properties of the integers by elementary methods. These methods include the use of divisibility properties, various forms of the axiom of induction and combinatorial arguments. Sometimes the notion of elementary methods is extended by bringing in the simplest elements of mathematical analysis. Traditionally, proofs are deemed to be non-elementary if they involve complex numbers.

Usually, one refers to elementary number theory the problems that arise in branches of number theory such as the theory of divisibility, of congruences, of arithmetic functions, of indefinite equations, of partitions, of additive representations, of the approximation by rational numbers, and of continued fractions. Quite often, the solution of such problems leads to the need to go beyond the framework of elementary methods. Occasionally, following the discovery of a non-elementary solution of some problem, one also finds an elementary solution of it.

As a rule, the problems of elementary number theory have a history going back over centuries, and they are quite often a source of modern trends in number theory and algebra.

From preserved ancient Babylonian cuneiform tablets one may deduce that the Babyloneans were familiar with the task of factoring natural numbers into prime factors. In the 5th century B.C. the Pythagoreans established the so-called doctrine of even and odd numbers and justified the proposition that the product of two natural numbers is even if and only if at least one of the factors is even. A general theory of divisibility was created, in essence, by Euclid. In his Elements (3rd century B.C.), he introduces an algorithm for finding the greatest common divisor of two integers and on this basis he justifies the main theorem of the arithmetic of integers: Every natural number can be factored in one and only one way into a product of prime factors.

After C.F. Gauss, at the beginning of the 19th century, constructed a theory of divisibility of complex integers, it became clear that the study of an arbitrary ring must begin with the construction of a divisibility theory in it.

All properties of the integers are connected in one way or another with the prime numbers (cf. Prime number). Therefore, questions on the disposition of the prime numbers in the sequence of natural numbers evoked the interest of scholars. The first proof that the set of prime numbers is infinite is due to Euclid. Only in the middle of the 19th century did P.L. Chebyshev take the following step in the study of the function $\pi(x)$, the number of prime numbers not exceeding $x$. He succeeded in proving by elementary means inequalities that imply

$$0.92129\frac{x}{\ln x}<\pi(x)<1.10555\ldots\frac{x}{\ln x}$$

for all sufficiently large $x$. Actually, $\pi(x)\sim x/\ln x$, but this was not established until the end of the 19th century by means of complex analysis. For a long time it was considered impossible to obtain the result by elementary means. However, in 1949, A. Selberg obtained an elementary proof of this theorem. Chebyshev also proved that for $n\geq2$ the interval $(n,2n)$ contains at least one prime number. A refinement of the interval containing at least one prime number requires a deeper study of the behaviour of the function $\pi(x)$.

In the 3rd century B.C. the sieve of Eratosthenes (cf. Eratosthenes, sieve of) was used to select the prime numbers from the set of natural numbers. In 1918 V. Brun showed that a modification of this method can serve as a basis for the study of a set of "almost primes". He proved the Brun theorem on prime twins. The Brun sieve is a special case of general sieve methods (cf. Sieve method) which give estimates for collections of almost primes not exceeding $x$ and belonging to a sequence $\{a_n\}$ of natural numbers. Sieve methods can be used when "good" approximations in the mean are known for the amount of integers $a_n\leq x$ belonging to a progression the modulus of which grows with $x$. Among the sieve methods developed after Brun, the Selberg sieve is of special significance. The strongest results are obtained by a combination of sieve methods and analytic methods. A sieve method in conjunction with the Shnirel'man method made it possible to effectively find a number $k$ such that any natural number $n\geq4$ can be represented as a sum of at most $k$ prime numbers.

Two integers $a$ and $b$ are said to be congruent modulo $m\geq1$ if they have the same remainder on division by $m$. Gauss (in 1801) introduced the notation $a\equiv b$ $\pmod m$. This form of writing, which brings about the analogy of congruences and equations, turned out to be convenient and instrumental in the development of the theory congruences (cf. Congruence).

Many results obtained previously by P. Fermat, L. Euler, J.L. Lagrange, and others, and also the Chinese remainder theorem, can be stated and proved simply in the language of the theory of congruences. One of the most interesting results of this theory is the quadratic reciprocity law.

The ancient Babylonians knew a large number of "Pythagorean triples". Apparently they knew some method for finding arbitrary many integer solutions of the indeterminate equation $x^2+y^2=z^2$. The Pythagoreans used the formulas $x=(a^2-1)/2$, $y=a$, $z=(a^2+1)/2$ to find solutions of this equation. Euclid indicated a method that allows one to find in succession integer solutions of the equation $x^2+2y^2=1$ (a special case of the Pell equation). In his Aritmetika Diophantus (3rd century B.C.) made an attempt to setting up a theory of indeterminate equations (see Diophantine equations). In particular, for the solution of equations of the second and some higher degrees he used systematically a device that enabled him to find from one rational solution of a given equation other rational solutions of it. Fermat (17th century) discovered another method, the "method of descent", and solved by it a number of equations, but the so-called Fermat great theorem, which he declared to have solved, has turned out to be beyond the power of elementary methods.

Fermat solved the problem of representing natural numbers by sums of two squares of integers. As a result of research by Lagrange (1773) and Gauss (1801) the problem of the representation of integers by a definite binary quadratic form was solved. Gauss developed the general theory of binary quadratic forms. The solution of the problem of representing numbers by forms of higher degree (for example, the Waring problem) and by quadratic forms in several variables usually go beyond the framework of elementary methods. Only certain special cases of such problems can be solved elementarily. An example is Lagrange's theorem: Every natural number is the sum of four squares of integers. It should be mentioned that Diophantus in his Aritmetika repeatedly used the possibility of representing a natural number as the sum of four squares of integers.

To elementary number theory one also reckons the theory of partitions, the foundations of which were laid by Euler (in 1751). One of the basic problems of the theory of partitions is the study of the function $P(n)$, the number of representations of a natural number $n$ as a sum of natural numbers. Other functions of similar type are also treated in the theory of partitions. Continued fractions (cf. Continued fraction) appeared in connection with problems of approximate computations (extraction of the square root of a natural number, search for approximations of real numbers by common fractions with small denominators). Continued fractions are applied in solving indefinite equations of the first and second degree. Using the apparatus of continued fractions J. Lambert (1766) was the first to establish that the number $\pi$ is irrational. In the solution of various problems in the approximation of real numbers by rational numbers one uses in elementary number theory the Dirichlet principle, besides continued fractions.

In number theory it is easy to state many problems that can be formulated elementarily and have so far remained unsolved. For example; Is the set of even perfect numbers finite or not? Is there at least one odd perfect number? Is the set of Fermat prime numbers finite or not? Is the set of Mersenne prime numbers finite or not (cf. Mersenne number)? Is the set of prime numbers of the form $n^2+1$ finite or not? Is it true that there is at least one prime number between the squares of two consecutive natural numbers? Is the set of incomplete fractions of the expansion of $2^{1/3}$ into a continued fraction bounded or not?

References

[1]	B.A. Venkov, "Elementary number theory" , Wolters-Noordhoff (1970) (Translated from Russian) MR0265267 Zbl 0204.37101
[2]	I.M. Vinogradov, "Basic number theory" , Moscow (1981) (In Russian)
[3]	A.O. Gel'fond, Yu.V. Linnik, "Elementary methods in the analytic theory of numbers" , M.I.T. (1966) (Translated from Russian) MR201368 Zbl 0142.01403
[4]	A.Ya. Khinchin, "Continued fractions" , Univ. Chicago Press (1964) (Translated from Russian) MR0161833 Zbl 0117.28601
[5]	C.F. Gauss, "Disquisitiones Arithmeticae" , Teubner (1801) (Translated from Latin) MR2308276 MR1876694 MR1847691 MR1356001 MR1167370 MR1138220 MR0837656 MR0638487 MR0479854 MR0197380 Zbl 1167.11001 Zbl 0899.01034 Zbl 0585.10001 Zbl 0136.32301 Zbl 21.0166.04
[6]	H. Davenport, "The higher arithmetic" , Hutchinson (1952) MR0050598 Zbl 0049.30901
[7]	E. Trost, "Primzahlen" , Birkhäuser (1953) MR0058630 Zbl 0053.36002
[8]	G.E. Andrews, "Theory of partitions" , Addison-Wesley (1976) MR0557013 Zbl 0371.10001
[9]	, The history of mathematics from Antiquity to the beginning of the XIX-th century , 1–3 , Moscow (1970–1972) (In Russian)
[10]	H. Wieleitner, "Die Geschichte der Mathematik von Descartes bis zum Hälfte des 19. Jahrhunderts" , de Gruyter (1923)
[11]	L.E. Dickson, "History of the theory of numbers" , 1–3 , Chelsea, reprint (1971) MR1793101 MR1720467 MR0245501 MR0245500 MR0245499 MR1520248 MR1519706 MR1519382 Zbl 1214.11003 Zbl 1214.11002 Zbl 1214.11001 Zbl 0958.11500 Zbl 60.0817.03 Zbl 49.0100.12 Zbl 48.1114.03 Zbl 48.0137.02 Zbl 47.0100.04
[12]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) MR0568909 Zbl 0423.10001
[13]	W. Sierpiński, "Elementary theory of numbers" , PWN (1964) (Translated from Polish) MR0227080 MR0175840 Zbl 0122.04402
[14]	K. Ireland, M. Rosen, "A classical introduction to modern number theory" , Springer (1982) MR0661047 Zbl 0482.10001

Comments

A translation of [5] into English is [a1].

For Chebyshev's result mentioned above see also Chebyshev theorems on prime numbers.

A Pythagorean triple is a triple $(a,b,c)$ of natural numbers satisfying $a^2+b^2=c^2$ (cf. also Pythagorean numbers).

For representations of numbers by special (quadratic) forms see also Quadratic form; Goldbach problem. More on partitions can be found in Combinatorial analysis.

Concerning the questions stated at the end of the main article above see also Perfect number; Prime number; Twins.

Fermat numbers are the special case of Mersenne numbers, which are of the form $2^n-1$, when $n$ itself is of the form $2^m$ (cf. Mersenne number); here $n$, $m$ are natural numbers.

References

[a1]	C.F. Gauss, "Disquisitiones Arithmeticae" , Yale Univ. Press (1966) (Translated from Latin) MR0197380 Zbl 0136.32301
[a2]	D. Shanks, "Solved and unsolved problems in number theory" , Chelsea, reprint (1978) MR0516658 Zbl 0397.10001
[a3]	A. Weil, "Number theory: an approach through history: from Hammupari to Legendre" , Birkhäuser (1984)