Guide to Tables in the Theory of Numbers (1941) / Chapter Skim
Currently Skimming:
DESCRIPTIVE SURVEY: F. Theory of Numbers
DESCRIPTIVE SURVEY: F. Theory of Numbers
Pages 5-84
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 5... ...
with exactly four distinct prime factors of which the second in order of magnitude is 5, appears in DICKSON 3. If n is such that |
From page 6... ...
, by means of which isolated values of |
From page 7... ...
holds for all x prime to n, has important applications in the theory of the binomial congruence. CAUCHY 1, 2 contain tables of $(n)
|
From page 8... ...
Glaisher has given several tables of numerical functions which depend upon the difference between the number of divisors of n of one specified form, and the number of divisors of n of another specified form. These functions occur naturally in the series expansion of certain elliptic functions and are also connected with the number of representations of integers by certain binary quadratic forms.
|
From page 9... ...
, plays a very fundamental role in the theory of numerical functions, and has the value +1 or -- 1 if n is a product of an even or odd number of distinct primes, but vanishes for all other numbers n> 1. This function is so easy to evaluate for isolated numbers whose factors are known that tables of j*
|
From page 10... ...
) are described under d4 (solutions of special binomial congruences)
|
From page 11... ...
. Let g be any primitive root of p" so that g'= 10 (mod p")
|
From page 12... ...
For 467g/>"< 1000 only the periods for l/p" are given. The primitive roots used for each p" are given on page 420.
|
From page 13... ...
incongruent primitive roots of p. The fact that there are so many primitive roots causes no difficulty in the theory of the binomial congruence but has caused considerable confusion in the tabulation of primitive roots.
|
From page 14... ...
The following is a tabular description of the 20 extensive tables of primitive roots arranged according to the highest value of p tabulated. Tables of Primitive Roots reference range of t factorization olp-i type of root indication that i0 is a root JACOBI 2 1-1000 yes 3 y*
|
From page 15... ...
A more extensive table of the number of primes whose least positive and greatest negative primitive root have a given value is given in CUNNINGHAM, WOODALL and CREAK 1, for p£ 25 409. It is remarkable that primes have such small primitive roots,i and this fact has been of great assistance in the preparation of tables described above.
|
From page 16... ...
131-191) p< 300 000 no yes There are four tables of Kraitchik which give residue-indices of 2 for primes of special forms up to high limits as follows: KRAITCHIK 4, p.
|
From page 17... ...
A table for a fixed prime p of powers of a primitive root g giving for each number i, 0^i^p -- 2, the least positive number « for which g' = n (mod />) may be thought of as similar to a table of the exponential function f.
|
From page 18... ...
An entirely independent calculation of a set of tables of similar extent (including also powers of primes <200) was made by HOUEL 1, who based his table on absolutely least primitive roots.
|
From page 19... ...
d4. Solutions of special binomial congruences Tables of powers and indices of a primitive root (described under ds)
|
From page 20... ...
. In spite of the availability of this general method, there exist many tables giving explicit solutions of binomial congruences of more or less special type, partly for the same reason that, in spite of the existence of tables of logarithms, there are numerous tables of square and cube roots, and partly because such tables have in most cases some important connection with the problem of factorization, a fact which accounts for the many extremely special tables described in what follows.
|
From page 21... ...
t q=2,3,5,6 p" < 10000, p g 19. Special tables of the general binomial congruences x" = r (mod p)
|
From page 22... ...
A table of all three-digit cube-endings, i.e., cubic residues, modulo 1000, is given in MATIES 1. For the case n = 4, GAUSS 2 has a short table giving for each /> = 4x+1< 100 not only its biquadratic residues but also those numbers
|
From page 23... ...
Finally there are tables giving merely the frequency of primes having a given number a as an «th power residue. These have been obtained from tables of residue-indices by counting the number of p's having a given entry.
|
From page 24... ...
The problem of factoring has long been recognized as a very fundamental one, and factor tables, as a partial solution of this problem, have a long and interesting history. This is especially true of the first of the two kinds of factor tables described below which we have called "ordinary." These factor tables were constructed for general use, the entries being found either by a sieve or by a multiple process.
|
From page 25... ...
It is not difficult to see that the advantages of condensation gained by raising the type number are soon more than offset by the difficulties of arranging and ordering the table, if indeed one is to maintain the usual condensed form in which the number, whose least factor is given, is indicated merely by the position which that factor occupies in the body of the table. A factor table of high type and of very considerable extent could, however, be arranged in a form similar to a list of primes in which the last few digits of each number considered are given together with some symbol for its factor.
|
From page 26... ...
In referring to nineteenth century tables mention should be made of the huge manuscript table of KULIK 3 which extends from 4 000 000 to 100 330 201.
|
From page 27... ...
In many cases short tables giving the results of a particular investigation have been published, mostly in periodical [27]
|
From page 28... ...
Often, however, each entry represents a great deal of hard work, in no way lessened by the existence of the other entries of the table. Occasionally, the complete factorization of a certain number is not known, but only one or two small prime factors are given.
|
From page 29... ...
Here the reader will find a history of the problem with complete references to the original sources. A short table giving merely the number of prime factors of 2P -- 1 for p^257 known in 1932 appears in D
|
From page 30... ...
24-26) of KRAITCHIK 4 gives all prime factors <300 000 of 2"± 1 for n odd and <257 and of 2u+2+l for 4k+2 < 500 in those cases where the complete factorization of these numbers had not then been found.
|
From page 31... ...
For the bases a = 3, 5, 6, 7, 11 and 12 Cunningham and VVoodall give, together with many complete factorizations, all prime factors /><100 000 dividing either a"+l for n odd and ^109, or o"+l for n even and ^ 100. Only the factors of Qn(a)
|
From page 32... ...
/2 for 712 values of og 14 033 378 718, in those cases in which no prime factor exceeds 200. This table is only one of a set of 9 tables giving the factors of a2+62 to be described presently.
|
From page 33... ...
We have already pointed out that several tables of primitive roots give in addition the factorization of p -- 1. These are described in di.
|
From page 34... ...
The complete table gives for 2452 numbers of the form a2+62, 6^9 their complete factorization. The numbers a are so chosen that all the prime factors of a2+6" are less than 200.
|
From page 35... ...
A more slowly increasing series than the Fibonacci series has been factored by HALL 1. Here the complete factorization of the norm N(a" -- l)
|
From page 36... ...
222-232) has given a complete factor table of all numbers of the form £2"+1 lying between 108 and 10i2 with £<1000.
|
From page 37... ...
In spite of the existence of ordinary factor tables, the first use, whose importance is often not fully appreciated by those interested in distribution phenomena, is perhaps the best reason for the publication of lists of primes. Here, again, lists of consecutive primes are more useful than lists of primes of special form.
|
From page 38... ...
In each case are given the upper and lower limits of the range in which all the primes are determined. If, in addition, the author includes a factor table for the range considered, this fact is indicated by an asterisk.
|
From page 39... ...
DESCRIPTIVE SURVEY f. range 19 486 15319 488 187*
|
From page 40... ...
independently for use in checking factor tables. As already mentioned, isolated values of ir(x)
|
From page 41... ...
DESCRIPTIVE SURVEY fi x= k• 10«, k = .2(.2)
|
From page 42... ...
All the tables of types A-D cited so far that are due to Glaisher have been reproduced by J GLAISHER 1, 2, 3 in the introductions to his factor tables of the fourth, fifth and sixth millions.
|
From page 43... ...
fs. Primes of special form As in the case of consecutive primes, lists of primes of special form often occur as arguments of tables giving further information about these numbers.
|
From page 44... ...
Tables giving the number of primes belonging to given linear forms and less than certain limits date from SCHERK 1 (1833)
|
From page 45... ...
) Many lists of high primes dividing an + b" appear in Cunningham's Binomial Factorisations.
|
From page 46... ...
9-10. Poletti, Sturani and Gerardin have constructed by a sieve process factor tables up to high limits of numbers of the form A-n?
|
From page 47... ...
For instance, the method of factoring depending on quadratic residues, as described by Legendre, makes use of certain lists of linear forms or "linear divisors" of quadratic forms x*
|
From page 48... ...
. SEELHOFF 1 contains lists of binary quadratic forms especially devised for factorization purposes.
|
From page 49... ...
for each coprime pair (a, 6) with A similar table by CUNNINGHAM 36 extends to o<100, 6<100.
|
From page 50... ...
. A special table due to J
|
From page 51... ...
and for all p"^ 128 with the exception of 125 and 127. All these tables are, of course, designed for the application of Gauss' method of exclusion and serve to reduce such problems as the representation of a number by a given binary quadratic form to the mere combination of linear forms, and thus to make applicable a certain graphical and mechanical technique fully described under another report of this Committee: Z
|
From page 52... ...
Since the even powers of a primitive root of p" are the quadratic residues of p", while the odd powers are the quadratic non-residues, a table of powers of a primitive root gives in particular a table of residues and non-residues. Such tables were cited and described under ds.
|
From page 53... ...
-- Ay2, so that tables of these forms deal only with those D's which have no square factor > 1. In general we may speak of the linear divisors of any binary quadratic form / as the set of arithmetic progressions to which any prime factor of a number properly represented by/must belong.
|
From page 54... ...
The tables of LEVANEN 2 give for 62 selected binary quadratic forms of negative determinant > -- 385 the corresponding linear divisors.
|
From page 55... ...
Since Euler's time the importance of the Pell equation to the theory of binary quadratic forms and of quadratic fields K(\/D) has been fully realized and Euler's original tables have been greatly extended.
|
From page 56... ...
= - 4. These are used in constructing automorphs of indefinite binary quadratic forms, or the units of the real quadratic field K(\/D)
|
From page 57... ...
A similar table for D^997 is due to CAYLEY 1. Solutions of (5)
|
From page 58... ...
Conformal multiplication is the basis of the extensive tables of solutions of (1) prepared by Nielsen.
|
From page 59... ...
CUNNINGHAM 7 gives all four partitions for /><100 000. This table is extended from 100 000 to 125 683 in CUNNINGHAM 36, where also are found several other tables giving quadratic partitions of primes of special form as follows.
|
From page 60... ...
js. Equations in more than 2 unknowns, rational triangles All but a few tables of this sort have to do with rational triangles, and most of these are lists of rational right triangles.
|
From page 61... ...
Two extensive tables arranged according to values of m and n may be cited. The first, BRETSCHNEIDER 1 gives all primitive triangles generated with n |
From page 62... ...
in spite of the fact that it is a trinomial congruence of the eighth degree. We may cite here however the table of REUSCHLE 3 which gives not only the primitive solutions of the congruence x" - 1 = 0 (mod p)
|
From page 63... ...
1. DIOPHANTINE EQUATIONS OF DEGREE >2 Actual tables of solutions of Diophantine equations of degree d>2 exist only for d = 3 and 4, although short notes giving occasional solutions of such equations with d>4 are scattered throughout the literature on the subject.
|
From page 64... ...
+ Dy* + DV - SDxyz = 1, like the Pell equations, has an infinity of solutions.
|
From page 65... ...
m. DIOPHANTINE CONTINUED FRACTIONS A number of useful tables of the continued fraction developments of algebraic irrationalities have been published.
|
From page 66... ...
A tabular analysis of the continued fraction for \fD arranged according to the length of the period is given for D< 1000 in KRAITCHIK 6, where also is given a similar analysis of ( -- l+\/4/T+T)
|
From page 67... ...
INCE 1 gives in effect Pk and Qk, but not qk in the expansion of \fD for all ZK2025 of the form D=4£+2, 4* +3, and without square factors.
|
From page 68... ...
Existing tables refer to four sorts of forms: binary quadratic, ternary quadratic, quaternary quadratic, and binary cubic forms. The theory of binary quadratic forms arose from the problem of solving Diophantine equations of the second degree, and early tables reflect this origin.
|
From page 69... ...
The theory of quadratic fields is of course very closely related to that of binary quadratic forms, their difference being largely one of nomenclature. Hence many of the tables cited under p are instances of tables related to binary quadratic forms.
|
From page 70... ...
Two tables of indefinite binary quadratic forms are included in Ross 1. The "basic" table gives reduced forms (a, b, -- c)
|
From page 71... ...
We turn now to the consideration of tables related to ternary quadratic forms. Interest in such forms originated from the problem of representing binary quadratic forms by ternary forms, and the earliest table involving ternary forms is concerned with this problem, and is found in LEGENDRE 1.
|
From page 72... ...
ARNDT 3 gave all reduced binary cubics of negative discriminant -- D, their classes and characteristic binary quadratic forms for all possible D<2000. CAYLEY 3 reproduced part of this table in revised form.
|
From page 73... ...
, (« odd) where w = «0»« and «O is the product of the distinct prime factors of n, and where « is not divisible by the prime p.
|
From page 74... ...
prime GRAVE 2 prime GOUWENS 2 prime For some reason Gauss and his followers failed to discover another quadratic form representing Qn(x) which is, for some applications, more important than (2)
|
From page 75... ...
In fact, the theory of binary quadratic forms is practically identical with quadratic field theory, and many tables relating to the former subject (described under n) are applicable in the latter, and conversely.
|
From page 76... ...
In particular DELONE 2 lists all fields with discriminant -- D with Z><172. Extensive tables of relative cubic fields are given in ZAPOLSKAIA 1.
|
From page 77... ...
A similar table for the quartic field defined by a primitive 8th root of unity is given in BICKMORE and WESTERN 1. This gives the coordinates of a canonical complex prime factor of every prime p = &n+l<25 000.
|
From page 78... ...
is even. Thanks to recent investigations the asymptotic series of Hardy and Ramanujan now offers an effective and reliable method of obtaining isolated values of p(n)
|
From page 79... ...
. Table II (p.
|
From page 80... ...
+i for 2«^ 500, and eleven other values of 2n between 4000 and 4166. STACKEL 1 has a similar table due to Weinreich for n = 6k^ 16 800.
|
From page 81... ...
The Waring problem has been generalized in many ways, but almost all tables refer to the problem of representing numbers as sums of positive fcth powers. These tables are of two sorts: basic tables dealing with the representation of numbers from 1 to N as sums of some limited number of kth powers, and special tables giving such information for miscellaneous ranges of numbers between certain high limits.
|
From page 82... ...
GUPTA 6 has a special table for this problem of [82]
|
From page 83... ...
is a sum of not more than 12 cubes of primes. Waring's problem with polynomial summands is responsible for a number of special tables due to Dickson and his pupils.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.