Зображення сторінки
PDF
ePub

The quotients resulting from the division by 9 are omitted, and the remainders alone preserved:

1 rem.+8=9, 9÷9=1+0 rem.

0 rem.+4=4, 0+4+8=12, 12÷9=1+3 rem.

3 rem.+2=5, 5÷9=0+5 rem. Whence r=5.

Division of the sum of the digits of the multiplier by 9 · 3+5=8, 8+4=12, 12÷9=1+3 rem.

3+8=11, 11+9=1+2 rem. Whence r'=2.

Therefore rxr'=5x2=10

And 1+0=1, 1÷9=0+1 rem.

The remainder from the division of the sum of the digits of rxr′ is consequently 1.

Division of the sum of the digits of the product by 9:

1+3+4+2=10, 10+9=1+1 rem.

1 rem.+8=9, 9÷9=1+0 rem.

0 rem.
1.+5+4=9, 9÷+9=1+0 rem.

0 rem. +1+3+6=10, 10+9=1+1 rem.

The remainder from the division of the sum of the digits of NN' is 1; but the remainder from the division of the sum of the digits of rxr' is also 1; whence the product is to be presumed accurate.

When the remainder from the division of the sum of the digits of the product rx is not the same as the remainder from the division of the sum of the digits of the product N× N', the calculation ought to be revised, being probably erroneous.

In the case of division; when the quotient is exact, that is, when D=dxq, d, q, D, are the representatives of N,N' and Nx N' respectively, and the process of verification is precisely like that already detailed.

But when the quotient is not exact, that is, when D=dxq+R, before proceeding with the verification, it is necessary to subtract the remainder R from the dividend D.

The dividend is thus rendered the exact product of the divisor and quotient, and this case reduced to the preceding.

It is evident that the figure 9 may hold the place of 0, and conversely; also that the order of the figures in NN' may be changed without changing the sum of the digits, and consequently without changing the remainder left from the division of that sum by 9.

For these reasons (and others might be adduced) the verifications of multiplication and division by this method are not so deserving of confidence as those already given in Articles 101 and 102.

132. A number which is exactly divisible by any other number greater than unity is said to be a composite number. The terms Prime and Composite are, hence, opposed to each other.

133. From the preceding remarks on the conditions of the divisibility of numbers, it is certain that no even number, excepting 2, can be a prime number (Art. 119). Among odd numbers the multiples of 3 and 5 are discovered by the tests of Articles 119 and 120. Therefore, in the research of prime numbers, it is not necessary to try any excepting such odd numbers as have none of these characters of divisibility.

The limits within which it is necessary to discover by trial whether a given number is prime or composite admit of another contraction.

If any number is divided by 6, a certain quotient, q, is found, and a remainder of 1, 2, 3, 4, 5, or 0; therefore all numbers may be considered as multiples of 6 with one of the remainders 1, 2, 3, 4, or 5.

Now, a multiple of 6 with the remainder 2 or 4 is divisible by 2, and a multiple of 6 with the remainder 3 is divisible by 3. Whence the prime numbers must all be found amongst multiples of 6+1 and multiples of 6+5.

These multiples of 6 may be represented by the expressions,

6x9+11

and 6×9+5

[ocr errors]

But 5 is equal to 6 diminished by 1, or 5=6-1. Therefore 6×q+5 may be otherwise expressed,

6xq+6-1

or q times 6+1 time 6-1

or (q+1)x6-1.

And since q denotes a number, that number and 1 may be added together. Let q+1=g,

then 6×q+5 becomes
6xq-1.

And the expressions A become

6x9 +1} B.
6xq-1]

Since the conclusions deduced in this Article depend on the condition that 6x9 and 6× are multiples of 6, without reference to the particular values of q, q, these conclusions must be true when q, q' are equal. Whence both of the expressions B may be put under the form,

6q+1.*

This conclusion, expressed in words, is: All prime numbers greater than 3 have this property, that if they are augmented or diminished by unity, the results are divisible by 6.

133. But although all prime numbers are comprehended in the formula 6q+1 (q being any whole number whatever), yet all the numbers expressed by 6q+1 are not prime numbers.

For the expressions, 6×q+1, 6×q+3, 6×q+5, evidently comprehend all odd numbers greater than 5. Of these, 6xq+3, which expresses multiples of 3, is not included in the general formula 6×q+1. This formula, therefore, comprehends all odd numbers which are not multiples of 3.

Now, the product of any two prime numbers greater than 2 or 3 is an odd number which cannot be divided by 3 (Art. 114). This product being an odd number, not a multiple of 3, is expressed by the formula 6xq±1, and it is not a prime number.

