PRIMITIVE ROOTS.

483

419. THEOREM.—Iƒ p, a number prime to a, divide the successive powers 1, a, a2, a3 . . . there will be one at least, before arriving at a', which will leave the remainder 1.

...

The remainders being each less than p, there can be but p-1 different ones, and, therefore, in the p first terms of the series 1, a, a2, a3 . . . a3−1, there are at least two which will give the same remainder. Representing them by am, am, and their common remainder by r, suppose

a=Ep+r, amE'p+r..

....

(1)

.. aTM'—aTM=(E'—E)p, or aTM(aTM'——1)=(E'—E)p;

and, as p is prime to a, it must divide am-1. Therefore we have unity for remainder in dividing by p the power amm, which is <a3. Q. E. D. 420. Let a designate the lowest power other than ao, which gives the remainder 1. All the preceding remainders are unequal. For, if for two powers, am, am' less than a", we could have the equalities (1), we might conclude, as just now, that am-m would give the remainder 1. Consequently, a" would not be the lowest power to which this property belonged.

THEOREM OF FERMAT.

421. If p be a prime number which will not divide a, the division of ao-1 by p will give 1 for a remainder. In other words, ap-1-1 is exactly divisible by p.

It must be carefully observed that p is an absolute prime number, and not simply prime to a.

Call q, q', q', . . ., and r, r', r', . . . the quotients and remainders of the p-1 quantities a, 2a, 3a (p-1)a, divided by p. If we multiply these quantities, and suppose E to be an entire number, we have

...

