Sidebilder
PDF
ePub

positive minimum residue; -2 is the negative minimum residue, and, at the same time, the absolute minimum.

404. The following consequences follow from the above:

Numbers which are congruous with reference to a composite modulus are so with reference to any of its divisors.

If several numbers are congruous with the same number with reference to the same modulus, they will be congruous with each other with reference to this modulus.

The same modulus must be supposed in what follows:

Congruous numbers have the same minima residues; incongruous have different.

405. If the numbers A, B, C, &c.; a, b, c, &c., are congruous each to each, i. e., Aa, Bb, &c, we shall have

A+B+C... = a+b+c..

If A a, Bb, we have also A-Ba-b.

406. If A a, we have also kAka.

If k is positive, this is but a particular case of the preceding article, in which AB=C... and abc...

If k is negative, -k will be positive; then -kA= ka .. kA=ka.

If A= a, Bb, then AB=ab; because AB=AB=Ab=ba.

407. If the numbers A, B, C... a, b, c . . ., each to each, then

ABC...abc...

for, by the preceding article, AB ab; for the same reason, ABC=abc, and so on.

By taking all the terms, A, B, C ... equal, and a, b, c . . . also equal, if Aa, Akak.

408. Let X be a function of the indeterminate x of the form

Ar+B+Cr+, &c.,

A, B, C... being any entire numbers whatever. If we give to x congruous values with reference to a certain modulus, the resulting values for X will be congruous also.

Let ƒ and g be congruous values of r; by the preceding articles, ƒa=ga3, and AfAga; in the same way we have BfBg", &c.

This theorem may be easily extended to functions of several indetermi

nates.

409. If, then, we substitute in place of r all entire consecutive numbers, and seek the minima residues of the values of X, they will form a series in which, after an interval of m terms (m being the modulus), the same terms will be again presented; that is to say, this series will be formed of a period of m terms repeated indefinitely.

Let there be, for example, X=x3-8x+6, and m=5; for x=0, 1, 2, 3, &c.; the values of X give for positive minima residues 1, 4, 3, 4, 3, 1, 4, &c., or the five, 1, 4, 3, 4, 3, are repeated indefinitely; and if we continue the series in the contrary direction, that is, if we give to r negative values, the same period will reappear in an inverse order; whence it follows that the series contains no other terms than those which compose the period.

410. Then, in this example, X can not become0, nor =2(mod. 5); and still less 0 or =2; from which it follows that the equations -8x+6=0 and a3—8x+4=0 have not entire roots, and, consequently, not rational roots. We see, in general, that when X is of the form

X2+Axa¬1+Bxa¬2+, &c., +N,

A, B, C... being entire quantities, and n entire and positive, the equation X=0 (a form to which every algebraic equation may be reduced) will have no rational root, if it happen that, for a certain modulus, the congruence X=0 be not satisfied.

411. Many arithmetic theorems may be demonstrated by the aid of the foregoing principles, as, for instance, the rule for determining whether a number is divisible by 9, 11, or any other number.

With reference to the modulus 9, all the powers of 10 are congruous with unity; then, if the number is of the form a+10b+100c+1000d+, &c., it will have, with reference to the modulus 9, the same minimum residue as a+b+c+, &c. It is clear from this, that if we add the figures of the number without regarding their place value, the sum obtained and the proposed number will have the same minimum residue. If, then, this last is divisible by 9, the sum of the figures will be also, and only in this case. It is the same with the divisor 3.

Many of the properties of prime numbers, the divisibility of products already given, &c., may be demonstrated by the aid of this system, but we shall not repeat them.

412. The term congruence is analogous to equation, and the determination of such values, for an indeterminate x, as to produce congruence in expression, is called resolving them. There are congruences resolvable and irresolvable. Congruences are also divided, like equations, into algebraic and transcendental. Those which are algebraic are divided, again, into congruences of the first, second, and higher degrees. There are congruences, also, containing different unknown quantities, of the elimination of which Gauss treats.

413. The congruence ax+b=c may be solved when its modulus m is prime with a; thus, let e be the positive minimum residue of c-b. We find necessarily a value of x<m, such that the minimum residue of the product ar, with reference to the modulus m, shall be e. Call this value, and we

[blocks in formation]

v

Here is called the root of the congruence. It is evident that all the numbers congruous with v, with reference to the modulus of the congruence, will also be roots (Art. 408). It is also evident that all the roots should be congruous with v; in fact, if t be another root, we have av+bat+b; then atav; and therefore vt. We may therefore conclude that the congruence xv(mod. m) gives the complete resolution of the congruence ar+b=c. The foregoing exposition will serve to show how the algerithm of Gauss connects itself with the indeterminate analysis, and we shall here quit the subject.

414. No algebraical formula can contain prime numbers only.

[merged small][ocr errors]

represent any general algebraical formula. It is to be demonstrated that such values may be given to x, that the formula in question shall not with that value produce a prime number, whatever values are given to p, q, r, &c. For suppose, in the first place, that by making x=m, the formula

[merged small][merged small][merged small][merged small][merged small][merged small][merged small][ocr errors][merged small][merged small][merged small][merged small][merged small]

p+qx+rx2+sx3=(p+qm+rm2+sm3+, &c.,)+
P(go+2rmo+38m2)+P2(ro2+3smo)+s43P3

=P+P(go+2rm+38m2)+
P2(ro2+3smo2)+sp3P3.

But this last quantity is divisible by P; and, consequently, the equal quantity p+qx+rx2+8x3, &c.,

is also divisible by P, and can not, therefore, be a prime number.