134. To discover whether a number expressed by the formula 6xq+1 is an absolute prime number, it is necessary to attempt its division by all the prime numbers, from 7 inclusive to that which is immediately inferior to the half of the given number. Beyond half the number it is useless to extend the trial, as no number can be exactly divided by a divisor greater than its half.

135. The manner of distinguishing prime from composite numbers having been explained, let it be next required to find all the prime factors of any given number.

To give generality to the results, let N represent the given number and a the least prime number by which N is divisible; and let the division of N and the successive quotients by a be repeated until after n divisions a quotient, N', not divisible by a is found.

Then N=a" × N'.

Since every prime number, other than a, which divides N, must divide N' (Art. 111), the investigation of the prime factors of N, different from a, is reduced to that of the prime factors of N'.

Let b represent the least prime number by which N' can be divided, n' the number of divisions possible by b, and N" the quotient not divisible by b.

Then N'b'xN",

and N=a"> N'=a" × b2 ×N".

Again, every prime factor, except a, b, which divides N must divide N".

* A general expression such as 6 x q± 1 is termed a Formula.

Let c be the prime number which divides N"; let the division of N" by c be n' times possible; and the quotient not divisible by c, N'"..

Then N"=""'×N",

and N=a"-b" xN"=a"×b" ×c""'N'""'.

Continuing this process, a prime number, or some power of a prime number, must be at length obtained for quotient. Dividing as often as possible by this prime number, a last quotient equal to unity is found. Let it be supposed that N'"'=d"'"'.

Then Naxb" × c''' ×N'"'=a" × b"' × c""' × d'"'.

And a, b, c, d are the only prime factors which can enter into the number N (Art. 115). This being accomplished, N is said to be decomposed into its simple factors.

136. As a particular example of the decomposition of a number into simple factors, let it be required to find the simple factors of the number 105840. Calculation:

2) 105840

2) 52920

2) 26460

2) 13230

3) 6615

3) 2205

3) 735

5) 245

7) 49

7) 7

1

:

Explanation the given number, 105840, ends in 0, therefore it is divisible by 2 (Art. 119).

For the same reason the first, second, and third quotients are divisible by 2. The fourth quotient, 6615, being an odd number, is not divisible by 2. Whence 105840 is divisible by 2×2×2×2=2*,

And 105840=24 × 6615.

The sum of the digits of 6615 being divisible by 3, 6615 is divisible by 3 (Art. 120).

For the same reasons the fifth quotient, 2205, and the sixth, 735, are divisible by 3; but the seventh, 245, is not.

Whence 6615 is divisible by 3×3×3=33.

And 105840=2+ × 6615=24 x 33 x 245.

The last figure of 245 being 5, 245 is divisible by 5 (Art. 122); but the 8th quotient, 49, ending neither in 5 nor 0, is not divisible by 5.

Whence 245=5 × 49,

And 105840=24 × 33 × 245=24 × 33 × 5 × 49.

The next prime number is 7, attempting the division of 49 by 7; 49+7=7, and 7+7=1.

Whence 49=7x7=72,

And 105840-24 × 33 × 5 × 49=24 × 33 × 5x72.

2, 3, 5, 7, are therefore the simple factors of the given number, 105840.

137. When two numbers, N, N', have been reduced to expressions composed of the products of their simple factors, if none of the prime factors which enter into the one number are found in the other, the numbers are prime to each other (Art. 114).

If one prime factor, a, is common to N, N', the numbers are both divisible by this factor, which is the only, and therefore the greatest, common measure of them both.

GREATEST COMMON MEASURE.

....

or m times in each, then If the prime factor, a, is contained 2, 3, 4 a2, a3, a1. . . . . or a" is the greatest common measure of N, N'. But if a is contained m times in N and n times in N', n being less than m, a" is the greatest common measure of N, N'.

For, let N=a" q, and N'=a" ×q. Then, since a, q, q' are prime to each other, the numbers N, N' can contain no common prime factor excepting a. Now a" xq is divisible by a", since by hypothesis the factor a enters into the product expressed by a" oftener than into that expressed by a"; and Whence aq or N, and a"×q or N', are both a"xq is a multiple of a". multiples of a"; but a" is the greatest number by which a" can itself be divided whence it is evident that a" is the greatest common measure of N, N'.

:

If N=a" b'xq'' and N'=a"b" ×q'", in which expressions a, b, q', q'" are prime to each other, and m, m' are greater respectively than n, n', it may in like manner be shown that a"b" is the greatest common measure of the numbers N, N': also that if m is greater than n, but m' less than n', then ab is the greatest common measure of N, N'.

", "", of which n" is less If another simple factor, c, raised to the powers c", than m", is contained in N, N' respectively, it follows, for the reasons already given, that a"b" is the greatest common measure of the numbers N, N'. This reasoning is as applicable to all the simple factors common to two given numbers as it is to one, or two, or three such factors. Whence the greatest common measure of two numbers is equal to the product of all the prime factors common to the two numbers raised each to the lower of the two powers with which it is affected in either of the given numbers.

