Elements of arithmetic

Prop. 1. If a fraction be reduced to its lowest terms, so called,[61] that is, if neither, numerator nor denominator be divisible by any integer greater than unity, then no fraction of a smaller numerator and denominator can have the same value.

Let a/b be a fraction in which a and b have no common measure greater than unity: and, if possible, let c/d be a fraction of the same value, c being less than a, and d less than b. Now, since

let m be the integer quotient of these last fractions (which must exist, since a > c, b > d), and let e and f be the remainders. Then

Hence,

instead of being equal to the former. Hence,

so that if a fraction whose numerator and denominator have no common measure greater than unity, be equal to a fraction of lower numerator and denominator, it is equal to another in which the numerator and denominator are still lower. If we proceed with

and so on. Now, if there be any process which perpetually diminishes the terms of a fraction by one or more units at every step, it must at last bring either the numerator or denominator, or both, to 0. Let

be one of the steps, and let a = kv + x, b = kw + y; so that

Now, if x = 0 but not y, this is absurd, for it gives

A similar absurdity follows if y be 0, but not x; and if both x and y be = 0, then a = kv, b = kw, or a and b have a common measure, k. Now k must be greater than 1, for v and w are less than c and d, which by hypothesis are less than a and b. Consequently a and b have a common measure k greater than 1, which by hypothesis they have not. If, then, a and b be integers not divisible by any integer greater than 1, the fraction a/b is really in its lowest terms. Also a and b are said to be prime to one another.

Prop. 2. If the product ab be divisible by c, and if c be prime to b, it must divide a. Let

Now b/c is in its lowest terms; therefore, by the last proposition, d and a must have a common measure. Let the greatest common measure be k, and let a = kl, d = km. Then

is also in its lowest terms; but so is b/c; therefore we must have m = b, l = c, for otherwise a fraction in its lowest terms would be equal to another of lower terms. Therefore a = kc, or a is divisible by c. And from this it follows, that if a number be prime to two others, it is prime to their product. Let a be prime to b and c, then no measure of a can measure either b or c, and no such measure can measure the product bc; for any measure of bc which is prime to one must measure the other.

Prop. 3. If a be prime to b, it is prime to all the powers of b. Every measure[62] of a is prime to b, and therefore does not divide b. Hence, by the last, no measure of a divides b²; hence, a is prime to b², and so is every measure of it; therefore, no measure of a divides bb², consequently a is prime to b³, and so on.

Hence, if a be prime to b, a cannot divide without remainder any power of b. This is the reason why no fraction can be made into a decimal unless its denominator be measured by no prime[63] numbers except 2 and 5. For if

which last is the general form of a decimal fraction, let

is an integer, whence (Prop. 2) b must divide 10ⁿ, and so must all the divisors of b. If, then, among the divisors of b there be any prime numbers except 2 and 5, we have a prime number (which is of course a number prime to 10) not dividing 10, but dividing one of its powers, which is absurd.

Prop. 4. If b be prime to a, all the multiples of b, as b, 2b, ... up to (a-1)b must leave different remainders when divided by a. For if, m being greater than n, and both less than a, we have mb and nb giving the same remainder, it follows that mb-nb, or (m-n)b, is divisible by a; whence (Prop. 2), a divides m-n, a number less than itself, which is absurd.

If a number be divided into its prime factors, or reduced to a product of prime numbers only (as in 360 = 2 × 2 × 2 × 3 × 3 × 5), and if a, b, c, &c. be the prime factors, and α, β, γ, &c. the number of times they severally enter, so that the number is a^α × bᵝ × cᵞ × &c., then this can be done in only one way: For any prime number v, not included in the above list, is prime to a, and therefore to a^α, to b and therefore to bᵝ and therefore to a^α × bᵝ Proceeding in this way, we prove that v is prime to the complete product above, or to the given number itself.

The number of divisors which the preceding number a^αbᵝcᵞ ... can have, 0 and itself included, is (α + 1)(β+ 1)(γ + 1).... For a^α as the divisors 1, a, a² ... a^α and no others, α + 1 in all. Similarly, bᵝ has β+ 1 divisors, and so on. Now as all the divisors are made by multiplying together one out of each set, their number (page 202) is (α + 1)(β + 1)(γ+ 1)....

If a number, n, be divisible by certain prime numbers, say 3, 5, 7, 11, then the third part of all the numbers up to n is divisible by 3, the fifth part by 5, and so on. But more than this: when the multiples of 3 are omitted, exactly the fifth part of those which remain are divisible by 5; for the fifth part of the whole are divisible by 5, and the fifth part of those which are removed are divisible by 5, therefore the fifth part of those which are left are divisible by 5. Again, because the seventh part of the whole are divisible by 7, and the seventh part of those which are divisible by 3, or by 5, or by 15, it follows that when all those which are multiples of 3 or 5, or both, are removed, the seventh part of those which remain are divisible by 7; and so on. Hence, the number of numbers not exceeding n, which are not divisible by 3, 5, 7, or 11, is ¹⁰/₁₁ of ⁶/₇ of ⁴/₅ of ²/₃ of n. Proceeding in this way, we find that the number of numbers which are prime to n, that is, which are not divisible by any one of its prime factors, a, b, c, ... is

or a^α-1b^β-1c^γ-1 ... (a - 1)(b - 1)(c - 1)....

Thus, 360 being 2³3²5, its number of divisors is 4 × 3 × 2, or 24, and there are 2³3.1.2.4 or 96 numbers less than 360 which are prime to it.

Prop. 5. If a be prime to b, then the terms of the series, a, a², a³, ... severally divided by b, must all leave different remainders, until 1 occurs as a remainder, after which the cycle of remainders will be again repeated.

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.

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 should it happen that the set 1, r, s, t, &c. is not complete, then m, mr, ms, &c. may give a different set of remainders.

