**Uh-oh, it looks like your Internet Explorer is out of date.**

For a better shopping experience, please upgrade now.

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

## Paperback(Reprint)

^{$}16.19

## Overview

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.

###### ADVERTISEMENT

## Product Details

ISBN-13: | 9780691178516 |
---|---|

Publisher: | Princeton University Press |

Publication date: | 01/30/2018 |

Edition description: | Reprint |

Pages: | 248 |

Sales rank: | 820,302 |

Product dimensions: | 5.60(w) x 8.90(h) x 0.70(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**

**PRINCETON UNIVERSITY PRESS**

**Copyright © 2016 Princeton University Press**

All rights reserved.

ISBN: 978-1-4008-8053-9

All 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* and*n.* 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< p*2< ··· <*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 *x*2 [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] *b*2 (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 (*a*1 - *a*2)(*a*1 + *a*2). Unique prime factorization now tells us that *p* divides *a*1 - *a*2 or *p* divides *a*1 + *a*2, and so either *a*1 [equivalent to] *a*2 (mod *p*) or *a*1 [equivalent to] -*a*2 (mod *p*). The second possibility is ruled out if we only square numbers from 1 to (*p* - 1)/2.

*(Continues...)*

Excerpted fromSumming It UpbyAvner 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