Page:EB1911 - Volume 19.djvu/883

particular power, independently of the arrangement of their elements, it is analogous to the integers, 1, 2, 3, &c, when used to denote powers of finite aggregates; for this reason it is called the least transfinite cardinal number.

22. There are aggregates which have a power greater than 𝑎: for instance, the arithmetical continuum of positive real numbers, the power of which is denoted by 𝑐. Another one is the aggregate of all those order-types which (like those in II. above) are the indices of aggregates of power 𝑎. The power of this aggregate is denoted by ^א₁. According to Cantor’s theory it is the transfinite cardinal number next superior to 𝑎, which for the sake of uniformity is also denoted by ^א₀. It has been conjectured that ^א₁＝𝑐, but this has neither been verified nor disproved The discussion of the aleph-numbers is still in a controversial stage (November 1907) and the points in debate cannot be entered upon here.

23. Transfinite numbers, both ordinal and cardinal, may be combined by operations which are so far analogous to those of ordinary arithmetic that it is convenient to denote them by the same symbols. But the laws of operation are not entirely the same; for instance, 2ω and ω2 have different meanings: the first has been explained, the second is the index of the scheme (𝑎₁𝑏₁ | 𝑎₂𝑏₂ | 𝑎₃𝑏₃ | . . . | 𝑎_𝑛𝑏_𝑛 | . . . ) or any similar arrangement. Again if 𝑛 is any positive integer, 𝑛𝑎＝𝑎^𝑛＝𝑎. It should also be observed that according to Cantor’s principles of construction every ordinal number is succeeded by a definite next one; but that there are definite ordinal numbers (e.g. ω, ω²) which have no ordinal immediately preceding them.

24. Theory of Numbers.—The theory of numbers is that branch of mathematics which deals with the properties of the natural numbers. As Dirichlet observed long ago, the whole of the subject would be coextensive with mathematical analysis in general; but it is convenient to restrict it to certain fields where the appropriateness of the above definition is fairly obvious. Even so, the domain of the subject is becoming more and more comprehensive, as the methods of analysis become more systematic and more exact.

The first noteworthy classification of the natural numbers is into those which are prime and those which are composite. A prime number is one which is not exactly divisible by any number except itself and 1; all others are composite. The number of primes is infinite (Eucl. Elem. ix. 20), and consequently, if 𝑛 is an assigned number, however large, there is an infinite number (𝑎) of primes greater than 𝑛.

If 𝑚, 𝑛 are any two numbers, and 𝑚>𝑛, we can always find a definite chain of positive integers (𝑞₁, 𝑟₁), (𝑞₂, 𝑟₂), &c., such that

𝑚＝𝑞₁𝑛+𝑟₁, 𝑛＝𝑞₂𝑟₁+𝑟₂, 𝑟₁＝𝑞₃𝑟₂+𝑟₃, &c.

with 𝑛>𝑟₁>𝑟₂>𝑟₃ . . .; the process by which they are calculated will be called residuation. Since there is only a finite number of positive integers less than 𝑛, the process must terminate with two equalities of the form

𝑟_ℎ−2＝𝑞_ℎ𝑟_ℎ−1+𝑟_ℎ,  𝑟_ℎ−1＝𝑞_ℎ+1𝑟_ℎ.

Hence we infer successively that 𝑟_ℎ is a divisor of 𝑟_ℎ−1, 𝑟_ℎ−2, . . . 𝑟₁, and finally of 𝑚 and 𝑛. Also 𝑟_ℎ is the greatest common factor of 𝑚, 𝑛: because any common factor must divide 𝑟₁, 𝑟₂, and so on down to 𝑟_ℎ: and the highest factor of 𝑟_ℎ is 𝑟_ℎ itself. It will be convenient to write 𝑟_ℎ＝dv (𝑚, 𝑛). If 𝑟_ℎ ＝ 1, the numbers 𝑚, 𝑛 are said to be prime to each other, or co-primes.

25. The foregoing theorem of residuation is of the greatest importance; with the help of it we can prove three other fundamental propositions, namely:—

(1) If 𝑚, 𝑛 are any two natural numbers, we can always find two other natural numbers 𝑥, 𝑦 such that

dv(𝑚,𝑛)＝𝑥𝑚−𝑦𝑛.

(2) If 𝑚, 𝑛 are prime to each other, and 𝑝 is a prime factor of 𝑚𝑛, then 𝑝 must be a factor of either 𝑚 or 𝑛.