All these last theorems are constantly verified in the process for reducing a fraction to a decimal fraction. If m be prime to b, or the fraction m/b in its lowest terms, the process involves the successive division of m, m × 10, m × 10², &c. by b. This process can never come to an end unless some power of 10, say 10ⁿ, is divisible by b; which cannot be, if b contain any prime factors except 2 and 5. In every other case the quotient repeats itself, the repeating part sometimes commencing from the first figure, sometimes from a later figure. Thus, ¹/₇ yields ·142857142857, &c., but ¹/₁₄ gives ·07(142857)(142857), &c., and ¹/₂₈ gives ·03(571428)(571428), &c.

In m/b, the quotient always repeats from the very beginning whenever b is a prime number and m is less than b; and the number of figures in the repeating part is then always b-1, or a measure of it. That it must be so, appears from the above propositions.

Before proceeding farther, we write down the repeating part of a quotient, with the remainders which are left after the several figures are formed. Let the fraction be ¹/₁₇, we have

0₁₀5₁₅8₁₄8₄2₆3₉5₅2₁₆9₇4₂1₃1₁₃7₁₁6₈4₁₂7₁

This may be read thus: 10 by 17, quotient 0, remainder 10; 10² by 17, quotient 05, remainder 15; 10³ by 17, quotient 058, remainder 14; and so on. It thus appears that 10¹⁶ by 17 leaves a remainder 1, which is according to the theorem.

If we multiply 0588, &c. by any number under 17, the same cycle is obtained with a different beginning. Thus, if we multiply by 13, we have

7647058823529411

beginning with what comes after remainder 13 in the first number. If we multiply by 7, we have 4117, &c. The reason is obvious: ¹/₁₇ × 13, or ¹³/₁₇, when turned into a decimal fraction, starts with the divisor 130, and we proceed just as we do in forming ¹/₁₇, when within four figures of the close of the cycle.

It will also be seen, that in the last half of the cycle the quotient figures are complements to 9 of those in the first half, and that the remainders are complements to 17. Thus, in 0₁₀5₁₅8₁₄8₄, &c. and 9₇4₂1₃1₁₃, &c. we see 0 + 9 = 9, 5 + 4 = 9, 8 + 1 = 9, &c., and 10 + 7 = 17, 15 + 2 = 17, 14 + 3 = 17, &c. We may shew the necessity of this as follows: If the remainder 1 never occur till we come to use aᵇ⁻¹, then, b being prime, b-1 is even; let it be 2k. Accordingly, a²ᵏ-1 is divisible by b; but this is the product of aᵏ-1 and aᵏ + 1, one of which must be divisible by b. It cannot be aᵏ - 1, for then a power of a preceding the (b - 1)th would leave remainder 1, which is not the case in our instance: it must then be aᵏ + 1, so that aᵏ divided by b leaves a remainder b-1; and the kth step concludes the first half of the process. Accordingly, in our instance, we see, b being 17 and a being 10, that remainder 16 occurs at the 8th step of the process. At the next step, the remainder is that yielded by 10(b-1), or 9b + b - 10, which gives the remainder b-10. But the first remainder of all was 10, and 10 + (b - 10) = b. If ever this complemental character occur in any step, it must continue, which we shew as follows: Let r be a remainder, and b - r a subsequent remainder, the sum being b. At the next step after the first remainder, we divide 10r by b, and, at the next step after the second remainder, we divide 10b - 10r by b. Now, since the sum of 10r and 10b - 10r is divisible by b, the two remainders from these new steps must be such as added together will give b, and so on; and the quotients added together must give 9, for the sum of the remainders 10r and 10b - 10r yields a quotient 10, of which the two remainders give 1.

If ¹/₅₉ and ¹/₆₁ be taken, the repeating parts will be found to contain 58 and 60 figures. Of these we write down only the first halves, as the reader may supply the rest by the complemental property just given.

01694915254237288135593220338, &c.
016393442622950819672131147540, &c.

Here, then, are two numbers, the first of which multiplied by any number under 59, and the second by any number under 61, can have the products formed by carrying certain of the figures from one end to the other.

But, b being still prime, it may happen that remainder 1 may occur before b - 1 figures are obtained; in which case, as shewn, the number of figures must be a measure of b - 1. For example, take ¹/₄₁. The repeating quotient, written as above, has only 5 figures, and 5 measures 41 - 1.

0₁₀2₁₈4₁₆3₃₇9₁

Now, this period, it will be found, has its figures merely transposed, if we multiply by 10, 18, 16, or 37. But if we multiply by any other number under 41, we convert this period into the period of another fraction whose denominator is 41. The following are 8 periods which may be found.

To find m/41, look out for m among the remainders, and take the period in which it is, beginning after the remainder. Thus, ³⁴/₄₁ is ·8292682926, &c., and ¹⁵/₄₁ is ·3658536585, &c. These periods are complemental, four and four, as 02439 and 97560, 07317 and 92682, &c. And if the first number, 02439, be multiplied by any number under 41, look for that number among the remainders, and the product is found in the period of that remainder by beginning after the remainder. Thus, 02439 multiplied by 23 gives 56097, and by 6 gives 14634.

The reader may try to decipher for himself how it is that, with no more figures than the following, we can extend the result of our division. The fraction of which the period is to be found is ¹/₈₇.

• 87)100(01149425
• 130
• 430
• 82001149425 × 25
• 37028735625 × 25
• 220718390625 × 25
• 46017959765625 × 25
• 25448994140625
• 0114942528735625
• 718390625
• 1795976 5625
• 448994
• 0114942528735632183908045977|011494
• |