Then a ˢ ÷ b gives the same remainder as s a ÷ b , which ( Prop. 4 ) cannot be either r or s , unless s be 1: let it be t . Then a ᵗ ÷ b gives the same remainder as ta ÷ b ; if t be not 1, this cannot be either r , s , or t : let it be u . So we go on getting different remainders, until 1 occurs as a remainder; after which, at the next step, the remainder of a ÷ b is repeated. Now, 1 must come at last; for division by b cannot give any remainders but 0, 1, 2, ... b - 1; and 0 never arrives ( Prop. 3 ), so that as soon as b -2 different remainders have occurred, no one of which is unity, the next, which must be different from all that precede, must be 1. If not before, then at a ᵇ⁻¹ we must have a remainder 1; after which the cycle will obviously be repeated.
Thus, 7, 7², 7³, 7⁴, &c. will, when divided by 5, be found to give the remainders 2, 4, 3, 1, &c.
Prop. 6. The difference of two mth powers is always divisible without remainder by the difference of the roots; or aᵐ -bᵐ is divisible by a-b; for
aᵐ - bᵐ = aᵐ - aᵐ⁻¹b + aᵐ⁻¹b - bᵐ
= aᵐ⁻¹(a - b) + b(aᵐ⁻¹ - bᵐ⁻¹)
From which, if aᵐ⁻¹-bᵐ⁻¹ is divisible by a - b, so is aᵐ-bᵐ. But a - b is divisible by a - b; so therefore is a²- b²; so therefore is a³-b³; and so on.
Therefore, if a and b, divided by c, leave the same remainder, a² and b², a³ and b³, &c. severally divided by c, leave the same remainders; for this means that a - b is divisible by c. But aᵐ - bᵐ is divisible by a - b, and therefore by every measure of a-b, or by c; but aᵐ - bᵐ cannot be divisible by c, unless aᵐ and bᵐ, severally divided by c, give the same remainder.
Prop. 7. If b be a prime number, and a be not divisible by b, then aᵇ and (a-1)ᵇ + 1 leave the same remainder when divided by b. This proposition cannot be proved here, as it requires a little more of algebra than the reader of this work possesses.4
Prop. 8. In the last case, aᵇ⁻¹ divided by b leaves a remainder 1. From the last, aᵇ-a leaves the same remainder as (a-1)ᵇ + 1-a or (a-1)ᵇ- (a-1); that is, the remainder of aᵇ - a is not altered if a be reduced by a unit. By the same rule, it may be reduced another unit, and so on, still without any alteration of the remainder. At last it becomes 1ᵇ-1, or 0, the remainder of which is 0. Accordingly, aᵇ - a, which is a(aᵇ⁻¹- 1), is divisible by b; and since b is prime to a, it must (Prop. 2) divide aᵇ⁻¹-1; that is, aᵇ⁻¹, divided by b, leaves a remainder 1, if b be a prime number and a be not divisible by b.
From the above it appears (Prop. 5 and 7), that if a be prime to b, the set 1, a, a², a³, &c. successively divided by b, give a set of remainders beginning with 1, and in which 1 occurs again at aᵇ⁻¹, if not before, and at aᵇ⁻¹ certainly (whether before or not), if b be a prime number. From the point at which 1 occurs, the cycle of remainders recommences, and 1 is always the beginning of a cycle. If, then, aᵐ be the first power which gives 1 for remainder, m must either be b-1, or a measure of it, when b is a prime number.
But if we divide the terms of the series m , ma , ma ², ma ³, &c. by b , m being less than b , we have cycles of remainders beginning with m . If 1, r , s , t , &c. be the first set of remainders, then the second set is the set of remainders arising from m , mr , ms , mt , &c. If 1 never occur in the first set before a ᵇ⁻¹ (except at the beginning), then all the numbers under b -1 inclusive are found among the set 1, r , s , t , &c.; and if m be prime to b ( Prop. 4 ), all the same numbers are found, in a different order, among the remainders of m , mr , &c. But