Algebra

Theory of Numbers

349 If 𝑎 is prime to 𝑏, 𝑎𝑏 is in its lowest terms.

Proof

Let 𝑎𝑏=𝑎₁𝑏₁, a fraction in lower terms.
Divide 𝑎 by 𝑎₁, remainder 𝑎₂ quotient 𝑞₁, Divide 𝑏 by 𝑏₁, remainder 𝑏₂ quotient 𝑞₁; and so on, as in finding the H.C.F. of 𝑎 and 𝑎₁, and of 𝑏 and 𝑏₁ (see 30). Let 𝑎_𝑛, and 𝑏_𝑛 be the highest common factors thus determined. Then, because 𝑎𝑏=𝑎₁𝑏₁, ∴𝑎𝑏=𝑎−𝑞₁𝑎₁𝑏−𝑞₁𝑏₁=𝑎₂𝑏₂70 and so on; thus 𝑎𝑏=𝑎₁𝑏₁=𝑎₂𝑏₂=⋯=𝑎_𝑛𝑏_𝑛 Therefore 𝑎 and 𝑏 are equimultiples of 𝑎_𝑛 and 𝑏_𝑛; that is, 𝑎 is not prime to 𝑏 if any fraction exists in lower terms. 350 If 𝑎 is prime to 𝑏, 𝑎'𝑏'=𝑎𝑏; then 𝑎' and 𝑏' are equimultiples of 𝑎 and 𝑏.

Proof

Let 𝑎'𝑏' reduced to its lowest terms be 𝑝𝑞. Then 𝑝𝑞=𝑎𝑏, and, since 𝑝 is now prime to 𝑞, and 𝑎 prime to 𝑏, it follows, by 349, that 𝑝𝑞 is neither greater nor less than 𝑎𝑏; that is, it is equal to it. Therefore ⋯. 351 If 𝑎𝑏 is divisible by 𝑐, and 𝑎 is not; then 𝑏 must be.

Proof

Let 𝑎𝑏𝑐=𝑞; ∴𝑎𝑐=𝑞𝑏 But 𝑎 is prime to 𝑐; therefore, by last, 𝑏 is a multiple of 𝑐. 352 If 𝑎 and 𝑏 be each of them prime to 𝑐, 𝑎𝑏 is prime to 𝑐. By 351 353 If 𝑎𝑏𝑐𝑑⋯ is divisible by a prime, one at least of the factors 𝑎, 𝑏, 𝑐, ⋯ must also be divisible by it.
Or, if 𝑝 be prime to all but one of the factors, that factor is divisible by 𝑝.351 354 Therefore, if 𝑎^𝑛 is divisible by 𝑝, 𝑝 cannot be prime to 𝑎; and if 𝑝 be a prime it must divide 𝑎. 355 If 𝑎 is prime to 𝑏, any power of 𝑎 is prime to any power of b.
Also, if 𝑎, 𝑏, 𝑐, ⋯ are prime to each other, the product of any of their powers is prime to any other product of their powers. 356 No expression with integral coefficients, such as 𝐴+𝐵𝑥+𝐶𝑥²+⋯, can represent primes only.

Proof

For it is divisible by 𝑥 if 𝐴=0; and if not, it is divisible by 𝐴, when 𝑥=𝐴. 357 The number of primes is infinite.

Proof

Suppose if possible 𝑝 to be the greatest prime. Then the product of all primes up to 𝑝, plus unity, is either a prime, in which case it would be a greater prime than 𝑝, or it must be divisible by a prime; but no prime up to 𝑝 divides it, because htere is a remainder 1 in each case. Therefore, if divisible at all, it must be by a prime greater than 𝑝. In either case, then, a prime greater than 𝑝 exists. 358 If 𝑎 be prime to 𝑏, and the quantities 𝑎, 2𝑎, 3𝑎, ⋯, (𝑏−1)𝑎 be divided by 𝑏, the remainders will be different.

Proof