(3) Every number may be uniquely expressed as a product of prime factors.

Hence if 𝑛＝𝑝^α𝑞^β𝑟^γ . . . is the representation of any number 𝑛 as the product of powers of different primes, the divisors of 𝑛 are the terms of the product (1+𝑝+𝑝²+ . . . +𝑝^α) (1+𝑞+ . . . +𝑞^β) (1+𝑟 . . . +𝑟^γ) their number is (α+1) (β+1) (𝛾+1) . . .; and their sum is Π(𝑝^α+1−1)÷Π(𝑝−1). This includes 1 and 𝑛 among the divisors of 𝑛.

26. Totients.—By the totient of 𝑛, which is denoted, after Euler, by φ(𝑛), we mean the number of integers prime to 𝑛, and not exceeding 𝑛. If 𝑛＝𝑝^α, the numbers not exceeding 𝑛 and not prime to it are 𝑝, 2𝑝, . . . (𝑝^α−𝑝), 𝑝^α of which the number is 𝑝^α−1: hence φ(𝑝^α)＝𝑝^α−𝑝^α−1. If 𝑚, 𝑛 are prime to each other, φ(𝑚𝑛)＝φ(𝑚)φ(𝑛); and hence for the general case, if 𝑛＝𝑝^α𝑞^β𝑟^γ . . . ,φ(𝑛)＝Π𝑝^α−1(𝑝−1), where the product applies to all the different prime factors of 𝑛. If 𝑑₁, 𝑑₂, &c., are the different divisors of 𝑛,

φ(𝑑₁)+φ(𝑑₂)+ . . . ＝𝑛.

For example 15＝φ(15)+φ(5)+φ(3)+φ(1)＝8+4+2+1.

27. Residues and congruences.—It will now be convenient to include in the term “number” both zero and negative integers. Two numbers 𝑎, 𝑏 are said to be congruent with respect to the modulus 𝑚, when (𝑎−𝑏) is divisible by 𝑚. This is expressed by the notation 𝑎≡𝑏 (mod 𝑚), which was invented by Gauss. The fundamental theorems relating to congruences are

If	𝑎≡𝑏 and 𝑐≡𝑑 (mod 𝑚), then 𝑎±𝑐≡𝑏±𝑑, and 𝑎𝑏 ≡𝑐𝑑.
If	ℎ𝑎≡ℎ𝑏(mod 𝑚) then 𝑎≡𝑏 (mod 𝑚/𝑑), where 𝑑＝dv(ℎ, 𝑚).

Thus the theory of congruences is very nearly, but not quite, similar to that of algebraic equations. With respect to a given modulus 𝑚 the scale of relative integers may be distributed into 𝑚 classes, any two elements of each class being congruent with respect to 𝑚. Among these will be φ(𝑚) classes containing numbers prime to 𝑚. By taking any one number from each class we obtain a complete system of residues to the modulus 𝑚. Supposing (as we shall always do) that 𝑚 is positive, the numbers 0, 1, 2, . . . (𝑚−1) form a system of least positive residues; according as 𝑚 is odd or even, 0, ±1, ±2, . . . ±⁠1/2⁠ (𝑚−1), or 0, ±1, ±2, . . . ±⁠1/2⁠(𝑚−2),⁠1/2⁠𝑚 form a system of absolutely least residues.

28. The Theorems of Fermat and Wilson.—Let 𝑟₁, 𝑟₂, . . . 𝑟_𝑡 where 𝑡＝φ(𝑚), be a complete set of residues prime to the modulus 𝑚. Then if 𝑥 is any number prime to 𝑚, the residues 𝑥𝑟₁, 𝑥𝑟₂, . . . 𝑥𝑟_𝑡 also form a complete set prime to 𝑚 (§ 27). Consequently 𝑥𝑟₁·𝑥𝑟₂ . . . 𝑥𝑟_𝑡≡𝑟₁𝑟₂ . . .𝑟_𝑡, and dividing by 𝑟₁𝑟₂ . . . 𝑟_𝑡, which is prime to the modulus, we infer that

𝑥^φ(^𝑚)≡1(mod 𝑚).

which is the general statement of Fermat’s theorem. If 𝑚 is a prime 𝑝, it becomes 𝑥^𝑝−1≡1 (mod 𝑝).

