124 SPECIAL TOPICS IN THEORETICAL ARITHMETIC

First there are evidently the same number of numbers,
namely m — 1, in the two sets.

Next each number of the first set is congruent (mod m) to
some one, and only one, of the numbers
0,1,2,3, -, m — 1. § 285.

And none of them is congruent to 0. § 297.

Therfor each of them is congruent to some one, and only
one, of the numbers 1, 2, 3, -+, m — 1.

Now no number in the second set can have congruent to it
two numbers of the first set, as then these two numbers would
be congruent to each other, which is impossible by § 297.

But each number of the second set must have congruent to
it some number in the first set.

For otherwise, since the sets have the same number of num-
bers, and each number of the first set is congruent to some
number in the second set, two of the first set would be con-
gruent to the same number in the second set, which we have
seen to be impossible.

We may write the theorem symbolically as follows:

a 1
2a 2

Ifall m > 1, then 3ar = 3 (mod m)
(m—l)c'z (m—i_)

Ex. 1. Ex. 2. Ex. 3.
4117 >1 w1t 61 —-3]1l4>1
1X4=4(mod7) 1X5=5(mod6) 1(—3) =1 (mod4)
2X4=1 2X5=4 2(—3)=2
3IX4=5 3X5=3 3(—3)=3

4 X4=2 4X5=2
5X4=6 5X5=1
6X4=3

299. Th. Ifa |l m > 1, if the natural series of integers are
multiplied by a, the results, taken in order, may be divided into