# Full text of "History Of The Theory Of Numbers - I"

## See other formats

PKBFACE. VII The properties of the set of all irreducible fractions, arranged in order of magnitude, whose numerators are ^m and denominators are ^n (called a Farey series if w=ra), have been discussed by many writers and applied to the approximation of numbers, to binary quadratic forms, to the composition of linear fractional substitutions, and to geometry (pp. 155-8). Some of the properties of periodic decimal fractions are already familiar to the reader in view of his study of arithmetic and the chapter of algebra dealing with the sum to infinity of a geometric progression. For the generalization to periodic fractions to any base 6, not necessarily 10, the length of the period of the periodic fraction for 1/rf, where d is prime to 6, is the least positive exponent e such that be — 1 is divisible by d. Hence this Chapter VI, which reports upon more than 160 papers, is closely related to the following chapter and furnishes a concrete introduction to it. The subject of exponents and primitive roots is one of the important topics of the theory of numbers. To present the definitions in the customary, compact language, we shall need the notion of congruence. If the difference of two integers a and 6 is divisible by m, they are called congruent modulo m and we write a=b (mod in). For example, 8=2 (mod 6). If n*= 1 (mod m), but n'^1 (mod m) for 0<s<e, we say that n belongs to the exponent e modulo m. For example, 2 and 3 belong to the exponent 4 modulo 5, while 4 belongs to the exponent 2. In view of Euler's generalization of Fermat's theorem, stated above, e never exceeds <£(w). If n belongs to this maximum exponent <£(n) modulo m, n is called a primitive root of m. For example, 2 and 3 are primitive roots of 5, while 1 and 4 are not. Lambert stated in 1769 that there exists a primitive root of any prime p, and Euler gave a defective proof in 1773. In 1785 Legendre proved that there are exactly <f>(e) numbers belonging modulo p to any exponent e which divides p — 1. In 1801 Gauss proved that there exist primitive roots of m if and only if m = 2, 4, pk or 2pk, where p is an odd prime. In particular, for a primitive root a of a prime modulus p and any integer N not divisible by p, there is an exponent ind N, called the index of N by Gauss, such that N==aindN (mod p). Indices play a r61e similar to logarithms, but we require two companion tables for each modulus p. The extension to a power of prime modulus is immediate. For a general modulus, systems of indices were employed by Dirichlet in 1837 and 1863 and by Kronecker in 1870. Jacobi's Canon Arithmeticus of 1839 gives companion tables of indices for each prime and power of a prime < 1000. Cunningham's Binary Canon of 1900 gives the residues of the successive powers of 2 when divided by each prime or power of a prime < 1000 and companion tables showing the powers of 2 whose residues are 1, 2, 3,.... In 1846 Arndt proved that, if g is a primitive root of the odd prime p, g belongs to the exponent pn~*(p — 1) modulo pn if and only if (j=^p~1 — 1 is divisible by px, but not by px+1, where