For a prime modulus 𝑝 there will be among the set 𝑥, 2𝑥, 3𝑥, . . . (𝑝−1)𝑥 just one and no more that is congruent to 1: let this be 𝑥𝑦. If 𝑦≡𝑥, we must have 𝑥²−1＝(𝑥−1) (𝑥+1)≡0, and hence 𝑥≡±1: consequently the residues 2, 3, 4, . . . (𝑝−2) can be arranged in ⁠1/2⁠ (𝑝−3) pairs (𝑥, 𝑦) such that 𝑥𝑦≡1. Multiplying them all together, we conclude that 2.3.4. . . .(𝑝−2)≡1 and hence, since 1.(𝑝−1)≡−1,

(𝑝−1)!≡−1 (mod 𝑝).

which is Wilson’s theorem. It may be generalized, like that of Fermat, but the result is not very interesting. If 𝑚 is composite (𝑚−1)!+1 cannot be a multiple of 𝑚: because 𝑚 will have a prime factor 𝑝 which is less than 𝑚, so that (𝑚−1)!≡0 (mod 𝑝). Hence Wilson’s theorem is invertible: but it does not supply any practical test to decide whether a given number is prime.

29. Exponents, Primitive Roots, Indices.—Let 𝑝 denote an odd prime, and 𝑥 any number prime to 𝑝. Among the powers 𝑥, 𝑥², 𝑥³, . . . 𝑥^𝑝−1 there is certainly one, namely 𝑥^𝑝−1, which ≡1 (mod 𝑝); let 𝑥^𝑒 be the lowest power of 𝑥 such that 𝑥^𝑒≡1. Then 𝑒 is said to be the exponent to which 𝑥 appertains (mod 𝑝): it is always a factor of (𝑝−1) and can only be 1 when 𝑥≡1. The residues 𝑥 for which 𝑒＝𝑝−1 are said to be primitive roots of 𝑝. They always exist, their number is φ(𝑝−1), and they can be found by a methodical, though tedious, process of exhaustion. If 𝑔 is any one of them, the complete set may be represented by 𝑔, 𝑔^𝑎, 𝑔^𝑏, . . . &c. where 𝑎, 𝑏, &c., are the numbers less than (𝑝−1) and prime to it, other than 1. Every number 𝑥 which is prime to 𝑝 is congruent, mod 𝑝, to 𝑔^𝑖, where 𝑖 is one of the numbers 1, 2, 3, . . . (𝑝−1); this number 𝑖 is called the index of 𝑥 to the base 𝑔. Indices are analogous to logarithms: thus

ind_𝑔 (𝑥𝑦)≡ind_𝑔 𝑥 + ind_𝑔 𝑦, ind_𝑔 (𝑥^ℎ)≡ ℎ ind_𝑔 𝑥 (mod p − 1).

Consequently tables of primitive roots and indices for different primes are of great value for arithmetical purposes. Jacobi’s Canon Arithmeticus gives a primitive root, and a table of numbers and indices for all primes less than 1000.

For moduli of the forms 2𝑝, 𝑝^𝑚, 2𝑝^𝑚 there is an analogous theory (and also for 2 and 4); but for a composite modulus of other forms there are no primitive roots, and the nearest analogy is the representation of prime residues in the form α^𝑥 β^𝑦 χ^𝑧 . . . , where α, β, γ are selected prime residues, and 𝑥, 𝑦, 𝑧, . . . are indices of restricted range. For instance, all residues prime to 48 can be exhibited in the form 5^𝑥 7^𝑦 13^𝑧, where 𝑥＝0, 1, 2, 3; 𝑦＝0, 1; 𝑧＝0, 1; the total number of distinct residues being 4.2.2＝16＝φ(48), as it should be.

30. Linear Congruences.—The congruence 𝑎′𝑥≡𝑏′ (mod 𝑚′) has no solution unless dv(𝑎′, 𝑚′) is a factor of 𝑏′. If this condition is satisfied, we may replace the given congruence by the equivalent one 𝑎𝑥≡𝑏 (mod 𝑚), where 𝑎 is prime to 𝑏 as well as to 𝑚. By residuation (§§ 24, 25) we can find integers ℎ, 𝑘 such that 𝑎ℎ−𝑚𝑘＝1, and thence obtain 𝑥≡𝑏ℎ (mod 𝑚) as the complete solution of the given congruence. To the modulus 𝑚′ there are 𝑚′/𝑚 incongruent solutions. For example, 12𝑥≡30 (mod 21) reduces to 2𝑥≡5 (mod 7) whence 𝑥≡6 (mod 7)≡6, 13, 20 (mod 21). There is a theory of simultaneous