Hence the lowest value of k is rs itself, and the proof that ab belongs to rs is completed.

45. If r and s are not relatively prime, and if m denote their least common multiple, it can be proved in an analogous manner that a number belonging to m can be determined by means of a and b.

46. Theorem. To every divisor, d, of p-1, there belongs (mod. p) at least one number a.

Proof. (1) We take up first the case: d=qa, where q is a prime.

(xaa−1)(x−1)qa + x/−2\q2 + . . . +xa" +1)=0 (mod. p).

+.

(3)

But by Fermat's theorem the congruence (1) is satisfied. for every value of r except those =0 (mod. p). Accordingly the congruence (3) has the maximum number of roots. But since neither factor of the left member of (3) can be congruent zero for more roots than there are units in its degree, it follows that each factor is congruent zero for as many roots as there are units in its degree. In particular:

has q roots. Some of these will also satisfy congruences of this type and of lower degree. By sees. 41, 40, all such roots will satisfy x-1=0 (mod. p). But by what has just been proved this congruence has precisely q-1 roots. Hence (sec. 40), there are precisely q-qa-1 or q-1(g-1) roots of the congruence (4) that satisfy no congruence of lower degree. That is, there exist precisely qa-1(q-1) incongruent numbers belonging to the exponent qa (mod. p).

(2) Case, d any divisor of p-1.

Let d=qar3s . . ., where q, r, s are different primes. Then by (1), there exists a number, call it a, belonging to qo; and there exists a number, call it b, belonging to r3. Hence, by the theorem of sec. 44, ab belongs to qar3.

By (1) there exists a number, call it c, belonging to s. Since q and s are relatively prime, (ab)c belongs to qars. Continuing in this way, all the factors of d are used, and the existence of a number belonging to d is established.

Corollary. There exists at least one number, call it g, belonging to p-1.

47. Definition. If g belongs to the exponent p-1, then g is called a primitive root of the congruence

x-1=1 (mod. p),

or briefly, a primitive root of p.

48. Theorem. If g is a primitive root of p, the numbers g, g2, g3 . . . gp-1 are distinct (mod. p) and have the residues

But p-1>h-k≥1. Hence this result contradicts the hypothesis that g is a primitive root of p. Consequently, the p-1 powers, g, g2, ... g-1, all have different residues (mod. p), and therefore have the residues 1, 2, 3 . . . p-1 in some order. 49. Theorem. If g is a primitive root of p, and if k is prime to p-1, gk is a primitive root of p.

The lowest admissible value of h is therefore p-1; that is, gk belongs to the exponent p-1, and is hence a primitive root of p.

Corollary. There are (p-1) primitive roots of p.

50. The actual value of a primitive root may be found by trial, if the modulus is small.

That is, 2 belongs to the exponent 8, and is not a primitive root of 17. Nor can any of the residues obtained, 2, 4, 8, 16, 15 (= −2), 13, 9, 1, be primitive roots. For they are all of the form 2 and (2)8 or 28k is 1 (mod. p) since 28 is so. Hence all of these residues belong either to 8 or to a divisor of 8.

The smallest number not in the above list is 3. Trying 3 it is found to belong to the exponent 16; that is, 3 is a primitive root of 17.

It can also be proved without trial that 3 must be a primitive root. For, since (16)=8, 17 has 8 primitive roots. But there are 8 residues of 2k, none of which is a primitive root, consequently, each one of the 8 other non-zero residues must be a primitive root. In particular, 3 is a primitive root.

If the second trial likewise does not lead to a primitive root, the theorems above (secs. 44, 45) enable us to determine a number belonging to the least common multiple of the two exponents. If this least common multiple is p-1 itself, we have found a primitive root. If not, we have at least a number belonging to a much larger exponent, and all its powers are thus excluded from further consideration. In this way, systematic trial enables us to find a primitive root.

For large primes, the calculations may become laborious. Some general theorems are known as to primitive roots. For example: If a prime is of the form 22n +1, it has the primitive root 3.

If a prime p is of the form 8n+3, and if 4n+1 is also prime, p has the primitive root 2.*

*Tschebyscheff, Theorie der Congruenzen, Berlin, 1889, p. 306, et seq., where others are given and proved.

VI. QUADRATIC CONGRUENCES

51. The most general congruence of the second degree in one unknown is:

ax2+bx+c=0 (mod. m).

We simplify the form of this as follows: Multiply both members and the modulus by 4a,

4a2x2+4abx+4ac=0 (mod. 4am).

(The modulus is multiplied also, so that the inverse operation may always be possible);

(2ax+b)2 — b2+4ac=0 (mod. 4am).

or:

Putting

y=2ax+b (mod. 4am)

d=b2-4ac (mod. 4am)

the congruence becomes:

y2d (mod. 4am).

From the values of y, we find the values of x, by solution of the

different primes, any number that satisfies the congruence:

.pk, where P1, P2... P2 are

Conversely, the definition of a congruence shows that any number that satisfies each of the congruences (2), satisfies also congruence (1).

53. The solution of the general quadratic congruence is thus reduced to that of the type:

x2-a=0 (mod. p*),

where p is a prime.

Any solution of this congruence is also a solution of:

x2-a=0 (mod. p1),

and, in particular, of:

where h<k,

x2-a=0 (mod. p,.

(3)

We shall restrict further consideration to congruences of this type, and as preliminary example take the modulus 7. Forming the squares of the seven least positive residues (mod. 7) we have:

02=0 22=4 42=2 62=1 (mod. 7)

12=1 32=2 52=4

We see from this that the congruence

x2a (mod. 7)

has a solution if a =0, 1, 2, 4, but has no solution if a =3, 5, 6. The former numbers are residues of squares according to the modulus 7, or briefly quadratic residues of 7; the latter numbers are not such residues.

54. Definition. If the congruence x2=a (mod. p) admits a solution, the number a is called a quadratic residue of p: otherwise it is called a quadratic non-residue of p. When there is no danger of misinterpretation, the word "quadratic" is often omitted for brevity.

55. It can be proved without much difficulty that the product of two residues of p is also a residue; that the product of two non-residues is a residue; and that the product of a residue and a non-residue is a non-residue.

56. These results can be stated in the form of a single

equation by the use of the symbol

()

*

which is defined as

* Introduced by Legendre, and known as "Legendre's symbol."