138. If a" is written a xaxaxa

a"

αχαχα.

[ocr errors][ocr errors]

to m factors,

.

to n factors,

and the same is done with b', b", cm'', c'', &c. &c.,

so that all the repetitions of all the simple factors common to N, N' are put in evidence, the conclusion just obtained may be more simply expressed thus: The greatest common measure of two numbers is equal to the product of all the simple factors common to the two numbers.

139. In the same manner it may be proved that the greatest common measure of three numbers is composed of the product of all the prime factors common to the three numbers; that of four numbers to the product of all the prime factors common to the four numbers, &c. &c.

140. If two numbers, N, N', are multiplied together, the product NxN' is a multiple of both the numbers; and if N, N' are decomposed into their simple factors, the product of all the factors being equal to NxN' is also a multiple of both the numbers.

When the simple factors into which N is decomposed are all different from those into which N' is decomposed, it is evident that the product NxN' is the least number which can be divided by both the numbers N, N' (Art. 115), or that it is the least common multiple of these numbers.

But when N, N' have one or more common prime factors, the least common multiple of N and N' is less than the product N× N'.

Let N be resolved into the product of the prime factors a, b, and N' be re

solved into the product of the prime factors a, c.

Then, since N divides any multiple of ab, it divides ab xc,

and since N' divides any multiple of ac, it divides ac xb.

Whence abc or acb is a common multiple of N and N'. This multiple of N, N' is less than N× N' or aabc. Also, since abc contains only the prime factors which enter into N, N', and since, to be capable of division by N,N', the number abc must contain every prime factor found in N, N', it follows that abc is the least common multiple of N, N'.

Next, let N contain the prime factors aab or ab,

and N.

ac:

F 3

Then, since N divides any multiple of ab, it divides a2bc,

and since N' divides any multiple of ac, it divides ac × ab.

Whence a2bc=ac × ab=a2bc is a common multiple of N, N'; and since it contains every prime factor found in N, N', and no more, it is the least common multiple of N, N'.

Since the product of the prime factors abc cannot be divided by a2, or the product abe by a", when i is greater than n, it follows that the highest power of each prime factor common to two numbers must be a factor of the least common multiple of these numbers.

Again, since the product of the prime factors ab cannot be divided by the prime factor c, or the product of ac by b (Art. 114), it is also evident that all the prime factors which are not common to N, N' must enter into the least common multiple of N, N'.

That which has been proved in the case of a, a, a, a", being equally true of a second common prime factor, b, b2, b', b", a third common prime factor, c, c2, c'', c'', &c., it follows, that to form the least common multiple of two numbers it is necessary to decompose the numbers into their prime factors, and to multiply together all the prime factors not common to the two numbers and the highest powers of the common prime factors. The product thus obtained is the multiple required.

[ocr errors]

141. For the same reasons, if N, N', N'. . . . are decomposed into prime factors, the least common multiple of N, N', N”. ... is equal to a product of which all the prime factors not common to the numbers raised to their respective powers, and the prime factors common to the numbers raised to the highest powers which they obtain in any of the numbers N, N', N'. . are the several factors.

142. Instead of denoting the repetitions of any simple factor by an exponent, let every factor be put in evidence, thus,

Let N-aabbce and N'aaabcc,

or, N=aabe × be and N'=aabc × ac.

Then, since N divides aabc × be, it also divides aabc beac;
And since N' divides dabc × ac, it divides aabc × ac × be.

Whence aabc beac, or aabc ac × be, or aabc abce, is a common multiple of N and N'.

Again, to render aabc x be or N capable of division by aabc xac or N', it is necessary to multiply aabc × be by ac; and to render aabc × ac capable of division by aabex be, it is necessary to multiply aabc x be by ac. Whence it follows, that aabc abce is the least number which is exactly divisible by aabc be and aabc ac; that is, aabc × abce is the least common multiple of the numbers N, N'.

The factors of the least common multiple of N, N' are,

1st. The simple factors which are common to N and N', taken once only.

2d. The simple factors contained in N, and not in N'.

3d. The simple factors contained in N', and not in N.

Whence, if two numbers are decomposed into simple factors, and if all the simple factors which are common to both the numbers are cancelled in one of them, the continual product of the remaining simple factors is the least common multiple of the two numbers.

The product of all the simple factors common to N, N', is the least common multiple of N, N': let this be m.

Then,

N aabbce

m aabc N' aaabcc

[blocks in formation]

be: let be=q.

ac: let ac q'.

Consequently aabc × be × ac=mqq; and hence, if two given numbers are divided by their greatest common measure, the product of the greatest

« НазадПродовжити »