From the first equation, d 1 h; from the second, d1irz; etc. Thus we can take the d of the theorem to be Tk. Other examples are the long-division algorithm and the square-root algorithm. It is frequently important to know whether two integers a and b have a common factor larger than 1. The following properties of the GCD are easily derived either from the definition or from the Euclidean algorithm. Let there be n numbers aI, az, If a given integer is relatively prime to each of several others, it is relatively prime to their product.
It is not the only such pair, as we shall see in Section Evaluate the following: a ,, ; b ,, ; c ,,, Hint: Prove that each member of the alleged equation divides the other. Use property d in the text, and the preceding problem. Show that if c is any integer representable in this form, then Die. Use the method of the preceding problem to prove the existence and uniqueness of an appropriately defined GCD of several integers aI, Extend assertions b through e of the text to the case of several integers.
It is customary to allow products to contain only one fa! Assume it to be true for 2, 3,4, If a is prime, we are through. Hereafter p will be used to denote a positive prime number, unless otherwise specified. But a divides both ac and be, and hence the left side of this equation, and therefore a divides c. Proof; Suppose that plPIP Unique Factorization Theorem. Proof: We must show exactly the following. Thus the two representations for a were identical. As a preliminary step we note that if an integer n has the unique factorization property, and if a prime P divides n, then P actually occurs in the prime factorization of n; for otherwise we could write nip as a product of primes, not necessarily unique, and multiplying through by P would yield a second representation for n as a product of primes.
By the induction hypothesis, a has unique factorization, and since both PI and pi divide a, it follows from the preliminary remark that both of these primes must actually occur in the factorization of a. This contradiction shows that n has unique factorization, and it follows from the induction axiom that all integers larger than 1 have this property.
At this point the question might well be raised, why all the fuss about a theorem whose truth seems perfectly obvious? The answer is, of course, that it seems obvious only because one is accustomed to it from experience with the small integers, and that one therefore believes that it is also true for larger integers. But believing and knowing are not the same thing. It might be instructive to consider a situation rather similar to the one we have been concerned with, in which factorization is not unique.
We could say that an element of D is prime in D if it is larger than 1 and has no factors in D except itself and 1; thus the first few numbers which are prime in Dare 5, 9, 13, 17, 21, 29, It is now quite straightforward to show that every integer greater than 1 in D can be represen. The difficulty here is that D is not large enough, i.
There is also no reason to suppose that the full set of integers is large enough, until it has been proved to be the case. Use this fact to give different solutions to Problems 9 and 10, Section Show that every integer can be uniquely represented as the product of a square and a square-free number, the latter being an integer not divisible by the square of any prime.
Suppose that there are h primes not exceeding the positive integer x, so that rex.. How many square. How many squares not larger than x are there? Deduce that the sum of the positive divisors of n is tr. Use the latter result to give a new proof that T n is odd if and only if n is a square. Since x is to be an integer, t l8 - 22y must also be integral. What we have shown is that any solution x, y of the original equation must be of this form.
By substitution, it is immediately seen that every pair of numbers of this form constitutes a solution, so that we have a general solution of the equation. The same idea could be applied in the general case, but it is somewhat simpler to adopt a different approach. Since every solution of 1 is a solution of 2 and conversely, we have the following theorem. There are various ways of obtaining a particular solution. Sometimes one can be found by inspection; if not, the method explained at the beginning of the section may be used or, what is almost the same thing, the Euclidean algorithm may be applied to find a solution of the equation which results when the original equation is divided by a, b.
The latter process of successively eliminating the remainders in the Euclidean algorithm can be systematized, but we shall not do this here. There are many "word problems" which lead to linear Diophantine equations that must be solved in positive integers, since only such solutions have meaning for the original problem. Let us first assume that a and b have opposite signs. Hence, in this case, there are always infinitely many positive solutions of the equation. The situation is quite different when a and b have the same sign. We can suppose that a and b are both positive, since otherwise we can multiply through in the original equation by How many bicycles of each kind were ordered?
Let m and n be positive integers, with m o Note that so far it is only the existence of N a, b which is in question, and not its size. When Mr. Smith cashed a check for X dollars and y cents, he received instead y dollars and x cents, and found that he had two cents more than twice the proper amount.
Number Theory -- from Wolfram MathWorld
For how much was the check written? The definition is easily extended to the case of more than two numbers, just as for the GOD. Use this to give a second proof of part 3 of Theorem As we shall see, there are also many other instances in which a comparison must be made of the remainders after dividing each of two numbers a and b by a third, say m. Of course, if the remainders are the same, then ml a - b , and conversely, and this might seem to be an adequate notation.
This has nothing to do with geometric congruence, of course. The use of the symbol UE " is suggested by the similarity of the relation we are discussing to ordinary equality. Each of these two relations is an example of an equivalence relation, i. These are called the reflexive, symmetric, and transitive properties, respectively. Congruence modulo a fixed number m is an equivalence relation. If describe the equivalence classes.
Define the relation Elementary properties of congruences. One reaSon for the superiority of the congruence notation is that congruences can be combined in much the same way as can equations. Proof: These statements follow immediately from the definition. But [CHAP. Finally, if ml a - b , then also mlk a - b for every k. The situation is a little more complicated when we consider dividing both sides of a congruence by an integer.
What is clearly necessary is that the part of m which does not divide k should divide a-b. Proof: Theorem Theorem is basic to much of what follows in this chapter. As a first very sImple application of it, let us consider the well-known rule that a number is divisible by 9 if and only if the Sum of the digits in its decimal expansion is divisible by 9. This statement provides a partial check On the correctness of arithmetical operations, called "casting out nines," which amounts simply to verifying that the italicized assertion holds in particular cases.
Let where ao, Show that if d consecutive values of f i. Show that no square has a decimal expansion ending in More generally, find all possible two-digit endings for squares. Show that every square is congruent to 0 or 1 mod 8.
Formulate a general conjecture, and test it in some other cases. Show that every quadratic discriminant b2 - 4ac is congruent to 0 or 1 mod 4. Show that if x, 6 ,. When dealing with congruences modulo a fixed integer m, the set of all integers breaks down into m classes, called the residue classes mod m , such that any two elements of the same class are congruent and two elements from two different classes are incongruent. The residue clas.. For many purposes it is completely immaterial which element of One of these residue classes is used; for example, Theorem shows this to be the case when one considers the values modulo m of a polynomial with integral coefficients.
In these instances it suffices to consider an arbitrary set of representatives of the various residue classes; that is, a set consisting of One element of each residue class. Such a set at, a2, If al, a2, Proof: We show directly that properties a and b above hold for this new set. Let a solution be Xo. Since al, When we restrict ourselves to a particular residue system mod m , say 0, 1, This "modular" multiplication is perhaps new to the student, but "modular" addition is familiar to everyone through our systems of keeping time.
Division is carried out in the same way in Table b ; being able to do so depends on the fact that, excluding the first row and column in the body of the table, each of the numbers 1, 2, 3, 4 occurs exactly once in each row. With respect to division, a composite modulus is somewhat less satisfactory, because the fundamental principle is no longer valid that a product is zero only if one of the factors is zero.
We shall return to this question in Section Show that if the integers have any two of the following three properties, they also have the third, and hence constitute a complete residue system mod m : a If i? Prove Theorem by verifying a and c , rather than a and b as is done in the text. This is a set of integers aI, If aI, The proof is exactly parallel to that of Theorem A function with this property is called a multiplicative function.
For another example, see Problem 10, Section But their number is also the product of the number of values which x assumes and the number of values which Y assumes. Whenever the range of summation or multiplication consists of anything more complicated than all the integers of a certain interval, the description of the range is written entirely below the L or IT. Further examples occur in the proof of the next theorem.
We separate the integers between 1 and n inclusive into classes C dl , Show that if din, then so d lso n. Let n be positive. Consider separately the cases plb and ptb. Because of the analogy between congruences and equations, it is natural to ask about the solution of congruences involving one or more integral unknowns. For this reason it is customary, for such congruences, to list only the solutions between 0 and m - 1, inclusive, with the understanding that any x congruent to one of those listed is also a solution.
Similarly, when the number of roots of a certain congruence is mentioned, it is actually the number of residue classes that is meant. Attention must be given, however, to the modulus with respect to which the solutions are counted since, for example, the arithmetic progression When we list residue classes as solutions of a congruence, we are, in effect, doing exactly the same thing as when we solve an equation. Similarly, a solution of the congruence 5x 5 3 mod 7 is given by x 5 2 mod 7 ; thus the solution of a congruence is described by another congruence, where x appears alone on one side and the other side is free of x.
With these remarks in mind, let us proceed to the details. The simplest case to treat is the linear congruence in one unknown; that is, the congruence ax s b mod m. In particular, x is unique modulo mid. If this is the case, there are exactly a, m solutions mod m. If no solution can be found by inspection, then the simplest procedure is to convert the congruence to an equation and solve by the method given at the beginning of Section Hence x -4 mod 49 , and the two solutions of the original congruence are x:; -4,45 mod Theorem provides the answer to a question alluded to earlier, namely, When is division possible in arithmetic mod m?
If m is a prime p, then division by any number not in the residue class of 0 is possible, but for composite modulus this is not the case. Actually, it is customary not to use the fractional notation, but to refer instead to the solution of a linear congruence. In the modular case, however, all of the infinitely many "fractions" alb which make sense mod m are congruent to one or another of the elements of the finite set 0, 1, The solution of a linear congruence in more than one unknown can be effected by the successive solution of a usually large number of congruences in a single unknown.
The obviously necessary condition for solvability, that aI, For, assuming it satisfied, we can divide through by al, If aL Here 2, 7, 12 - 1. The general situation is described in the following theorem, which is easily proved by induction on the number of unknowns. It is obvious that such a system of n congruences will have no solution unless every pair taken from among them has a solution.
From the first of the congruences x ;;. Proof: The theorem is trivially true if there is only one congruence in the system. Solve the congruence 6x 3. Replace these two congruences in turn by a single congruence mod ml , with a new unknown. Note that once the numbers el, A famous theorem of P. The proof is rather difficult. Treat separately the cases pil and ptl. As is well known, the equality sign is used between polynomials in two essentially different ways. In the equation for example, it means that the left- and right-hand sides are identical polynomials, i. If we temporarily refer to the first as algebraic equality, and to the second as numerical equality, there is the following connection between them: if two polynomials are algebraically equal, they are also numerically equal for every value of x, and if two polynomials are numerically equal for every value of x or even for infinitely many values of x , then they are algebraically equal.
The congruence symbol is also used in two different ways, to relate polynomials. This meaning of the congruence symbol is usually intended when there is no reference to numerical values of x, or to roots or solutions of the congruence. The other meaning of the symbol is that x is a number for which the numerical values f x and II x are congruent mod m. There are other ways as well in which polynomial congruences behave differently from polynomial equations.
It is a theorem though possibly not one familiar to the reader that every polynomial with integral coefficients factors in a unique way into irreducible polynomials with integral coefficients.
You might also Like...
But there is not much to be done when there are too many solutions. The reverse situation, in which there are too few solutions, also occurs, of course. These examples show also that the strong distinction between real and complex numbers sometimes disappears in this "modular" arithmetic, since -1 already has a square root mod 5!
It turns out that some degree of order returns if we restrict attention to congruences with prime moduli: polynomials have unique factorization, they have no more roots than the degree would indicate, etc. For this reason we shall frequently consider theorems valid only for this particular case, although some, such as the following one, are true in general.
Since the leading coefficient in the divisor is 1, no fractions will ever be encountered in the process. Assume that every congruence of degree n - 1 has at most n - 1 solutions, and that a is a root of the original congruence. Let f x be apolynomial of degree n, with integral coefficients. Show that if n 1 consecutive values of! Problem 1, Section Consider d x - do x.
See Problem 12, Section Find an example of polynomials a x and b x which are relatively prime mod p but not mod q , for suitable primes p and q. The general problem of higher-degree congruences is too difficult for further development here, but we can obtain some information in an elementary way in the special case of quadratic congruences. Analogous definitions hold for nthpower residues and nonresidues.
This linear congruence is always solvable, since pfb, and the solution is unique if we require that it also be one of the numbers 1, 2, For fixed a, the numbers band b' will be called associates. We must distinguish two cases, depending on whether some b is associated with itself or not. By Lagrange's theorem there are no others, so that for all b different from bi and p - bI , we find that b is different from its associate h'. Thus if a is a quadratic residue of p, the integers 1, Here a is called the "first entry," and p the "second entry.
If P is prime, then p - I! The sequence of powers of a fixed positive integer a is a special case of the more general geometric progressions studied in algebra. We shall now study the sequence which results when the powers are all reduced to their least positive remainders mod m , where m is an integer relatively prime to a.
Here again, as in the preceding chapter, there are problems whose solutions for composite modulus are too complicated for inclusion in this text, and these will be discussed only for prime modulus. The reader should take care to be aware of this restriction whenever it is present. We begin with a specific case, the sequence of powers of 2, reduced mod In other words, the sequence is periodic from the beginning, with period 8.
To see this, note first that while there are infinitely many powers of a, there are only the m integers 0, 1, Moreover, 1, which is the first element of the sequence, is also the first number to repeat. Again we have all divisors of a number as period lengths, but this time the number is not m - 1. We now prove the general theorems bearing on these data. If pta, then aP - Since! Proof: The assertion follows immediately from Theorems and It is convenient to prove here a theorem which we shall use in the next section, and which, in a certain sense, generalizes Fermat's theorem. The following theorem introduces other polynomials having the maximum numbers of roots.
Since it can have no more than this number, it must have exactly d solutions Deduce that there are infinitely many primes congruent to 1 modulo any fixed power of 2. Since we obtain t d t'. This is a special case of the next theorem. If any integer belongs to t mod p , then exactly q; t incongruent numbers belong to t mod p.
- Navigation menu.
- Chained By Fear (The Death Wizard Chronicles Book 2);
- Account Options!
- Nathans Best Christmas Ever! (Christmas Books for Kids).
- History of the Theory of Numbers, Volume II: Diophantine Analysis by Leonard Eugene Dickson?
- Refine your editions:.
If tl p - 1 , there are q; t incongruent numbers mod p which belong to t mod p. Proof: Let d rurt over the divisors of p - 1, and for each such d let ", d be the number of integers among 1, 2, By Theorem and Fermat's theorem, each of the integers 1, 2, As noted earlier, for example, the primitive roots of 19 are 2, 3, 10, 13, 14, The importance of this notion lies in the fact that if g is such a primitive root, then its powers, 2 'I' m g,g, Thus we have a convenient way of representing all the elements of a reduced residue system, some implications of which are to be found later in this chapter and in the problems.
There are exactly cp p - 1 primitive roots of a prime p. The question of just which moduli have primitive roots is not altogether simple. Without going into details of the proof, we record the answer: the numbers having primitive roots are exactly those of the forms 2, 4, pa, 2p"', where p is any odd prime.
History of the Theory of Numbers: Volume II; Diophantine Analysis: 2 (Dover Books on Mathematics)
We shall use q as a symbol for these numbers throughout the remainder of the present chapter. The problem of actually finding a primitive root, for large modulus, has not been solved, in the sense that no simple algorithm leads straight to a solution. For given modulus q, it is, of course, a finite problem which can be solved by successively testing the clements of a reduced residue system. A slightly more rapid method is indicated in Problem 3 at the end of the next section, but this is also laborious for large q, particularly if cp q has many distinct prime divisors.
Show that if p 1 mod 4 and g is a primitive root of p, then so is -g. Show that if q has primitive roots, there are 6. Find all primitive roots of Find a primitive root of 23 and then, using Theorem , all primitive roots of Let q be a number having primitive roots and let g be one of them. Then the numbers g, g2,. The relation between a number a and the exponent of a power of g which is congruent to a mod q is very similar to the relation between an ordinary positive real number x and its logarithm.
This exponent is called an index of a to the base g, and written "indo a". Since 2 is a primitive root of 9, we construct the table as before: n: 2 ind n: 1 Thus ind x 4 8 7 5 1 2 3 4 5 6 Such a criterion has the disadvantage that it requires knowledge of the value of ind c, and for this reason the following is more useful. Let q be a number having primitive roots. Note the connection with Problem 3, Section Much of the content of the preceding chapters depends, in the end, on the division theorem, Theorem We now return to this theorem as the source of yet another important range of ideas in number theory.
New York: Dover, c. Dudley, U. Elementary Number Theory. San Francisco, CA: W. Freeman, Friedberg, R. An Adventurer's Guide to Number Theory. Gauss, C. Disquisitiones Arithmeticae. Goldman, J. Guy, R. Unsolved Problems in Number Theory, 3rd ed. Hardy, G. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, New York: Chelsea, Hasse, H. Berlin: Springer-Verlag, Herkommer, M. Number Theory: A Programmer's Guide. New York: McGraw-Hill, Ireland, K. Kato, K. Number Theory 1: Fermat's Dream.
Teoría de números
Washington, DC: Math. Koblitz, N. A Course in Number Theory and Cryptography. Landau, E. Elementary Number Theory, 2nd ed.
Lang, S. Algebraic Number Theory, 2nd ed. Lenstra, H. Computational Methods in Number Theory, 2 vols. Amsterdam: Mathematisch Centrum, LeVeque, W. Fundamentals of Number Theory. Handbook of Number Theory. Mollin, R. Algebraic Number Theory. Fundamental Number Theory with Applications. Niven, I. Ogilvy, C. Excursions in Number Theory. This second volume in the series, which is suitable for upper-level undergraduates and graduate students, is devoted to the subject of diophantine analysis.
It can be read independently of the preceding volume, which explores divisibility and primality, and volume III, which examines quadratic and higher forms. Featured topics include polygonal, pyramidal, and figurate numbers; linear diophantine equations and congruences; partitions; rational right triangles; triangles, quadrilaterals, and tetrahedra; the sums of two, three, four, and n squares; the number of solutions of quadratic congruences in n unknowns; Liouville's series of eighteen articles; the Pell equation; squares in arithmetical or geometrical progression; equations of degrees three, four, and n; sets of integers with equal sums of like powers; Waring's problem and related results; Fermat's last theorem; and many other related subjects.