Main Properties of Divisibility

MAIN PROPERTIES OF DIVISIBILITY Theorems of Fermat and Euler. Primitive Roots.-A posi tive integer, like 7, is called a prime if it has no factor except itself and 1. But 6= 2 X3 is composite. Two integers, like 8 and are called relatively prime if they have no common factor > I.

In 1640 Fermat stated

that, if p is any prime and if n is any integer not divisible by p, then is divisible by p. For example, = 8o is divisible by 5. The generalization by Euler in 176o states that if m is any positive integer, prime or composite, and if n is relatively prime to in, then - I is divisible by m. Here 4)(m) denotes the number of positive in tegers not exceeding m which are relatively prime to m. For ex ample, these are 1, 5, 7, and I I when m= 12, SO that and =624 is divisible by 12.

theorem shows that the linear equation nx± my

= c, in which n and m are relatively prime, has the integral solution x=cnk, y= ±cq, where k =4)(m) - I and q is the quotient of no(m) by m.

A

primitive root n of m is such that 4(m) is the least positive exponent e for which I is divisible by m. For example, 2 is a primitive root of 5, since is divisible by 5, while no one of 2 - I, I, I is divisible by 5. Again, 5 and 7 are primi tive roots of 9. There exist primitive roots of m if and only if m is 2, 4, pk, or where p is an odd prime.

Quadratic Residues. Law of Reciprocity.-When

the squares are divided by 7, the positive remainders < 7 are 1, 4, 2, which are called least quadratic residues of 7. Evi dently the squares of 5 = 7 - 6 = 7 - I have the same remainders as the squares of 3, 2, I. Likewise, • • • have the same remainders as • • • . Finally, the square of a multiple of 7 has the remainder zero, which is not counted as a quadratic residue. Hence when all squares relatively prime to 7 are divided by 7, the only remainders < 7 are I, 2, 4, which are therefore the only least quadratic residues of 7. The remaining positive integers 3, 5, 6 less than 7 are called the least' quadratic of 7. Then if t is any integer, 3+7t, 5+7t, and 6+ 7t are called non-residues of 7 while 1+71, 2+ 7t, and 4+ 7t are called residues of 7. Clearly the product of any two residues or of two non-residues is a residue, while the product of a residue by a non-residue is a non-residue.

The generalization from 7 to any m is immediate. If an integer r is relatively prime to m and if r differs from some square by a multiple of m, then r is a quadratic residue of m. But if is is

relatively prime to m and if there is no integer x such that is divisible by m, then a is a quadratic of m. If m= 15, we need only test the squares of 1, 2, 4, 7; their remainders i and 4 are the only least quadratic residues of 15. The remaining positive integers < 15 and relatively prime to 15 are 2, 7, 8, I 1, 13, 14 and give all the least non-residues of 15.

If p is a prime > 2, and if s is any integer not divisible by p, Legendre's symbol (s/p) is defined to have one of just two values, viz., + I when s is a quadratic residue of p, and — I when s is a non-residue. The earlier results give (2/7) = + I, (3/7) = —1. By use of the formulas (s/p) (t/p) = (st/P), ( = (— I) = ( I) the computation of any symbol (s/p) is evidently reduced to that of (//p) where 1 is an odd prime In case 1>p, we have / = ap+r, where o < rq, our former method applies to (p/q). All these prin ciples are illustrated in the following example: ( — = (— I/73) = +I, = +i, (ii/73)= (73/11) = (7/10= — (I i/7) = — (4/7) = — I.

Here it was necessary to know that 73, and 7 are all primes. The removal of the restriction to primes would obviously save much work. Partly for this reason, but mainly on account of its importance in many investigations, we shall discuss Jacobi's symbol.

Let P be a positive odd integer. If P= i, we take (s/ P)= (0) = +1.

But if • • • where pi, P2 are odd primes, not necessarily distinct, we define Jacobi's symbol to be (s/P) = (s/Pi) (s/P2) • • (s/Pr).

In case an even number of these factors is — 1, the symbol (s/P) is + I and yet s is a non-residue of P. While therefore Jacobi's symbol does not admit of the same interpretation as Legendre's, yet all the above formulas hold true, including the reciprocity law, provided p and q are now any relatively prime positive odd integers. If for we define (s/n) to be (s/P), we see that the reciprocity law holds also when just one of p and q is negative.