eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
The power and properties of numbers, from basic addition and sums of squares to cutting-edge theory
We use addition on a daily basis—yet how many of us stop to truly consider the enormous and remarkable ramifications of this mathematical activity? Summing It Up uses addition as a springboard to present a fascinating and accessible look at numbers and number theory, and how we apply beautiful numerical properties to answer math problems. Mathematicians Avner Ash and Robert Gross explore addition's most basic characteristics as well as the addition of squares and other powers before moving onward to infinite series, modular forms, and issues at the forefront of current mathematical research.
Ash and Gross tailor their succinct and engaging investigations for math enthusiasts of all backgrounds. Employing college algebra, the first part of the book examines such questions as, can all positive numbers be written as a sum of four perfect squares? The second section of the book incorporates calculus and examines infinite series—long sums that can only be defined by the concept of limit, as in the example of 1+1/2+1/4+. . .=? With the help of some group theory and geometry, the third section ties together the first two parts of the book through a discussion of modular forms—the analytic functions on the upper half-plane of the complex numbers that have growth and transformation properties. Ash and Gross show how modular forms are indispensable in modern number theory, for example in the proof of Fermat's Last Theorem.
Appropriate for numbers novices as well as college math majors, Summing It Up delves into mathematics that will enlighten anyone fascinated by numbers.
Product Details
| ISBN-13: | 9781400880539 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 05/17/2016 |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 248 |
| Sales rank: | 708,107 |
| File size: | 9 MB |
About the Author
Read an Excerpt
Summing It Up
From One Plus One to Modern Number Theory
By Avner Ash, Robert Gross
PRINCETON UNIVERSITY PRESS
Copyright © 2016 Princeton University PressAll rights reserved.
ISBN: 978-1-4008-8053-9
CHAPTER 1
PROEM
In the interest of allowing the reader to enjoy our book without constantly referring to many other references, we collect in this chapter many standard facts that we will often use in the remainder of the book. A reader familiar with elementary number theory can skip this chapter and refer back to it when necessary. We covered most of these topics in Ash and Gross (2006).
1. Greatest Common Divisors
If a is a positive integer and b is any integer, then long division tells us that we can always divide a into b and get an integer quotient q and integer remainder r. This means that b = qa +r, and the remainder r always satisfies the inequality 0 ≤ r< a. For example, if we take a = 3 and b = 14, then 14 = 4 · 3 + 2; the quotient q = 4 and the remainder r = 2. You may not be used to thinking about it, but you can do this with b< 0 also. Take b = –14 and a = 3, and -14 = (-5) · 3 + 1; the quotient is q= - 5, and the remainder is r = 1. Notice that if we divide by 2, the remainder will always be 0 or 1; if we divide by 3, the remainder will always be 0, 1, or 2; and so on.
If the result of the long division has r = 0, then we say that "a divides b." We write this sentence symbolically as a | b. Of course, one requirement for long division is that a cannot be 0, so whenever we write a | b, we implicitly assert that a ≠ 0. If the remainder r is not zero, we say that "a does not divide b." We write that assertion symbolically as a [??] b. For example, 3 | 6, 3 [??] 14, and 3[??](-14). Notice that if n is any integer (even 0), then 1 | n. Also, if a is any positive integer, then a | 0. At the risk of giving too many examples, we also point out that 2 | n means that n is even, and 2[??]n means that n is odd.
Suppose now that m and n are integers that are not both 0. We can then define the greatest common divisor:
DEFINITION: The greatest common divisor of m and n, symbolically written (m, n), is the largest integer d such that d | m and d| n. If the greatest common divisor of m and n is 1, we say that m and n are relatively prime.
Because all divisors of m are at most as big as m (if m > 0) or –m (if m< 0), we can theoretically list all divisors of m and all divisors of n, and then pick the largest number that is on both lists. We know that the number 1 is on both lists, and there may or may not be any larger number simultaneously on both lists. For example, (3, 6) = 3, (4, 7) = 1, (6, 16) = 2, and (31, 31) = 31. This process would be tedious, though, if we wanted to compute (1234567, 87654321). There is a process called the Euclidean algorithm, which allows one to compute greatest common divisors without listing all of the divisors of both m and n. We will not describe that process here, but we will state and prove one consequence, often called Bézout's identity.
THEOREM 1.1: Suppose that m and n are not both 0, and suppose that d is the greatest common divisor of m and n. Then there are integers λ and μ such that d = λm + μn.
You can skip the proof if you like. It's actually a frustratingly incomplete proof, because we aren't going to tell you how to find λ and μ. Part of what the Euclidean algorithm does is to let you find λ and μ quickly.
PROOF: Let S be the following very complicated set, in which the symbol Z stands for the set of all integers:
S = {am + bn | a, b [member of] Z}.
In words, S is the set of all multiples of m(positive, negative, and 0) added to all multiples of n (ditto). Because S contains 0· m + 0 · n, we know that S contains 0. Because S contains m, -m, n, and -n, we know that S contains some positive integers and some negative integers, whether m and n are positive or negative. Moreover, if we add two numbers in S, we get a number that is in S. One more nonobvious assertion is that if s is any number in S, then every multiple of s is also in S.
Now, find the integer d that is the smallest positive integer in S. (Here's where we are using a quite subtle fact: If T is any set of integers that contains some positive integers, then there is some number that is the smallest positive integer in T.) We know that d is the sum of a multiple of m and a multiple of n, so write d = λm + μn. We are now going to prove three assertions:
(1) d | m.
(2) d | n.
(3) If c | m and c | n, then c ≤ITL d.
After we prove these assertions, we can conclude that d is the greatest common divisor of m and n.
Let's try dividing m by d. We know that we can write m = qd + r, where 0 ≤ r< d. Let's rewrite that equation as r= (-q)d + m. We know that m is an element of S because it's 1 · m + 0 · n. We know that d is an element of S, and therefore every multiple of d is an element of S. In particular, (-q)d is an element of S. We know that when we add two elements of S, we always get an element of S. Therefore, we are sure that r is an element of S.
But r is smaller than d, and we picked d to be the smallest positive element in S. We are forced to conclude that r = 0, which, at long last, tells us that d divides m. A similar argument shows that d divides n.
Now we know that d is a common divisor of both m and n. How do we know that d is the largest number that divides both m and n? Suppose that c is a positive integer that divides both m andn. We can write m = q1c and n = q2c. We know that d = λ + μn for some integers λ and μ, because d is an element of S. Substitution tells us that d = c(λq1 + λq). In other words, c divides d, so c cannot be larger than d. So d is the greatest common divisor of m and n, and d = λm + μn, as we just said.
[]
Note: We do not give full proofs of many theorems in this book. When we do give a proof, as we just did, the end of the proof is marked with a square [].
One of many consequences of theorem 1.1 is referred to both as the Fundamental Theorem of Arithmetic and as Unique Prime Factorization. Remember a basic definition:
DEFINITION: A prime is a number p that is larger than 1 and has no positive divisors other than 1 and p.
THEOREM 1.2: Suppose that n is an integer that is larger than 1. Then there is one and only one way to factor n into primes:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
where each pi is prime, pITL]1< p2< ··· <pk, and each ei > 0.
The reason that our phrasing is so detailed is that there may be many ways to factor some numbers into a product of primes: 12 = 2 · 2 · 3, 12 = 2 · 3 · 2, and 12 = 3 · 2 · 2, for example. But these are really all the same factorization, once we restrict our product formula to list the primes in increasing order.
2. Congruences
Suppose that n is an integer that is larger than 1. We write a = b (mod n), read in words as "a is congruent to b modulo n," for the assertion that n | (a – b). The number n is called the modulus of the congruence. Congruence is an equivalence relation, which means that for fixed n:
(C1) a = a (mod n).
(C2) If a = b (mod n), then b = a (mod n).
(C3) If a = b (mod n) and b = c (mod n), then a = c (mod n).
Moreover, congruence gets along very well with addition, subtraction, and multiplication:
(C4) If a = b (mod n) and c = d (mod n), then a + c = b + d (mod n), a – c = b&nd ash; d (mod n), and ac = bd (mod n).
Cancellation needs an extra condition:
(C5) If am = bm (mod n) and (m, n) = 1, then a = b (mod n).
It is simpler to discuss cancellation when the modulus is a prime. In that case, (C5) becomes:
(C6) Suppose that p is a prime. If am = bm(mod p) and m [??] 0 (mod p), then a = b(mod p).
This last fact is so helpful that we will try to use a prime modulus in our congruences whenever possible.
There is one more helpful fact about congruences, and this one we'll prove, using theorem 1.1.
THEOREM 1.3: Suppose that p is a prime that does not divide some integer a. Then there is an integer µ such that aµ = 1 (mod p).
PROOF: Because (a, p) = 1, we can find integers μ and v such that aμ + pv = 1. Rewrite that equation as aμ- 1 = pv, and we see that p | (aμ – 1). In other words, aμ = 1 (mod p).
[]
3. Wilson's Theorem
These ideas can be applied to yield a striking result called "Wilson's Theorem."
THEOREM 1.4: Suppose that p is a prime. Then (p - 1)! [equivalent to] -1 (mod p).
Notice that we are making an assertion about rather large numbers, even when p is not that large. For example, when p = 31, then Wilson's Theorem asserts that 30! = –1 (mod 31), which expands out to
26525285981219105863630848000000 [equivalent to] -1 (mod 31)
or equivalently that 265252859812191058636308480000001 is a multiple of 31.
PROOF: Let p be a prime number. We want to show that (p – 1)! [equivalent to] -1 (mod p).
We begin by listing all the positive integers from 1 to p - 1:
1,2,3, ..., p - 1.
Their product is (p - 1)!. Let x be one of these numbers. Is there a y on the list such that xy [equivalent to] 1 (mod p)? Yes! That's exactly what we proved in theorem 1.3. We can take y to be the number on the list that is congruent to μ mod p, where μ is the integer given to us by theorem 1.3.
We call y the inverse of x modulo p.]I TL We are justified in saying the inverse because y is unique. Why? Suppose xy' [equivalent to] 1 (mod p) for some other y' also on the list. Then xy [equivalent to] xy' (mod p). Multiply through by y to obtain yxy [equivalent to] yxy' (mod p). But yx = 1 (mod p), so we conclude that y [equivalent to] y' (mod p). Because both y and y' are on the list, their difference is between 0 and p, and cannot be divisible by p. So no other inverse for x can exist; y is the only one.
Now we group the numbers on our list in pairs, each with its inverse. The complication is that some of the numbers might be their own inverse! When can this happen? Well, x is its own inverse if and only if x2 [equivalent to] 1 (mod p). Equivalently, (x - 1)(x + 1) = x2 - 1 [equivalent to] 0 (mod p). In other words, p must divide (x - 1)(x + 1). Because p is prime, this can happen only if p divides either x - 1 or x + 1. Thus, the numbers on the list that are their own inverse are exactly 1 and p - 1.
So reorder our list as
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
where aibi [equivalent to] 1 (mod p) for each i. Multiplying everything together modulo p, we obtain their product [equivalent to] p - 1 (mod p). In other words, (p - 1)! [equivalent to] -1 (mod p).
[]
4. Quadratic Residues and Nonresidues
We start with some terminology:
DEFINITION: Let p be a prime that is not 2. If p does not divide an integer a and a [equivalent to] b2 (mod p) for some b, then a is a quadratic residue modulo p. If p does not divide a and a [??] b (mod p) for any integer b, then a is a quadratic nonresidue modulo p.
Typically, this terminology is shortened to "residue" and "nonresidue," with the word "quadratic" and the modulus implicitly understood. In fact, for the remainder of this section, we will often omit "(mod p)" from our congruences to save some space.
After choosing some prime p, making a list of residues modulo p can be done by squaring the integers from 1 to p – 1. But the task is actually only half as long, because k2 = (p - k)2 (mod p), so we only need to square the integers from 1 to (p - 1)/2. For example, the residues modulo 31 are
1,4,9,16,25,5,18,2,19,7,28,20,14,10,8.
We computed this list by squaring the integers from 1 to 15 and then dividing each by 31 and computing the remainder. The nonresidues are the numbers between 1 and 31 that are not on the list.
There are 15 residues modulo 31, and in general there are (p - 1)/2 residues modulo p. In case you're worried, we should show you why our list can't have any duplicates: If a21 [equivalent to] a22 (mod p), then p divides a21 - a22, so p divides the product (a1 - a2)(a1 + a2). Unique prime factorization now tells us that p divides a1 - a2 or p divides a1 + a2, and so either a1 [equivalent to] a2 (mod p) or a1 [equivalent to] -a2 (mod p). The second possibility is ruled out if we only square numbers from 1 to (p - 1)/2.
(Continues...)
Excerpted from Summing It Up by Avner Ash, Robert Gross. Copyright © 2016 Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
- Frontmatter, pg. i
- CONTENTS, pg. vii
- PREFACE, pg. xi
- ACKNOWLEDGMENTS, pg. xv
- INTRODUCTION: WHAT THIS BOOK IS ABOUT, pg. 1
- CHAPTER 1. PROEM, pg. 11
- CHAPTER 2. SUMS OF TWO SQUARES, pg. 22
- CHAPTER 3. SUMS OF THREE AND FOUR SQUARES, pg. 32
- CHAPTER 4. SUMS OF HIGHER POWERS: WARING’S PROBLEM, pg. 37
- CHAPTER 5. SIMPLE SUMS, pg. 42
- CHAPTER 6. SUMS OF POWERS, USING LOTS OF ALGEBRA, pg. 50
- CHAPTER 7. INFINITE SERIES, pg. 73
- CHAPTER 8. CAST OF CHARACTERS, pg. 96
- CHAPTER 9. ZETA AND BERNOULLI, pg. 103
- CHAPTER 10. COUNT THE WAYS, pg. 110
- CHAPTER 11. THE UPPER HALF-PLANE, pg. 127
- CHAPTER 12. MODULAR FORMS, pg. 147
- CHAPTER 13. HOW MANY MODULAR FORMS ARE THERE?, pg. 160
- CHAPTER 14. CONGRUENCE GROUPS, pg. 179
- CHAPTER 15. PARTITIONS AND SUMS OF SQUARES REVISITED, pg. 186
- CHAPTER 16. MORE THEORY OF MODULAR FORMS, pg. 201
- CHAPTER 17. MORE THINGS TO DO WITH MODULAR FORMS: APPLICATIONS, pg. 213
- BIBLIOGRAPHY, pg. 225
- INDEX, pg. 227
What People are Saying About This
"In Summing It Up, Ash and Gross, with their customary charm and clarity, build an impressive tower from the most basic mathematical story imaginable. They start by adding up finite sequences and whole numbers before journeying to the upper reaches of contemporary developments in number theory."—Jordan Ellenberg, author of How Not to Be Wrong: The Power of Mathematical Thinking"With joy and reflection,Summing It Up encourages readers to work alongside the authors to engage in simple computations with profound implications. It progresses elegantly to an insightful discussion of the ideas behind the classical theory of modular forms. A wonderful book."—Barry Mazur, Harvard University"This book takes general readers on a journey from simple addition to the modern theory of modular forms. Plentiful and accurate references are available for interested readers who want to look up further information."—Xiaoheng Wang, Princeton University"In Summing It Up, Ash and Gross are erudite and meticulous—they write with care and precision. Their book adopts the voice of a wise elder telling math stories to precocious children. It will interest readers of all ages who seek a window into current mathematics."—Kenneth Ribet, University of California, Berkeley"Summing It Up ambitiously presents concepts of number theory, from the elementary to the advanced, for readers with only a knowledge of high school math and some calculus. With a crisp yet conversational style and excellent examples, Ash and Gross explain a great amount of interesting and important math."—James Pommersheim, coauthor of Number Theory: A Lively Introduction with Proofs, Applications, and Stories"A well-motivated and fun introduction to some very deep topics in mathematics, Summing It Up takes readers on a mathematics tour starting with very classical material and building towards some amazing recent work, with many highlights along the way. It can be read by those with many different levels of mathematical background. I thoroughly enjoyed it."—Nathan Kaplan, University of California, Irvine