Elementary Number Theory: An Algebraic Approach
()
About this ebook
Ethan D. Bolker teaches mathematics and computer science at the University of Massachusetts, Boston.
Related to Elementary Number Theory
Titles in the series (100)
A History of Mathematical Notations Rating: 4 out of 5 stars4/5Analytic Inequalities Rating: 5 out of 5 stars5/5First-Order Partial Differential Equations, Vol. 2 Rating: 0 out of 5 stars0 ratingsInfinite Series Rating: 4 out of 5 stars4/5Laplace Transforms and Their Applications to Differential Equations Rating: 5 out of 5 stars5/5Theory of Approximation Rating: 0 out of 5 stars0 ratingsMethods of Applied Mathematics Rating: 3 out of 5 stars3/5A Catalog of Special Plane Curves Rating: 2 out of 5 stars2/5Dynamic Probabilistic Systems, Volume II: Semi-Markov and Decision Processes Rating: 0 out of 5 stars0 ratingsMathematics in Ancient Greece Rating: 5 out of 5 stars5/5The Calculus Primer Rating: 0 out of 5 stars0 ratingsFirst-Order Partial Differential Equations, Vol. 1 Rating: 5 out of 5 stars5/5History of the Theory of Numbers, Volume II: Diophantine Analysis Rating: 0 out of 5 stars0 ratingsAdvanced Calculus: Second Edition Rating: 5 out of 5 stars5/5Calculus Refresher Rating: 3 out of 5 stars3/5Calculus: An Intuitive and Physical Approach (Second Edition) Rating: 4 out of 5 stars4/5Differential Geometry Rating: 5 out of 5 stars5/5Topology for Analysis Rating: 4 out of 5 stars4/5An Introduction to Lebesgue Integration and Fourier Series Rating: 0 out of 5 stars0 ratingsNumerical Methods Rating: 5 out of 5 stars5/5Theory of Games and Statistical Decisions Rating: 4 out of 5 stars4/5Mathematics for the Nonmathematician Rating: 4 out of 5 stars4/5Differential Forms with Applications to the Physical Sciences Rating: 5 out of 5 stars5/5Geometry: A Comprehensive Course Rating: 4 out of 5 stars4/5Fourier Series and Orthogonal Polynomials Rating: 0 out of 5 stars0 ratingsElementary Matrix Algebra Rating: 3 out of 5 stars3/5The History of the Calculus and Its Conceptual Development Rating: 4 out of 5 stars4/5Applied Multivariate Analysis: Using Bayesian and Frequentist Methods of Inference, Second Edition Rating: 0 out of 5 stars0 ratingsVectors and Their Applications Rating: 0 out of 5 stars0 ratingsAn Adventurer's Guide to Number Theory Rating: 4 out of 5 stars4/5
Related ebooks
Axiomatic Set Theory Rating: 4 out of 5 stars4/5Introductory Non-Euclidean Geometry Rating: 0 out of 5 stars0 ratingsTopics in Number Theory, Volumes I and II Rating: 5 out of 5 stars5/5Number Theory Rating: 4 out of 5 stars4/5An Introduction to Algebraic Structures Rating: 2 out of 5 stars2/5Elliptic Tales: Curves, Counting, and Number Theory Rating: 4 out of 5 stars4/5Sets, Sequences and Mappings: The Basic Concepts of Analysis Rating: 0 out of 5 stars0 ratingsThe Philosophy of Set Theory: An Historical Introduction to Cantor's Paradise Rating: 4 out of 5 stars4/5A Concept of Limits Rating: 4 out of 5 stars4/5Advanced Number Theory Rating: 0 out of 5 stars0 ratingsFundamentals of Number Theory Rating: 5 out of 5 stars5/5Naive Set Theory Rating: 4 out of 5 stars4/5Introductory Discrete Mathematics Rating: 4 out of 5 stars4/5Elements of Abstract Algebra Rating: 4 out of 5 stars4/5Algebraic Extensions of Fields Rating: 0 out of 5 stars0 ratingsFirst Course in Mathematical Logic Rating: 3 out of 5 stars3/5The History of the Calculus and Its Conceptual Development Rating: 4 out of 5 stars4/5Introduction to the Theory of Sets Rating: 3 out of 5 stars3/5Set Theory: The Structure of Arithmetic Rating: 5 out of 5 stars5/5Cohomology and Differential Forms Rating: 5 out of 5 stars5/5Algebraic Number Theory Rating: 0 out of 5 stars0 ratingsFinite-Dimensional Vector Spaces: Second Edition Rating: 0 out of 5 stars0 ratingsThe Classical Groups: Their Invariants and Representations (PMS-1) Rating: 4 out of 5 stars4/5Elementary Theory of Numbers Rating: 4 out of 5 stars4/5Introduction to Mathematical Thinking: The Formation of Concepts in Modern Mathematics Rating: 4 out of 5 stars4/5Logic in Elementary Mathematics Rating: 0 out of 5 stars0 ratingsGeneral Topology Rating: 4 out of 5 stars4/5A Course on Group Theory Rating: 4 out of 5 stars4/5Lie Groups for Pedestrians Rating: 4 out of 5 stars4/5Extremal Graph Theory Rating: 3 out of 5 stars3/5
Mathematics For You
Calculus Made Easy Rating: 4 out of 5 stars4/5Standard Deviations: Flawed Assumptions, Tortured Data, and Other Ways to Lie with Statistics Rating: 4 out of 5 stars4/5Quantum Physics for Beginners Rating: 4 out of 5 stars4/5My Best Mathematical and Logic Puzzles Rating: 5 out of 5 stars5/5Algebra - The Very Basics Rating: 5 out of 5 stars5/5Basic Math & Pre-Algebra For Dummies Rating: 4 out of 5 stars4/5Real Estate by the Numbers: A Complete Reference Guide to Deal Analysis Rating: 0 out of 5 stars0 ratingsLogicomix: An epic search for truth Rating: 4 out of 5 stars4/5The Thirteen Books of the Elements, Vol. 1 Rating: 0 out of 5 stars0 ratingsThe Everything Guide to Algebra: A Step-by-Step Guide to the Basics of Algebra - in Plain English! Rating: 4 out of 5 stars4/5The Little Book of Mathematical Principles, Theories & Things Rating: 3 out of 5 stars3/5Game Theory: A Simple Introduction Rating: 4 out of 5 stars4/5Mental Math Secrets - How To Be a Human Calculator Rating: 5 out of 5 stars5/5The Everything Everyday Math Book: From Tipping to Taxes, All the Real-World, Everyday Math Skills You Need Rating: 5 out of 5 stars5/5Algebra I Workbook For Dummies Rating: 3 out of 5 stars3/5Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game - Updated Edition Rating: 4 out of 5 stars4/5Algebra I For Dummies Rating: 4 out of 5 stars4/5See Ya Later Calculator: Simple Math Tricks You Can Do in Your Head Rating: 4 out of 5 stars4/5Flatland Rating: 4 out of 5 stars4/5Relativity: The special and the general theory Rating: 5 out of 5 stars5/5The Golden Ratio: The Divine Beauty of Mathematics Rating: 5 out of 5 stars5/5Basic Math Notes Rating: 5 out of 5 stars5/5The Math of Life and Death: 7 Mathematical Principles That Shape Our Lives Rating: 4 out of 5 stars4/5Is God a Mathematician? Rating: 4 out of 5 stars4/5ACT Math & Science Prep: Includes 500+ Practice Questions Rating: 3 out of 5 stars3/5
Reviews for Elementary Number Theory
0 ratings0 reviews
Book preview
Elementary Number Theory - Ethan D. Bolker
parents
1
Linear Diophantine Equations
We shall begin our study of number theory not with the topic announced in the title of this first chapter but with an empirical investigation of a problem studied and solved by Fermat.
1. SUMS OF SQUARES
Which positive integers can be written as sums of two integral squares? Let us call such integers representable; the first few representable integers are 1, 2, 4, 5, 8, 9, 10, 13, and 16. What pattern does the sequence of representable integers form? How can we decide whether a given integer is representable? We need more data to make intelligent guesses.
The representable integers less than 100 appear in boldface in Table 1. The arrangement of that table in rows of eight allows us to guess a part of the pattern; the third, sixth, and seventh columns seem free of representable integers. The reader is invited (in Problem 6.1) to prove that that phenomenon continues. It is harder to predict which integers in the other columns are representable. Some hints will be found in Problems 6.2 and 6.3.
Some integers can be represented more than one way. The smallest such is 25 = 5² + 0² = 4² + 3²; the others less than 100 are 50, 65, and 85.
TABLE 1a
The least integer representable three ways is
Counting the number of ways n can be represented gives clues to the pattern of representable integers. (See Problems 6.2 and 6.3.)
The recorded history of the study of representable integers starts in about 250 A.D. with Diophantos. Problems in which integral values of the unknowns are sought are called Diophantine in his honor. In the seventeenth century Fermat gave, as a simple function of n, the number of solutions to the Diophantine equation x² + y² = n and thus answered all the questions we have raised about the representability of integers. His answer is our Theorem 36.3.
In the preface to the collected works of Eisenstein, Gauss wrote of number theory that ... important propositions, with the impress of simplicity upon them, are often easily discoverable by induction and yet are of so profound a character that we cannot find their demonstration until after many vain attempts; and even then, when we do suceed, it is often by some tedious and artificial process, while the simpler methods may long remain concealed.
The argument which stretches from here to our proof of Fermat’s theorem on representable integers and beyond is not the shortest possible, but by lengthening and modernizing it we have freed it of many of the artificial processes
and revealed the simpler methods
to which Gauss refers.
2. DIVISIBILITY AND UNIQUE FACTORIZATION
The simplest nontrivial Diophantine equation,
(1)
has a solution if and only if a divides b; when that occurs we write a | b and say too that a is a factor or divisor of b, while b is a multiple of a. Since a0 = 0, we have a | 0 for every a. An integer p other than 0, 1, or – 1 is prime when its only divisors are ± 1 and ±p. If n ≠ 0, ±1 is not prime, it is composite.
2.1 Theorem. Every nonzero integer other than ±1 can be written uniquely
as a product of primes.
The uniqueness is qualified by the quotation marks because, for example,
6 = ( – 2)( – 3) = 3 · 2
and 2, – 2, 3, and – 3 are all primes. What we mean by uniquely
is, of course, that if n = ± p1 ··· pr = ±q1 ··· qs where the pi and the qj are primes, then r = s, and the sequence |p1|, ..., |pr| is a permutation of the sequence |q1|,..., |qs|.
In Appendix 1 we prove that Lemma 2.2 below implies Theorem 2.1, the fundamental theorem of arithmetic. We repeat here some of the auxiliary definitions and intermediate steps in that argument.
2.2 Lemma. Given integers m and n ≠ 0 there are unique integers q and r with 0 ≤ r < |n| for which
m = qn + r.
This is simply a formal assertion of the possibility of division with remainder
in Z, the ring of integers.
2.3 Definition. The integer d is a greatest common divisor of a and b in Z if d | a and d | b, and if whenever c | a and c | b, then c | d.
2.4 Theorem. Every pair 〈a, b〉 of integers except 〈0, 0〉 has a greatest common divisor d. The Diophantine equation
(2)
has a solution.
There are several algorithms for computing d and solving Eq. (2) in a predictable finite number of steps. The most common, the Euclidean algorithm, is illustrated in Example 15 of Appendix 1.
If d is a greatest common divisor of a and b, then so is – d; no other integer enjoys this privilege. We shall write (a, b) for the positive greatest common divisor of a and b and 〈a, b〉 for the ordered pair formed by a and b. Thus (4, 6) = 2 and (25, -4) = 1. If a ≠ 0 then (a, 0) = |a| because the common divisors of a and 0 are just the divisors of a; (0, 0) is undefined.
2.5 Definition. The integers a and b are relatively prime, or coprime, if and only if (a, b) = 1.
If p is prime and a ≠ ± 1, then p and a are relatively prime if and only if p a, that is, p does not divide a.
2.6 Theorem. If a | bc and (a, b) = 1, then a | c. In particular, if a prime divides a product, then it divides one of the factors. (See Appendix 1, Theorem 16.)
2.7 Definition. An integer m ≠ 0 is a common multiple of a and b if a | m and b | m. If neither a nor b is 0, then |ab| is a common multiple, so among the positive common multiples there is a least, which we write
l.c.m. {a, b}.
2.8 Theorem. If ab > 0, then the least common multiple of a and b is ab/(a, b); the least common multiple divides any common multiple.
3. THE DIOPHANTINE EQUATION ax + by = c
The second simplest Diophantine equation is ax + by = c which one often meets in secondary school in a form such as: " How many dimes and quarters make n cents ? " That banking problem is clearly hopeless unless 5 | n.
3.1 Theorem. The Diophantine equation
(3)
has solutions if and only if (a, b)|c. When solutions exist, they are all given by
(4)
where
(5)
and n is any integer.
Proof. Only if
is obvious. To show that Eqs. (4) give all the solutions suppose (a, b) | c and that 〈x, y〉 is a solution to Eq. (3). Let a’ = a/(a, b); b’ = b/(a, b); and c’ = c/(a, b). Use Theorem 2.4 to find a solution 〈x0, y0〉 to Eq. (5). Then
(6)
Since (a’, b’) = 1 (Problem 6.11), Eq. (6) implies
a’|y – cy0
so that
y = c’y0 + a’n
for some integer n. Then
a’(x – c’x0) = – a’b’n
so
(7)
Moreover, if x and y are defined by Eqs. (4) then 〈x, y〉 solves Eq. (3).
4. THE DIOPHANTINE EQUATION a1x1 + ··· + anxn = c
Let a1, ..., an be integers at least one of which is not 0. A greatest common divisor d of a1, ..., an is a common divisor which is a multiple of every common divisor. Write (a1, ..., an) for the unique positive greatest common divisor the proof of whose existence is Problem 6.13. Now we generalize Theorem 3.1.
4.1 Theorem. The Diophantine equation
(8)
(some ai ≠ 0) has a solution if and only if (a1, ... , an) | c.
Proof. When n = 2, this is just Theorem 3.1, so our induction on n, the number of variables, begins well. Suppose n > 2. We shall show that Eq. (8) can be solved assuming that similar equations in n – 1 variables can be solved. To this end observe that (a1, a2, ..., an) = ((a1, a2), a3,..., an) (Problem 6.14). Then use Theorem 3.1 and the inductive hypothesis to find integers y1, y2, x, x3 ,..., xn satisfying
a1y1 + a2y2 = (a1, a2)
and
(a1, a2)x + a3x3 + ··· + anxn = c.
If we set x1 = y1 x and x2 = y2 x, then 〈x1,..., xn〉 solves Eq. (8).
5. THE INFINITUDE OF THE PRIMES
This section contains some information on the way in which the primes are distributed in Z and introduces some techniques which we shall generalize in the next chapter. Euclid knew the following theorem.
5.1 Theorem. There are infinitely many primes.
Proof. Let P be the set of primes. Since 2 is prime, P is not empty. We shall show that no finite subset Q of P exhausts P. Suppose Q = {q1, ..., qn} is a nonempty subset of P. Let m = 1 + q1 ··· qn ≠ ± 1. The fundamental theorem of arithmetic implies that there is a prime p which divides m. Since no q1 divides m, p ∉ Q. That is, Q ≠ P, so P is infinite.
We can exploit this method to prove a little more. Lemma 2.2 implies that every integer n may be written in just one of the forms, 4k; 4k + 1; 4k + 2; or 4k + 3. Since 2 | 4k and 2 | 4k + 2, every odd prime is of the form 4k + 1 or 4k + 3. The following lemma is a very special case of a principle we shall introduce in Section 7.
5.2 Lemma. The product of integers of the form 4k + 1 is again of that form.
Proof. It clearly suffices to prove this lemma for the product of just two integers. Let n = 4k + 1 and n’ = 4k’ + 1. Then
5.3 Theorem. There are infinitely many primes of the form 4k + 3.
Proof. Let P be the set of such primes. Since 3 ∈ P, P is not empty. We shall show that no finite subset Q of P exhausts P. Suppose Q = {q1,..., qn} is a nonempty subset of P. Let
The fundamental theorem of arithmetic implies that m is a product of primes. Since m is odd, every prime divisor of m is odd. If all the prime divisors of m were of the form 4k + 1, then m would be of that form (Lemma 3.2), which is false. Therefore there is a prime p ∈ P which divides m. Since no qi divides m, p ∉ Q. That is Q ≠ P; P is infinite.
Note that we have not used the full strength of the fundamental theorem of arithmetic. We needed only the existence, not the uniqueness,
of a prime factorization of m to prove Theorems 5.1 and 5.3.
The technique we used to prove Theorem 5.3 fails to prove the infinitude of the primes of the form 4n + 1 since the analogue of Lemma 3.2 is false: (4 · 1 + 3)(4 · 0 + 3) = 7 · 3 = 21 = 4 · 5 + 1. In fact, the product of two numbers of the form 4k + 3 is always of the form 4k + 1. There are infinitely many primes of the form 4k + 1; we shall prove it in Section 12. Much more is known. A justly famous theorem of Dirichlet’s asserts that the arithmetic progression of numbers of the form ak + b contains infinitely many primes whenever a ≠ 0 and (a, b) = 1. Dirichlet’s theorem is beyond the scope of this book; we shall, however, prove several special cases.
6. PROBLEMS
6.1 Show that the third, sixth, and seventh columns of Table 1 remain free of representable integers.
6.2 Prove that 2n is representable when n is. Is the converse true?
6.3 Prove that mn is representable when m and n are. How many ways can mn be represented ?
6.4* Formulate some guesses about integers which can be represented as a sum of three squares. Show that column 7 in Table 1 contains no such integers. We shall show in Section 40 that every integer is a sum of four squares.
6.5 Show n(n – 1)(2n – 1) is always divisible by 6.
6.6 Prove that the Diophantine equation
3y² – 1 = x²
has no solutions. That is, 3y² – 1 is never a perfect square.
6.7 n n, then 24 | (n² + 23).
6.8 What is (3² · 5⁶ · 7³ · 17, 3²¹ · 5 · 13)? The answer is easily computed without the Euclidean algorithm and suggests a useful theorem for computing greatest common divisors when prime factorizations are known. That theorem simplifies some of the problems which follow.
6.9 Prove Theorem 2.8.
6.10 Prove: If (a, b) = 1 and ab is a square, then |a| and |b| are squares.
6.11 .
6.12 Use the fundamental theorem of arithmetic to show that the Diophantine equation nx² = y² has a solution if and only if n is a square. Deduce that √n is irrational unless n is a square.
6.13 Prove that n integers at least one of which is not zero have a greatest common divisor.