Summing It Up: From One Plus One to Modern Number Theory

Summing It Up: From One Plus One to Modern Number Theory

by Avner Ash, Robert Gross


View All Available Formats & Editions
Members save with free shipping everyday! 
See details


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: 9780691170190
Publisher: Princeton University Press
Publication date: 05/17/2016
Pages: 248
Product dimensions: 6.90(w) x 9.40(h) x 1.00(d)

About the Author

Avner Ash is professor of mathematics at Boston College. Robert Gross is associate professor of mathematics at Boston College. They are the coauthors of Elliptic Tales: Curves, Counting, and Number Theory and Fearless Symmetry: Exposing the Hidden Patterns of Numbers (both Princeton).

Read an Excerpt

Summing It Up

From One Plus One to Modern Number Theory

By Avner Ash, Robert Gross


Copyright © 2016 Princeton University Press
All rights reserved.
ISBN: 978-1-4008-8053-9



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:


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 | (ab). 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), ac = 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


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


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.


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

Preface xi

Acknowledgments xv

Introduction: What This Book is About 1

1 Plus 1

2 Sums of Interest 3

Part 1 Finite Sums

Chapter 1 Proem 11

1 Greatest Common Divisors 11

2 Congruences 14

3 Wilson's Theorem 15

4 Quadratic Residues and Nonresidues 17

5 The Legendre Symbol 19

Chapter 2 Sums of Two Squares 22

1 The Answer 22

2 The Proof Is Not in the Pudding 26

3 The "If" Parts of Theorems 2.1 and 2.3 28

4 The Details 29

Chapter 3 Sums of Three and Four Squares 32

1 Three Squares 32

2 Interlude 33

3 Four Squares 34

4 Sums of More Than Four Squares 35

Chapter 4 Sums of Higher Powers: Waring's Problem 37

1 g(k) and G(k) 37

2 Sums of Biquadrates 39

3 Higher Powers 40

Chapter 5 Simple Sums 42

1 Return to First Grade 42

2 Adding Small Powers 43

Chapter 6 Sums of Powers, Using Lots of Algebra 50

1 History 50

2 Squares 52

3 Divertimento: Double Sums 55

4 Telescoping Sums 57

5 Telescoping Sums Redux 59

6 Digression: Euler-Maclaurin Summation 66

Part 2 Infinite Sums

Chapter 7 Infinite Series 73

1 Finite Geometric Series 73

2 Infinite Geometric Series 75

3 The Binomial Series 76

4 Complex Numbers and Functions 79

5 Infinite Geometric Series Again 81

6 Examples of Infinite Sums 83

7 e, ex, and ez 85

8 Power Series 87

9 Analytic Continuation 91

Chapter 8 Cast of Characters 96

1 H 96

2 ez Again 97

3 q, Δ*, and Δ0 98

Chapter 9 Zeta and Bernoulli 103

1 A Mysterious Formula 103

2 An Infinite Product 104

3 Logarithmic Differentiation 106

4 Two More Trails to Follow 109

Chapter 10 Count the Ways 110

1 Generating Functions 110

2 Examples of Generating Functions 113

3 Last Example of a Generating Function 119

Part III Modular Forms and Their Applications

Chapter 11 The Upper Half-Plane 127

1 Review 127

2 The Strip 128

3 What Is a Geometry? 130

4 Non-Euclidean Geometry 132

5 Groups 134

6 Matrix Groups 138

7 The Group of Motions of the Hyperbolic Non-Euclidean Plane 141

Chapter 12 Modular Forms 147

1 Terminology 147

2 SL2(Z) 148

3 Fundamental Domains 150

4 Modular Forms at Last 153

5 Transformation Property 155

6 The Growth Condition 158

7 Summary 158

Chapter 13 How Many Modular Forms Are There? 160

1 How to Count Infinite Sets 160

2 How Big Are Mk and Sk? 164

3 The q-expansion 169

4 Multiplying Modular Forms 171

5 Dimensions of Mk and Sk 175

Chapter 14 Congruence Groups 179

1 Other Weights 179

2 Modular Forms of Integral Weight and Higher Level 182

3 Fundamental Domains and Cusps 182

4 Modular Forms of Half-Integral Weight 184

Chapter 15 Partitions and Sums of Squares Revisited 186

1 Partitions 186

2 Sums of Squares 190

3 Numerical Example and Philosophical Reflection 196

Chapter 16 More Theory of Modular Forms 201

1 Hecke Operators 201

2 New Clothes, Old Clothes 208

3 L-functions 210

Chapter 17 More Things to Do With Modular Forms: Applications 213

1 Galois Representations 214

2 Elliptic Curves 217

3 Moonshine 219

4 Bigger Groups (Sato-Tate) 221

5 Envoy 223

Bibliography 225

Index 227

What People are Saying About This

From the Publisher

"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

Customer Reviews