Assume 𝑚𝑎−𝑛𝑏=𝑚'𝑎−𝑛'𝑏, 𝑚 and 𝑛 being less than 𝑏, ∴𝑎𝑏=𝑛−𝑛'𝑚−𝑚'Then by 350 359 A number can be resolved into prime factors in one way only. by 353 360 To resolve 5040 into its prime factors. Rule: Divide by the prime numbers successively.

Thus 5040=2⁴⋅3²⋅5⋅7 361 Required the least multiplier of 4704 which will make the product a perfect fourth power. By (196), 4704=2⁵⋅3⋅7². Then 2⁵⋅3¹⋅7²×2³⋅3³⋅7²=2⁸⋅3⁴⋅7⁴=84⁴ the indices 8, 4, 4 being the least multiples of 4 which are not less than 5, 1, 2 respectively.
Thus 2³⋅3³⋅7²=3584 is the multiplier required. 362 All numbers are of one of the forms 2𝑛 or 2𝑛+1 All numbers are of one of the forms 2𝑛 or 2𝑛−1 All numbers are of one of the forms 3𝑛 or 3𝑛±1 All numbers are of one of the forms 4𝑛 or 4𝑛±1 or 4𝑛+2 All numbers are of one of the forms 4𝑛 or 4𝑛±1 or 4𝑛−2 All numbers are of one of the forms 5𝑛 or 5𝑛±1 or 5𝑛±2 and so on. 363 All square numbers are of the form 5𝑛 or 5𝑛±1.

Proof

By squaring the forms 5𝑛, 5𝑛±1, 5𝑛±2, which comprehend all numbers whatever. 364 All cube numbers are of the form 7𝑛 or 7𝑛±1. And similarly for other powers. 365 The highest power of a prime 𝑝, which is contained in the product 𝑚!, is the sum of the integral parts of 𝑚𝑝, 𝑚𝑝², 𝑚𝑝³, ⋯ For there are 𝑚𝑝 factors in 𝑚! which 𝑝 will divide; 𝑚𝑝² which it will divide a second time; and so on. The successive divisions are equivalent to dividing by 𝑝^𝑚𝑝⋅𝑝^𝑚𝑝²⋅⋯=𝑝^{𝑚𝑝+𝑚𝑝²+⋯}

Example

The highest power of 3 which will divide 29!. Here the factors 3, 6, 9, 12, 15, 18, 21, 24, 27 can be divided by 3. Their number is 293=9 (the integral part).
The factors 9, 18, 27 can be divided a second time. Their number is 293²=3 (integral part).
One factor, 27, is divisible a third time. 293³=1 (integral part).
9+3+1=13; that is, 3¹³ is the highest power of 3 which will divide 29!. 366 The product of any 𝑟 consecutive integers is divisible by 𝑟!.

Proof

𝑛(𝑛−1)⋯(𝑛−𝑟+1)𝑟! is necessarily an integer, by (96). 367 If 𝑛 be a prime, every coefficient in the expansion of (𝑎+𝑏)^𝑛, except the first and last, is divisible by 𝑛By last 368 If 𝑛 be a prime, the coefficient of every term in the expansion of (𝑎+𝑏+𝑐⋯)^𝑛, except 𝑎^𝑛, 𝑏^𝑛, ⋯, is divisible by 𝑛.

Proof

By (367). Put 𝛽 for (𝑏+𝑐+⋯). 369

Fermat's Theorem

If 𝑝 be a prime, and 𝑁 prime to 𝑝; then 𝑁^𝑝−1−1 is divisible by 𝑝

Proof

𝑁^𝑝=(1+1+⋯)^𝑝=𝑁+𝑀𝑝By 368 370 If 𝑝 be any number, and if 1, a, 𝑏, 𝑐, ⋯, (𝑝−1) be all the numbers less than, and prime to 𝑝; and if 𝑛 be their number, and 𝑥 any one of them; then 𝑥^𝑛−1 is divisible by 𝑝.

Proof

