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
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.