Chapter XXII: Appendix: IX

ON SOME GENERAL PROPERTIES OF NUMBERS.

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.

[61] This theorem shews that what is _called_ reducing a fraction to its lowest terms (namely, dividing numerator and denominator by their greatest common measure), is correctly so called.

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

_a_ _c_ _a_ _b_
--- = ---, we have --- = ---;
_b_ _d_ _c_ _d_
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

_a_ _mc_ + _e_ _c_ _mc_
--- or ---------- = --- = ----
_b_ _md_ + _f_ _d_ _md_

Hence,

_e_ _mc_
--- and ---- must be equal, for if not,
_f_ _md_

_mc_ + _e_ _mc_ _e_
---------- would lie between ---- and ---,
_md_ + _f_ _md_ _f_

instead of being equal to the former. Hence,

_a_ _e_
--- = ---;
_b_ _f_

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

_a_ _e_
--- = --- in a similar manner, we find
_b_ _f_

_a_ _g_
--- = --- where _g_ < _e_, _h_ < _f_,
_b_ _h_

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

_a_ _v_
--- = ---
_b_ _w_

be one of the steps, and let _a_ = _kv_ + _x_, _b_ = _kw_ + _y_; so that

_kv_ + _x_ _v_
---------- = ---.
_kw_ + _y_ _w_

Now, if _x_ = 0 but not _y_, this is absurd, for it gives

_kv_ _kv_
---------- = ----.
_kw_ + _y_ _kw_

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

_ab_ _b_ _d_
---- = _d_, then --- = ---.
_c_ _c_ _c_

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

_b_ _km_ _m_ _m_
--- = ---- = ---, and ---
_c_ _kl_ _l_ _l_

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

_a_ _c_
--- = ---,
_b_ 10ⁿ

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

_a_ 10ⁿ_a_
--- be in its lowest terms; then ------
_b_ _b_

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.

[62] For that which measures a measure is itself a measure; so that if a measure of _a_ could have a measure in common with _b_, _a_ itself would have a common measure with _b_.

[63] A prime number is one which is prime to all numbers except its own multiples, or has no divisors except 1 and itself.

PROP. 4. If _b_ be prime to _a_, all the multiples of _b_, as _b_, 2_b_, ... 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

_a_ - 1 _b_ - 1 _c_ - 1
_n_ ------- ------- ------- ...
_a_ _b_ _c_

or _a_{^α-1} - 1}_b_ᵝ⁻¹_c_ᵞ⁻¹ ... (_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 _r__a_ + _b_, which (Prop. 4) cannot be _r_: let it be _s_. 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 _m_th 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]

[64] Expand (_a_-1)ᵇ by the binomial theorem; shew that _when b is a prime number_ every coefficient which is not unity is divisible by _b_; and the proposition follows.

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 2_k_. 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 _k_th 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 9_b_ + _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 10_r_ by _b_, and, at the next step after the second remainder, we divide 10_b_-10_r_ by _b_. Now, since the sum of 10_r_ and 10_b_-10_r_ 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 10_r_ and 10_b_-10_r_ 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.

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

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
820 01149425 × 25
370 28735625 × 25
220 718390625 × 25
460 17959765625 × 25
25 448994140625
0114942528735625
718390625
1795976 5625
448994
----------------------------+------
0114942528735632183908045977|011494
|