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 az for instance, the arithmetical continuum of positive real numbers, the power of which is denoted by c. Another one is the aggregate of all those order-types which (like those in II. above) are the indices of aggregates of power a. The power of this aggregate is denoted by “L According to Cantor's theory it is the transfinite cardinal number next superior to a, which for the sake of uniformity is also denoted by No. It has been conjectured that *', =c, 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, 2w and co2 have different meanings: the first has been explained, the second is the index of the scheme (aibi l agbz I asbg | I a, b, ,| )or any similar arrangement. Again if n is any positive integer, na=a"=a 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 dehnite ordinal numbers (e.g w, wf) 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 I; all others are composite. The number of primes is infinite (Eucl Elem. ix. 20), and consequently, if n is an assigned number, however large, there is an infinite number (a) of primes greater than n.

If m, n are any two numbers, and m> n, we can always find a definite chain of positive integers (gl, ri), (gg, rg), &c, such that m=q1n+r1, n=g2r1-1-rg, r1=g3r2'+r3, &c

with n>r1>r2>r3 .; the process by which the are calculated will be called residuation Since there is only a finite number of positiye integers less than rt, the process must terminate with two equalities of the form

Th-2 = qm» 1 +fh, fb-1 = Qh-s-xfn.

Hence we infer successively that 11. is a divisor of Th.-1» fh-21. .r1, and finally of m and n. Also ri is the greatest common factor of m, nz because any common factor must divide rl, rg, and so on down to nf: and the highest factor of rn is rn itself. It will be convenient to write f1»=dV (rn, 1t). If rr = I, the numbers m, n are said to be prime to each other, or co-primes.

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

(I) If m, n are any two natural numbers, we can always find two other natural numbers x, y such that

dv(m, n) =xm -yn.

(2) If m, n are prime to each other, and p is a prime factor of mn, then p must be a factor of either m or n.

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

Hence if n=p“g5r'Y is the representation of any numbern as the product of powers of different primes, the divisors of n are the terms of the product

<I+1>+1>“+ -, +1>“> (1+q+ ~ +49 <1-H+ . . . +fv) -their number 15 (fl-l-I) (B+I) (~/+I) .; and their sum is Il(p“+'-l) + II(p- I). This includes I and n among the divisors of n.

26. Totients.—By the totient of n, which is denoted, after Euler, by ¢(n), we mean the number of integers prime to n, and not exceeding n. If n=p¢, the numbers not exceeding n and not prime to it are p, zp, (pe-p), ps of which the number is p¢'1; hence ¢(P“) = p“-p“'1 If m, n are prime to each other, 4>(rnn) =4>(rn)4>(n); and hence for the general case, if n=p“g3rY ,4>(n)=lIp'1“1(p-1), where the product applies to all the different prime factors of n. If di, dz, &c., are the different divisors of n, ~ ¢(lli)+d>(d2)+ - . . =rl.

For ¢XamPl€» 15 =¢(1s>+¢><5)+q><.s>+<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 a, b are said to be congruent with respect to the modulus rn, when (a-b) is divisible by m. This is expressed by the notation aab (mod rn), which was invented by Gauss. The fundamental theorems relating to congruences are

If a-Eb and csd (mod m), then a=*=cEb=1=d, and abEcd If haEhb(mod rn) then aab (mod rn/d), where d=dv(h, m). Thus the theory of congruences is very nearly, but not quite, similar to that of algebraic equations. With respect to a given modulus in the scale of relative integers may be distributed into rn classes, any two elements of each class being congruent with respect to m. Among these will be d>(m) classes containing numbers prime to m. By taking any one number from each class we obtain a complete system of residues to the modulus m. Supposing (as we shall always do) that m is positive, the numbers 0, I, 2, (m-I) form a system of least positive residues; according as rn is odd or even, 0, =*=I, ='=2, is (m-1), or o, =f=1, =2, . =sé(m-2), § m form a system of absolutely least residues.

28. The Theorems of Fermat and Wilson.—Let ri, rg, rf where t=d>(m), be a complete set of residues prime to the modulus rn. Then if x is any number prime to rn, the residues xrl, xrg, xn also form a complete set prime to m (§ 27). Consequently xryxrz xr, § r, r, r, , and dividing by r1r2 ri, which is prime to the modulus, we infer that

x¢( ') E I (mod rn).

which is the general statement of Fermat's theorem. If rn is a prime p, it becomes xf"'§ r (mod p).

For a prime modulus p there will be among the set x, 2x, x, (p-1)x just one and no more that is congruent to I: let tlliis be xy. Ifysx, wemusthavex'-I = (x-I) (x+1)Eo, and hencexs *IZ consequently the residues 2, 3, 4, (p-2) can be arranged in % (p-3) pairs (x, y) such that xysr. Multiplying them all together, we conclude that 2.3.4. (p-2) EI and hence, since I (p- I)-E - I, (P"1)!E-I(f110d P).

which is Wilson's theorem. It may be generalized, like that of Fermat, but the result is not very interesting. If in is composite (m- 1) !+I cannot be a multiple of m: because rn will have a prime factor p which is less than m, so that (m-I)!Eo (mod p). 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 p denote an odd prime, and x any number prime to p. Among the powers x, xl, x', xp" there is certainly one, namely x1"1, which EI (mod p); let x” be the lowest power of x such that x”EI. Then e is said to be the exponent to which x appertains (mod p): it is always a factor of (p-I) and can only be I when scsi. The residues x for which e =p- I are said to be primitive roots of p. They always exist, their number is 4>(p-1), and they can be found by a. methodical, though tedious, process of exhaustion. If g is any one of them, the complete set may be represented by g, g", gb, &c where a, b, &c, are the numbers less than (p-I) and prime to it, other than I. Every number x which is prime to p is congruent, mod p, to gi, where i is one of the numbers I, 2, 3, (p-I); this number i is called the index of x to the base g. Indices are analogous to logarithms: thus

ind, (xy)Eind, x+ind, , y. ind, ,(x )Eh indgx (mod p-I). 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 2p, p'", 2p"' 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 a' B” X' ~, where a, B, 7, are selected prime residues, and x, y, z, are indices of restricted range. For instance, all residues prime to 48 can be exhibited in the form 5” 7” I3', where x=o, I, 2, 3; y=o, 1; z=o, 1; the total number of distinct residues being 4.2.2 = 16 =¢(48), as it should be.

30. Linear Congruences.—The congruence a'xEb' (mod m') has no solution unless dv(a', m') is a factor of b'. If this condition is satisfied, we may replace the given congruence by the equivalent one axab (mod rn), where a is prime to b as well' as to rn. By residuation (§§ 24, 25) we can find integers h, k such that ah-mk = 1, and thence obtain xsbh (mod m) as the complete solution of the given congruence. To the modulus rn' there are m'/m in congruent solutions. For example, I2xE30 (mod 21) reduces to 2x55 (mod 7) whence x56 (mod 7) 56, 13, 20 ~(mod 21). There is a theory of simultaneous