If 𝑥, a𝑥, 𝑏𝑥, ⋯, (𝑝−1)𝑥 be divided by 𝑝, the remainders will be all different and prime to 𝑝 [as in (358)]; therefore the remainders wil be 1, a, 𝑏, 𝑐, ⋯, (𝑝−1); therefore the product 𝑥^𝑛a𝑏𝑐⋯(𝑝−1)=a𝑏𝑐⋯(𝑝−1)+𝑀𝑝 371

Wilson's Theorem

If 𝑝 be a prime, and only then, 1+(𝑝−1)! is divisible by 𝑝.

Proof

Put (𝑝−1) for 𝑟 and 𝑛 in (285), and apply Fermat's Theorem to each term. 372 If 𝑝 be a prime=2𝑛+1, then (𝑛!)²+(−1)^𝑛 is divisible by 𝑝.

Proof

By multiplying together equi-distant factors of (𝑝−1)! in Wilson's Theorem, and putting 2𝑛+1 for 𝑝. 373 Let 𝑁=𝑎^𝑝𝑏^𝑞𝑐^𝑟⋯ in prime factors; the number of integers, including 1, which are less than 𝑛 and prime to it, is 𝑁~~1−1𝑎1−1𝑏1−1𝑐~~⋯

Proof

The number of integers prime to 𝑁 contained in 𝑎^𝑝 is 𝑎^𝑝−𝑎^𝑝𝑎. Similarly in 𝑏^𝑞, 𝑐^𝑟, ⋯. Take the product of these.
Also the number of integers less than and prime to (𝑁×𝑀×⋯) is the product of the corresponding numbers for 𝑁, 𝑀, ⋯ separately. 374 The number of divisors of 𝑁, including 1 and 𝑁 itself, is =(𝑝+1)(𝑞+1)(𝑟+1)⋯. For it is equal to the number of terms in the product (1+𝑎+⋯+𝑎^𝑝)(1+𝑏+⋯+𝑏^𝑞)(1+𝑐+⋯+𝑐^𝑟)⋯ 375 The number of ways of resolving 𝑁 into two factors is half the number of its divisors (371). If the number be a square the two equal factors must, in this case, be reckoned as two divisors. 376 If the factors of each pair are to be prime to each other, put 𝑝, 𝑞, 𝑟, ⋯, each equal to one. 377 The sum of the divisors of 𝑁 is 𝑎^𝑝+1−1𝑎−1⋅𝑏^𝑞+1−1𝑏−1⋅𝑐^𝑟+1−1𝑐−1⋅⋯

Proof

By the product in (374), and by (85). 378 If 𝑝 be a prime, then the 𝑝−1^th power of any number is of the form 𝑚𝑝 or 𝑚𝑝+1.By Fermat's Theorm (369)

Example

The 12^th power of any number is of the form 13𝑚 or 13𝑚+1. 379 To find all the divisors of a number; for instance, of 504. III 1 50422 25224 12628 633361224 2139183672 7771428562142 8416863126252504 Explanation. Resolve 504 into its prime factors, placing them in column II. The divisors of 504 are now formed from the numbers in column II., and placed to the right of that column in the following manner:

Place the divisor I to the right of column II., and follow this rule:- Multiply in order all the divisors which are written down by the next number in column II., which has not already been used as a multiplier: place the first new divisor so obtained and all the following products in order to the right of column II.

380 𝑆_𝑟 the sum of the 𝑟^th powers of the first 𝑛 natural numbers is divisible by 2𝑛+1.

Proof

𝑥(𝑥²−1²)(𝑥²−2²)⋯(𝑥²−𝑛²) constitutes 2𝑛+1 factors divisible by 2𝑛+1, by (366). Multiply out, rejecting 𝑥, which is to be less than 2𝑛+1. Thus using (372), 𝑥^2𝑛−𝑆₁𝑥^2𝑛−2+𝑆₂𝑥^2𝑛−4−⋯𝑆_𝑛−1𝑥²+(−1)^𝑛(|𝑛)²=𝑀(2𝑛+1). Put 1, 2, 3, ⋯, (𝑛−1) in succession for 𝑥, and the solution of the (𝑛−1) equations is of the form 𝑆_𝑟=𝑀(2𝑛+1)