Let a + b give the remainder r (not unity); then a² ÷ b gives the same remainder as ra + b, which ([Prop. 4]) cannot be r: let it be s. Then aˢ ÷ b gives the same remainder as sa ÷ 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.[64]
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.