up | next | prev | tail |
In the present chapter we are concerned primarily with certain elementary properties of the positive integers 1, 2, 3, 4, …It will sometimes be convenient, when no confusion can arise, to employ the word integer or the word number in the sense of positive integer.
We shall suppose that the integers are already defined, either by the process of counting or otherwise. We assume further that the meaning of the terms greater, less, equal, sum, difference, product is known.
From the ideas and definitions thus assumed to be known follow immediately the theorems:
I. | The sum of any two integers is an integer. |
II. | The difference of any two integers is an integer. |
III. | The product of any two integers is an integer. |
Other fundamental theorems, which we take without proof, are embodied in the following formulas:
IV. | = | . | |
V. | = | . | |
VI. | = | . | |
VII. | = | . | |
VIII. | = | . |
Here , , denote any positive integers.
These formulas are equivalent in order to the following five theorems: addition is commutative; multiplication is commutative; addition is associative; multiplication is associative; multiplication is distributive with respect to addition.
EXERCISES
DEFINITIONS. An integer is said to be divisible by an integer if there exists an integer such that . It is clear from this definition that is also divisible by . The integers and are said to be divisors or factors of ; and is said to be a multiple of or of . The process of finding two integers and such that is equal to a given integer is called the process of resolving into factors or of factoring ; and is said to be resolved into factors or to be factored.
We have the following fundamental theorems:
I. If is a divisor of and is a divisor of , then is a divisor of .
Since is a divisor of a there exists an integer such that . Since is a divisor of there exists an integer such that . Substituting this value of in the equation we have . But from theorem III of § 1.1 it follows that is an integer; hence, is a divisor of , as was to be proved.
II. If is a divisor of both and , then is a divisor of the sum of and .
From the hypothesis of the theorem it follows that integers and exist such that
Adding, we have
where is an integer. Hence, is a divisor of .
III. If is a divisor of both and , then is a divisor of the difference of and .
The proof is analogous to that of the preceding theorem.
DEFINITIONS. If and are both divisible by , then is said to be a common divisor or a common factor of and . Every two integers have the common factor 1. The greatest integer which divides both and is called the greatest common divisor of and . More generally, we define in a similar way a common divisor and the greatest common divisor of integers , , , .
DEFINITIONS. If an integer is a multiple of each of two or more integers it is called a common multiple of these integers. The product of any set of integers is a common multiple of the set. The least integer which is a multiple of each of two or more integers is called their least common multiple.
It is evident that the integer is a divisor of every integer and that it is the only integer which has this property. It is called the unit.
DEFINITION. Two or more integers which have no common factor except are said to be prime to each other or to be relatively prime.
DEFINITION. If a set of integers is such that no two of them have a common divisor besides they are said to be prime each to each.
EXERCISES
DEFINITION. If an integer is different from 1 and has no divisor except itself and 1 it is said to be a prime number or to be a prime.
DEFINITION. An integer which has at least one divisor other than itself and 1 is said to be a composite number or to be composite.
All integers are thus divided into three classes:
We have seen that the first class contains only a single number. The third class evidently contains an infinitude of numbers; for, it contains all the numbers In the next section we shall show that the second class also contains an infinitude of numbers. We shall now show that every number of the third class contains one of the second class as a factor, by proving the following theorem:
I. Every integer greater than 1 has a prime factor.
Let be any integer which is greater than 1. We have to show that it has a prime factor. If is prime there is the prime factor itself. If is not prime we have
where and are positive integers both of which are less than . If either or is prime we have thus obtained a prime factor of . If neither of these numbers is prime, then write
Both and are factors of and each of them is less than . Either we have not found in or a prime factor of or the process can be continued by separating one of these numbers into factors. Since for any given there is evidently only a finite number of such steps possible, it is clear that we must finally arrive at a prime factor of . From this conclusion, the theorem follows immediately.
Eratosthenes has given a useful means of finding the prime numbers which are less than any given integer . It may be described as follows:
Every prime except 2 is odd. Hence if we write down every odd number from 3 up to we shall have it the list every prime less than except 2. Now 3 is prime. Leave it in the list; but beginning to count from 3 strike out every third number in the list. Thus every number divisible by 3, except 3 itself, is cancelled. Then begin from 5 and cancel every fifth number. Then begin from from the next uncancelled number, namely 7, and strike out every seventh number. Then begin from the next uncancelled number, namely 11, and strike out every eleventh number. Proceed in this way up to . The uncancelled numbers remaining will be the odd primes not greater than .
It is obvious that this process of cancellation need not be carried altogether so far as indicated; for if is a prime greater than , the cancellation of any number from will be merely a repetition of cancellations effected by means of another factor smaller than , as one my see by the use of the following theorem.
II. An integer is prime if it has no prime factor equal or less than , where is the greatest integer whose square is equal to or less than .
Since has no prime factor less than , it follows from theorem I that is has no factor but unity less than . Hence, if is not prime it must be the product of two numbers each greater than ; and hence it must be equal to or greater than . This contradicts the hypothesis on ; and hence we conclude that is prime.
EXERCISE
I. The number of primes is infinite.
We shall prove this theorem by supposing that the number of primes is not infinite and showing that this leads to a contradiction. If the number of primes is not infinite there is a greatest prime number, which we shall denote by . Then form the number
Now by theorem 1 of § 1.3 has a prime divisor . But every non-unit divisor of is obviously greater than . Hence is greater than , in contradiction to the conclusion that is the greatest prime. Thus the proof of the theorem is complete.
In a similar way we may prove the following theorem:
II. Among the integers of the arithmetic progression , , , , , there is an infinite number of primes.
If the number of primes in this sequence is not infinite there is a greatest prime number in the sequence; supposing that this greatest prime number exists we shall denote it by . Then the number ,
is not divisible by any number less than or equal to . This number , which is of the form , has a prime factor. If this factor is of the form we have already reached a contradiction, and our theorem is proved. If the prime is of the form the complementary factor is of the form . Every prime factor of is greater than . Hence we may treat as we did , and with a like result. Hence we must ultimately reach a prime factor of the form ; for, otherwise, we should have expressed as a product of prime factors all of the form —a result which is clearly impossible. Hence we must in any case reach a contradiction of the hypothesis. Thus the theorem is proved.
The preceding results are special cases of the following more general theorem:
III. Among the integers of the arithmetic progression , , , , , there is an infinite number of primes, provided that and are relatively prime.
For the special case given in theorem II we have an elementary proof; but for the general theorem the proof is difficult. We shall not give it here.
EXERCISES
If and are any two positive integers there exist integers and , , such that
If is a multiple of the theorem is at once verified, being in this case . If is not a multiple of it must lie between two consecutive multiples of ; that is, there exists a such that
Hence there is an integer , , such that . In case is greater than it is evident that and . Thus the proof of the theorem is complete.
I. If is a prime number and is any integer, then either is divisible by or is prime to .
This theorem follows at once from the fact that the only divisors of are and .
II. The product of two integers each less than a given prime number is not divisible by .
Let be a number which is less than and suppose that is a number less than such that is divisible by , and let be the least number for which is so divisible. Evidently there exists an integer such that
Then . Since is divisible by it is clear that is divisible by ; so is also; and hence their difference , , is divisible by . That is, the product of by an integer less than is divisible by , contrary to the assumption that is the least integer such that is divisible by . The assumption that the theorem is not true has thus led to a contradiction; and thus the theorem is proved.
III. If neither of two integers is divisible by a given prime number their product is not divisible by .
Let and be two integers neither of which is divisible by the prime . According to the fundamental theorem of Euclid there exist integers , , , such that
Then
If now we suppose to be divisible by we have divisible by . This contradicts II, since and are less than . Hence is not divisible by .
By an application of this theorem to the continued product of several factors, the following result is readily obtained:
IV. If no one of several integers is divisible by a given prime their product is not divisible by .
I. Every integer greater than unity can be represented in one and in only one way as a product of prime numbers.
In the first place we shall show that it is always possible to resolve a given integer greater than unity into prime factors by a finite number of operations. In the proof of theorem I, § 1.3, we showed how to find a prime factor of by a finite number of operations. Let us write
If is not unity we may now find a prime factor of . Then we may write
If is not unity we may apply to it the same process as that applied to and thus obtain a third prime factor of . Since it is clear that after a finite number of operations we shall arrive at a decomposition of into prime factors. Thus we shall have
where , , , are prime numbers. We have thus proved the first part of our theorem, which says that the decomposition of an integer (greater than unity) into prime factors is always possible.
Let us now suppose that we have also a decomposition of into prime factors as follows:
Then we have
Now divides the first member of this equation. Hence it also divides the second member of the equation. But is prime; and therefore by theorem IV of the preceding section we see that divides some one of the factors ; we suppose that is a factor of . It must then be equal to . Hence we have
By the same argument we prove that is equal to some , say . Then we have
Evidently the process may be continued until one side of the equation is reduced to . The other side must also be reduced to at the same time. Hence it follows that the two decompositions of are in fact identical.
This completes the proof of the theorem.
The result which we have thus demonstrated is easily the most important theorem in the theory of integers. It can also be stated in a different form more convenient for some purposes:
II. Every non-unit positive integer can be represented in one and in only one way in the form
where , , , are different primes and , , , are positive integers.
This comes immediately from the preceding representation of in the form by combining into a power of all the primes which are equal to .
COROLLARY 1. If and are relatively prime integers and is divisible by both and , then is divisible by .
COROLLARY 2. If and are each prime to then is prime to .
COROLLARY 3. If is prime to and is divisible by , then is divisible by .
The following theorem is an immediate corollary of the results in the preceding section:
I. All the divisors of ,
are of the form
and every such number is a divisor of .
From this it is clear that every divisor of is included once and only once among the terms of the product
when this product is expanded by multiplication. It is obvious that the number of terms in the expansion is . Hence we have the theorem:
II. The number of divisors of is .
Again we have
Hence,
III. The sum of the divisors of is
In a similar manner we may prove the following theorem:
IV. The sum of the powers of the divisors of is
EXERCISES
Let and be two positive integers such that is greater than . Then, according to the fundamental theorem of Euclid, we can form the set of equations
If is a multiple of we write , , in the above equations.
DEFINITION. The process of reckoning involved in determining the above set of equations is called the Euclidian Algorithm.
I. The number to which the Euclidian algorithm leads is the greatest common divisor of and .
In order to prove this theorem we have to show two things:
1) That is a divisor of both and ;
2) That the greatest common divisor of and is a divisor of .
To prove the first statement we examine the above set of equations, working from the last to the first. From the last equation we see that is a divisor of . Using this result we see that the second member of next to the last equation is divisible by Hence its first member must be divisible by . Proceeding in this way step by step we show that and , and finally that and , are divisible by .
For the second part of the proof we employ the same set of equations and work from the first one to the last one. Let be any common divisor of and . From the first equation we see that is a divisor of . Then from the second equation it follows that is a divisor of . Proceeding in this way we show finally that is a divisor of . Hence any common divisor, and in particular the greatest common divisor, of and is a factor of .
This completes the proof of the theorem.
COROLLARY. Every common divisor of and is a factor of their greatest common divisor.
II. Any number in the above set of equations is the difference of multiples of and .
From the first equation we have
so that the theorem is true for . We shall suppose that the theorem is true for every subscript up to and prove it true for the subscript . Thus by hypothesis we have1
Substituting in the equation
we have a result of the form
From this we conclude at once to the truth of the theorem.
Since is the greatest common divisor of and , we have as a corollary the following important theorem:
III. If is the greatest common divisor of the positive integers and , then there exist positive integers and such that
If we consider the particular case in which and are relatively prime, so that , we see that there exist positive integers and such that . Obviously, if and have a common divisor , greater than , there do not exist integers and satisfying this relation; for, if so, would be a divisor of the first member of the equation and not of the second. Thus we have the following theorem:
IV. A necessary and sufficient condition that and are relatively prime is that there exist integers and such that .
The theory of the greatest common divisor of three or more numbers is based directly on that of the greatest common divisor of two numbers; consequently it does not require to be developed in detail.
EXERCISES
I. The common multiples of two or more numbers are the multiples of their least common multiple.
This may be readily proved by means of the unique factorization theorem. The method is obvious. We shall, however, give a proof independent of this theorem.
Consider first the case of two numbers; denote them by and and their greatest common divisor by . Then we have
where and are relatively prime integers. The common multiples sought are multiples of and are all comprised in the numbers , where is any integer whatever. In order that these numbers shall be multiples of it is necessary and sufficient that shall be a multiple of ; that is, that shall be a multiple of ; that is, that shall be a multiple of , since and are relatively prime. Writing we have as the multiples in question the set where is an arbitrary integer. This proves the theorem for the case of two numbers; for is evidently the least common multiple of and .
We shall now extend the proposition to any number of integers . The multiples in question must be common multiples of and and hence of their least common multiple . Then the multiples must be multiples of and and hence of their least common multiple . But is evidently the least common multiple of . Continuing in a similar manner we may show that every multiple in question is a multiple of , the least common multiple of . And evidently every such number is a multiple of each of the numbers .
Thus the proof of the theorem is complete.
When the two integers and are relatively prime their greatest common divisor is and their least common multiple is their product. Again if is prime to both and it is prime to their product ; and hence the least common multiple of is in this case . Continuing in a similar manner we have the theorem:
II. The least common multiple of several integers, prime each to each, is equal to their product.
EXERCISES
I. If and are positive integers and , then can be represented in terms of in one and in only one way in the form
where
That such a representation of exists is readily proved by means of the fundamental theorem of Euclid. For we have
If the value of given in the last of these equations is substituted in the second last we have
This with the preceding gives
Substituting from this in the preceding and continuing the process we have finally
a representation of in the form specified in the theorem.
To prove that this representation is unique, we shall suppose that has the representation
where
and show that the two representations are identical. We have
Then
The first member is divisible by . Hence the second is also. But the second member is less than in absolute value; and hence, in order to be divisible by , it must be zero. That is, . Dividing the equation through by and transposing we have
It may now be seen that . It is evident that this process may be continued until either the ’s are all eliminated from the equation or the ’s are all eliminated. But it is obvious that when one of these sets is eliminated the other is also. Hence, . Also, every equals the which multiplies the same power of as the corresponding . That is, the two representations of are identical. Hence the representation in the theorem is unique.
From this theorem it follows as a special case that any positive integer can be represented in one and in only one way in the scale of 10; that is, in the familiar Hindoo notation. It can also be represented in one and in only one way in any other scale. Thus
Or, using a subscript to denote the scale of notation, this may be written
For the case in which (of theorem I) is equal to 2, the only possible values for the ’s are 0 and 1. Hence we have at once the following theorem:
II. Any positive integer can be represented in one and in only one way as a sum of different powers of 2.
EXERCISES
Let be any positive integer and any prime number not greater than . We inquire as to what is the highest power of the prime contained in .
In solving this problem we shall find it convenient to employ the notation
to denote the greatest integer such that . With this notation it is evident that we have
and more generally
If now we use to denote the index of the highest power of contained in an integer , it is clear that we have
since only multiples of contain the factor . Hence
Applying the same process to the -function in the second member and remembering relation (1) it is easy to see that we have
the series on the right containing evidently only a finite number of terms different from zero. Thus we have the theorem:
I. The index of the highest power of a prime contained in is
The theorem just obtained may be written in a different form, more convenient for certain of its applications. Let be expressed in the scale of in the form
where
Then evidently
Adding these equations member by member and combining the second members in columns as written, we have
Comparing this result with theorem I we have the following theorem:
II. If is represented in the scale of in the form
where is prime and
then the index of the highest power of contained in is
Note the simple form of the theorem for the case ; in this case the denominator is unity.
We shall make a single application of these theorems by proving the following theorem:
III. If , , , , are any positive integers such that , then
(A) |
is an integer.
Let be any prime factor of the denominator of the fraction (A). To prove the theorem it is sufficient to show that the index of the highest power of contained in the numerator is at least as great as the index of the highest power of contained in the denominator. This index for the denominator is the sum of the expressions
(B) |
The corresponding index for the numerator is
(C) |
But, since , it is evident that
From this and the expressions in (B) and (C) it follows that the index of the highest power of any prime in the numerator of (A) is equal to or greater than the index of the highest power of p contained in its denominator. The theorem now follows at once.
COROLLARY. The product of consecutive integers is divisible by .
EXERCISES
as an integer.
is an integer. Generalize to integers .
is an integer ( being positive integers). Generalize to the case of integers .
We have seen that the number of primes is infinite. But the integers which have actually been identified as prime are finite in number. Moreover, the question as to whether a large number, as for instance , is prime is in general very difficult to answer. Among the large primes actually identified as such are the following:
No analytical expression for the representation of prime numbers has yet been discovered.
Fermat believed, though he confessed that he was unable to prove, that he had found such an analytical expression inEuler showed the error of this opinion by finding that is a factor of this number for the case when .
The subject of prime numbers is in general one of exceeding difficulty. In fact it is an easy matter to propose problems about prime numbers which no one has been able to solve. Some of the simplest of these are the following:
up | next | prev | top |