a. 2a. 3a.... (p-1)a=(qp+r)(q'p+r')(q′′p+r")...

The first member is equal to

1.2.3

and, as the remainders r, r', r'' rr'r''... must evidently be that of . (p-1), from 1 to (p-1).

3

=E+rr'r''

....

...

(p-1)ap-1

are all different (Art. 415), the product the whole series of natural numbers, 1, 2, Hence the above equality becomes

(p-1) a1Ep+1.2 3

(p—1)(aP-1—1)=Ep.

The 1° member of this equality is, therefore, divisible by p; but since p is a prime number, it can not divide any of the factors 1.2.3 must, therefore, divide aP-1—1.

...

(p-1); it Q. E. D.

Suppose that we take for p only prime numbers; if we wish that the powers ao, a1 . . . ap-1 should give for remainders all the numbers inferior to p, it is necessary to choose a, such that ao1 should be the lowest power above ao, which gives the remainder 1; and if, among those which fulfill this condition, we take for a only numbers below p, we have those which Euler calls primitive roots.

For the best method of calculating them, the student is referred to the article by Mr. Ivory, in the fourth volume of Supplement to Encyclopedia Britannica. We shall limit ourselves to setting down here the primitive roots of numbers as far as 37.

23

5

7

29

31

37

10. 13. 14. 15

10. 11. 13 14. 15. 17.20.21

2. 3 8.10.11 14. 15. 18. 19. 21. 26. 27

3.11. 12. 13. 17. 21. 22. 24

2.5 13. 15. 17. 18. 19. 20. 22. 24. 32. 35

THE FORMS OF SQUARE NUMBERS.

422. Every square number is of one of the forms 4n or 4n+1.

Every number is either even or odd; that is, every number is of one of the forms 2n or 2n+1; and, consequently, every square is of one of the forms 4n4n,

4n+4n+14n+1.

DEDUCTIONS.

(1) Every even square number is divisible by 4.

(2) Since every odd square by the above is of the form 4(n2+n)+1, and since n2+n is necessarily even, it follows that every odd square is of the form 8n+1; and, consequently, no number of the forms 8n+3, 8n+5, 8n+7 can be a square number.

(3) The sum of two odd squares can not be a square; for

(8n+1)+(8n+1)±4n+2,

which is an impossible form.

423. Every square number is of one of the forms 5n or 5n1. For all numbers, compared by the modulus 5, are of one of the forms

25n°10n+15n+1,

25n+20n+45n+4 or 5n-1.

Therefore all squares are of one of the forms 5n or 5n1.

DEDUCTIONS.

(1) If a square number be divisible by 5, it is also divisible by 25; and if a number be divisible by 5 and not by 25, it is not a square.

(2) No number of the form 5n+2 or 5n+3 is a square number.

(3) If the sum of two squares be a square, one of the three is divisible by 5, and, consequently, also by 25; for all the possible combinations of the three forms 5n, 5n+1, and 5n-1 are as follows:

Now, of these six forms, the latter four have one of the squares divisible by 5, and, therefore, also by 25. And the first two are each impossible forms for square numbers; that is, neither of these two combinations can produce squares; therefore, if the sum of two squares be a square, one of the three squares is divisible by 25.

(4) In a similar way, it may be shown that all square numbers compared by modulus 10 are of one of the forms

10n, 10n+5, 10n+1, 10n+6, 10n+4, or 10n+9. Therefore, all square numbers terminate with one of the digits 0, 1, 4, 5, 6, or 9; and hence, again, no number terminating with 2, 3, 7, or 8 can be a square number.

(5) By examining, in like manner, the forms of squares to modulus 100, we may deduce the following properties :

(6) A square number can not terminate with an odd number of ciphers. (7) If a square number terminate with a 4, the last figure but one must be

even.

(8) If a square number terminate with a 5, it must terminate with 25.

(9) If the last digit of a square be odd, the last digit but one must be even; and if it terminate with any even digit except 4, the last but one must be odd. (10) A square number can not terminate with more than three equal digits, unless they are 0's; nor can it terminate with three, unless they are 4's. 424. All square numbers are of the same form with regard to any modulus, a, as the squares

For every number may be represented by the formula an±r, in which r shall never exceed ja.

where it is obvious that r2 and (an+r)2 will leave the same remainder when divided by a; therefore, (an+r)2 and r2 will be of the same form compared by modulus a; but r never exceeds a, therefore all numbers compared by modulus a are of the same forms as

Therefore, all square numbers are of the same form to modulus 4a as the

02, 1o, 2o, 3o, &c., a2;

of the same forms as the squares

squares

and hence we see immediately that all square numbers to modulus 8 must be

that is, they are all of the form

02, 12, 22

8n, 8n+1, 8n+4,

as we have already demonstrated.

(2) The following tables exhibit the possible and impossible forms of square numbers for all moduli from 2 to 10.

425. THE name continued fraction is given to an expression of the form

i. e., a fraction whose denominator is a whole number and a fraction, and which latter fraction has also for its denominator a whole number plus a fraction, and so on.

An expression whose numerators and denominators are any quantities whatever, may have the form of a continued fraction; but continued fractions, of which the numerators are 1 and the denominators whole positive numbers, are the kind which most usually occur.

These expressions arise in various ways, and are of great use in finding the approximate values of fractions and ratios that are expressed in large numbers. as well as in the resolution of certain unlimited problems of the first and second degrees; in the latter of which the answer can not be easily obtained in whole numbers by any other method.

a

Thus, in order to represent the irreducible fraction or ratio

b

by a continued

fraction, let b be contained in a, p times with a remainder c; also, let c be contained in b, q times with a remainder d, and so on, according to the following scheme :

C

p, q, r, &c., are called partial quotients, and p+ 4+, &c., complete quotients.

By taking the reciprocals of the second, third, &c., of the above equations, we have

Whence, by extending the number of terms and generalizing the formula, we shall have

according as the numerator is greater or less than the denominator; for in the latter case we should invert the first as well as the second, third, &c., equations. To convert a given irreducible fraction into a continued one, we have the following

RULE.

Divide the greater of the two terms of the fraction by the less, and the last divisor continually by the last remainder, till nothing remains, as in finding their greatest common measure; then the successive quotients thus found will be the denominators of the several terms of the continued fraction, the numerators of which are always 1.