Hence, then, it appears, that in any algebraical formula such a value may be given to the indeterminate quantity as will render it divisible by some other number; and, therefore, no algebraical formula can be found that contains prime numbers only.

But, although no algebraical formula can be found that contains prime numbers only, there are several remarkable ones that contain a great many; thus, x+x+41, by making successively x=0, 1, 2, 3, 4, &c., will give a series 41, 43, 47, 53, 61, 71, &c., the first forty terms of which are prime numbers. The above formula is mentioned by Euler in the Memoirs of Berlin (1772, p. 36).

To the above we may add the following: x2+x+17 and 2x2+29; the former has 17 of its first terms prime, and the latter 29.

Fermat asserted that the formula 2m+1 was always a prime, while m was taken any term in the series 1, 2, 4, 8, 16, &c.; but Euler found that 23+1=641x6700417 was not a prime.

415. If a and b be any two numbers prime to each other, and each of the terms of the series

b, 2b, 3b, 4b, &c., (a−1)b

be divided by a, they will each leave a different remainder. For if any two of these terms, when divided by a, leave the same remainder, let them be represented by xb, yb; then it is obvious that xb-yb would be divisible by a, or (x—y)b would be divisible by a. But this is impossible, because a is prime to b, and x-y is less than a; therefore b(x-y) is not divisible by a, but it would be so divisible if the terms xb, yb left the same remainder; these do not, therefore, leave the same remainder; consequently, every term of the series

b, 2b, 3b, &c., (a—1)b,

divided by a, will leave a different remainder.

DEDUCTIONS.

416. Since the remainders arising from the division of each term in the series b, 2b, 3b, &c., (a-1)b

by a are different from each other, and a-1 in number, and each of them

necessarily less than a, it follows that these remainders include all numbers from 1 to a-1.

417. Hence, again, it appears that some one of the above terms will leave a remainder 1; and that, therefore, if b and a be any two numbers prime to each other, a number r<a may be found that will render br-1 divisible by a, or the equation bx-ay=1 is always possible if a and b are numbers prime to each other.

And it is always impossible if a and b have any common measure, as is evldent, because one side of the equation bx-ay=1 would be divisible by this common measure, but the other side, 1, would not be so; therefore, in this case the equation is impossible.

418. If a be any prime number, then will the formula

1.2.3.4.5, &c., (a-1)+1

be divisible by a; for it is demonstrated in our preceding second deduction, that if a and b be any two numbers prime to each other, another number x may be found <a, that renders the product br-1*a, or, which is the same thing, br=ya+1; and that there is only one such value of x<a, may be shown as follows:

The foregoing equation gives, by transposition,

[ocr errors][merged small][merged small][merged small]

and make x=x+m and y'=y±n, where m is necessarily less than a, because both x and x' are so by the supposition.

Now, by this substitution, we have

but

(bxbm)-(ayan)=1;
bx-ay=1;

therefore bm=Fan, or bm÷a; but this is impossible, since b is prime to a and m<a, as in Art. 415. There can not, therefore, be two values of x less than a, that render the equation br-ay-1 possible.

But, in the series of integers

1.2.3.4.5......a-1,

every term is prime to a except the first, a being itself a prime; if, therefore, we write successively b=2, b'=3, b'=4, &c., a corresponding term x, in the same series, may be found for each distinct value of b, that renders the product xbay+1, x'b'±ay'+1, x"b"±ay" +1, &c.; and it is evident that no one of these values of r can be equal either to 1 or a-1; for, in the first case, we should have 1×b=ay+1, which is impossible, because b<a; and the second would give (a—1)b=ay+1, or a(b—y)=b+1; that is, b+1÷÷÷a, which can only be when b-a-1, or when br, which case is excepted, because we suppose two different terms of the series. In fact, since (a—1)2

ay+1, there can be no other term in the same series that is of this form; for if ray+1, then (a-1)2-x2 would be divisible by a, or (a-1+x) ×(a—1—x)÷a, which is impossible, since each of these factors is prime to

*To save the repetition of the words "divisible by," which frequently occur, the sign is used to express them; and, for the same reason, the symbol is introduced, to express the words "of the form of," which are also of frequent occurrence.

Нн

a, as is evident, because x <a, and a is a prime number. Hence our product

becomes

1.2.3.4.5....(a—1)

1. bx.b'x'. b'x'....a-1;

but each of these products, bx, b'x', b''x', &c., is, as we have seen, of the form ay+1; therefore their continued product will have the same form, and the whole product, including 1 and a-1, will be

H (ay+1)x(a−1)a2y+ay+a−1,

to which if unity be added, the result will be evidently divisible by a; that is, the formula

1.2.3.4.5......(a−1)+1

is always divisible by a when a is a prime number.

* DEDUCTIONS.

(1) The product

is the same as

1.2.3.4.5......(a-1)

1(a—1)2(a—2)3(a—3), &c., (a—1)2;

and this product, as regards remainder, when divided by a, is the same as

[merged small][merged small][ocr errors][merged small][merged small][merged small][merged small][merged small][merged small][merged small]

therefore, from what is said above relating to the ambiguous sign, we shall have

[ocr errors][merged small][merged small][subsumed][ocr errors][ocr errors][subsumed]

Hence every prime of the form 4n+1 is a divisor of the sum of two squares. Again, the latter form may be resolved into the two factors

[blocks in formation]

which product being divisible by a, it follows that a is a divisor of one or other of these factors when it is a prime number of the form 4n-1.

(2) From the first product, which we have shown to be divisible by a, viz., 1.2.3.4, &c., (a-1)+1

a

we may derive a great many others, as

=e, an integer,

[blocks in formation]

and so on till we arrive at the same form as that in the first deduction.

« ForrigeFortsett »