Math 58 - Number Theory

download uncropped hi-res version (2.1MB)

This is the home page for Math 58, Number Theory.

back to Walter Stromquist's page

jump to course documents

jump to schedule (last updated 11/1/06) ---

12/18/06 - Here's all I can provide in the way of a "what's on the final" sheet:

The exam is scheduled for 9am-noon on Thursday, December 21, in our usual classroom. I will take advantage of the available time, but will try to keep speed from being a major factor. The exam will be a closed book exam (no book, no notes, yes calculators). I'll be looking for concepts, techniques, proofs, and general understanding, and will try to avoid relying on specific details that you would have to memorize. In particular, it is **not** necessary that you know everything on the Theoretical Computer Science Cheat Sheet. (That's for your Ph.D. qualifying exam.)

The exam will cover the entire semester, but it is doing double duty with respect to the last three weeks, so the last three weeks' material will represent more than its proportional 3/13 of the exam.

Things we have covered since Exam 2, and sections (etc.) to read:

- Recognizing primes - Rabin test; Pick a and raise it to power equal to the odd part of n-1, accept as prime if result is 1; otherwise keep squaring it till it reaches power n-1; accept as prime only if -1 occurs before 1. Repeat for high probability of correctness.
**Section 6.2.** - Recognizing primes - PRIMES is in P.
**Read the first three pages**of that paper to get an idea of how they saw the problem and what they did. - RSA encryption - appropriate section in text. We never broke each others codes, but if you can factor your rivals' "n" you know everything they know.
- Factoring - Fermat, Pollard Rho (Section -), Pollard p-1 (Section -)
- Factoring - Quadratic Seive - notes are only class reference. Calculate x^2-n for lots of x's; factor some of them, picking a list of prime factors in advance and taking advantage of the regular pattern of divisibility in the sequence to avoid having actually to divide; when enough numbers are factored solve a linear system to pick out a bunch whose product has all even exponents; now you have found an instance of x2=y2 mod n.
- Analytic number theory -
**see essay, below**although I did notice that we went through this fairly fast.

I may revise this with corrected section numbers tomorrow.

12/12/06 - Here's the promised assessment questionnaire. More details in class.

58assessment.doc -- 4-page Word doc; no graphics or equations

12/10/06 - Here are my class notes on Analytic Number Theory from December 5-7. They include the
proof of Chebyshev's version of the Prime Number Theorem, the proof Dirichlet's theorem (for primes congruent to
1 and 3 mod 4) using Euler products, the derivation of r2(n) by analytic means, and the similar derivation of
the number of ways n can be represented as a-squared-plus-twice-b-squared.

analyticNT.pdf - 14-page pdf (improved 6pm 12/10)

(Clearly, I'm tripping out on the power of LaTeX.)

12/7/06 - Here's an interesting link:

http://www.tug.org/texshowcase/cheat.pdf

It's a ten-page pdf entitled "Theoretical Computer Science Cheat Sheet." It's intended to tell you all you need to know about mathematics. And it does. It turns out that you have been wasting your time taking math classes; all you needed to do was to glance at this document.

From the URL, I suspect that one reason for posting it is to illustrate the power of TeX. It does that pretty well, too. (Thanks to George Dahl for the link.)

11/21/06 -- Homework for Tuesday 11/28: Nothing to turn in, but do these things...

(a) download and install xnumbers, if you can, and play with it for a while

(b) find a better RSA key, by finding two primes of 20 or more digits (using xnumbers
or any other device)

(c) read the first three pages of the AKS paper (see below).

Happy Thanksgiving!

11/21/06 -- Here's something with possibilities: the XNUMBERS add-in for Excel is a
free, open-source package of functions for use in Excel 2003 or Excel XP. Its main
feature is high-precision (typically up to 200 digits) for both real-number and integer
arithmetic. Among its number theory functions:

xpowmod ( a, b, m ) - computes a^b mod m

MCD ( a, b ) - computes gcd (a, b) [MCD means maximum common divisor; we would have said gcd]

nextprime ( a ) - gives the smallest prime >=a (up to 6 or 8 digits or so)

We'll try to download and install this in class.

11/21/06 -- Today we'll look at primality tests --- two in particular. The first
is the Miller-Rabin test in section 6.2; the second is the one in the paper "PRIMES is
in P" by Agrawal, Kayal, and Saxena (AKS). Here's the version of the AKS
paper in the *Annals of Mathematics:*

http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf

That's from 2004, but preprints appeared in 2002. This paper is the best senior thesis
project ever.

11/17/06 -- FWIW, you may use the Excel calculator for the exam. (I don't know that it will be useful.)

11/17/06 -- Here is the table from the blackboard of groups and their encryption keys:

group | n | e | |

CM | 6,199,471 | 3285 | (sent to JK, to be broken by GPB) |

JK | 5,092,093 | 3575 | (sent to GPB, to be broken by CM) |

GPB | 34,111,313 | 1003 | (sent to CM, to be broken by JK) |

DR | 264,427 | 7873 | (sent to BD, to be broken by WKL) |

BD | 42,241 | 4213 | (sent to WKL, to be broken by DR) |

WKL | 1,088,513 | 1963 | (sent to DR, to be broken by BD) |

Encoding: Q = P ^ e (mod n)

Decoding: P = Q ^ d (mod n)

d is chosen so that ed=1 (mod phi(n)).

Why the decoding works: Q^d = (P^e)^d = P^(ed) = P^(k phi(n)) times P = P (mod n).

Clearly this is possible only if (e, phi(n)) = 1. Nobody knows how to get d from (n,e) without knowing phi(n) (although there is no proof that there isn't a way). We do know that finding phi(n) is as hard as factoring n. (But actually there are is no proof that factoring n is as difficult as it appears to be, so the RSA scheme is relying pretty heavily on conjectures.)

11/16/06 -- Here's the "what's on the exam" sheet:

Word version (4 pages with MathType)

web version (html, but stored by Word, so the symbols are garbled. This includes the Greek letters tau, sigma, phi, and mu, so perhaps you should take the trouble of dealing with the Word version.)

I guess we covered a lot. The list looks pretty frightening, even to me -- even more frightening than the exam itself, I think.
But hey, you know all this stuff cold.

11/16/06 -- Here is the completed Excel workbook from class today.

58calculator.xls (Yes, you can use this on the exam, though I don't
know that there will be an occasion for it.)
It should suffice
for calcuating:

b^e (mod m)

gcd(a,b)

x,y such that xa + yb = gcd

(and if gcd=1)

a-inverse mod b

b-inverse mod a

11/16/06 -- Instructions for exam:

Take this exam at a time and place of your choosing. **Time limit:** 4 hours from start to finish. You may use a calculator but not a computer. You may use any paper reference that was prepared (a) by anyone before class time on November 16 or (b) by you at any time. You may consult the course web site but no other web or electronic resources. Write your answers on this paper, your own paper, or both. It isn’t necessary to turn in scratch paper. There are 11 numbered questions on 5 pages.

Show your work. (It may sometimes be necessary for full credit, and it’s always necessary for part credit.)

Return this exam in class or to my office by **11:20am on Tuesday, November 21.**

11/14/06 -- Homework problems for 11/16/06 (or whenever you can do them!):

1. If x^2 + y^2 = z^2 and x, y, z are positive integers, can x be a perfect number?

2. If x^2 + y^2 = z^2 and x, y, z are positive integers, can z be a perfect number?

3. If x^2 + y^2 = z^2 and x, y, z are positive integers, can x and y be perfect numbers?

4. If x^2 + y^2 = z^2 and x, y, z are positive integers, can x and z be a perfect numbers?

5. If x^2 + y^2 = z^2 and x, y, z are positive integers, can x, y, and z be perfect numbers?

These are hard enough if you limit your consideration to even perfect numbers, which are of the form 2^(n-1) times (2^n)-1 whenever (2^n)-1 happens to be prime. But you might also consider odd perfect numbers. If there are any, then each is of the form a^b times c^2, where a is a prime congruent to 1 mod 4 and b is odd. (In fact, b is itself congruent to 1 mod 4, c is relatively prime to a, and many, many, other restrictions are known to hold. If you can first prove that there are no odd perfect numbers, then 1 through 5 above will be easier.)

11/13/06 -- There is no homework to be turned in on 11/14. But if you're hungry for another dose of Gaussian Integers, here is one:

Word version: GaussianPrimes.doc (3 pages with MathType)

web version: GaussianPrimes.htm

The climax of this essay is a short proof that each prime p=1(mod4) can be written as a sum of two squares in ONLY one way.

Some symbols didn't come through in the web version. For example, the little raised circle stands for "congruent to," and the backwards apostrophe means "times" --- at least on my version of Firefox.

11/7/06 -- Homework 13: Word verson and html version.

11/7/06 -- Well, this is interesting: I googled "Plimpton 322" (with extra keywords like Babylonian and Pythagoras)
and found--well, see for yourself.

http://www.math.ubc.ca/~cass/courses/m446-03/pl322/322.jpg -- image from Prof. Cass

Professor Cass's site at UBC:
http://www.math.ubc.ca/~cass/courses/m446-03/pl322/pl322.htm

D. Joyce's site at Clark U.:
http://aleph0.clarku.edu/~djoyce/mathhist/plimpnote.html

...and that's just starters.

11/6/06 -- Three notes on homework 12:

(1) The text has answers to #1, the six Legendre symbols, on page 667. Exactly half of the text's answers are correct.

(2) On #3, I told you to compute N = 5(n!)-1, but of course you realized that you should use N = 5(n!)^2-1.

(3) Do you think the last set of questions are about Gaussian integers? You're right, of course, but they're also about how many ways you can represent an integer as a sum of squares.

Homework 12: Word verson and html version.

11/1/06 -- I updated the schedule. See above.

10/26/06 -- Homework 11: Word verson and html version.

10/26/06 -- Here is the list of things to come, as shown on the board this morning...

- I. Quadratic Reciprocity (Chapter 11)

-when is x a square, mod p?

-prove the reciprocity theorem: if p and q are primes, then whether p is a square mod q has something to do with whether q is a square mod p.

- II. Diophantine Equations (mostly Chapter 13)

-solving quadratic equations mod p

-x^2 + y^2 = z^2 (Pythagorean triples)

-x^n + y^n = z^n (Fermat's Last Theorem; Wiles)

-Pell's equation (?)

-Sums of squares

-Contest problems

- III. Factoring and Primality Testing

-Pseudoprimes and Carmichael numbers (1729 and all that; Section 6.2)

-Rabin's (probabilistic) primality test

-PRIMES is in P (ca. 2002)

-Special tests for Fermat and Mersenne numbers?

-Pollard's "p-1" factoring method

-Pollard's "rho" factoring method

-RSA encryption

-*The quadratic seive (for factoring) - IV. Hint at analytic number theory

-zeta function

-prime number theorem

-Riemann hypothesis - V. Hint at algebraic number theory

-Gaussian integers (Chapter 14)

We're doing quadratic residues and the quadratic reciprocity theorem first, because understanding which numbers are squares will help with both the diophantine equations and the quadratic seive.

Today we already took a bite out of the first item --- which numbers are squares mod p. We learned that -1 is a square mod p if p is congruent to 1 mod 4, but not if p is congruent to 3 mod 4. (That's because, if g is a generator of Z*, then the squares are the even powers of g; but -1 is g^((p-1)/2), and that's an even power precisely when p = 1 mod 4.) That's Theorem 11.5 in the text. Theorem 11.6 takes the next bite; it tells when 2 is a square mod p.

10/25/06 -- Things you find on the internet...

From a review of Neal Stephenson's *Cryptonomicon*:

The math gets out of hand, too. Naturally I swooned to see the Riemann Zeta Function on page 11; but I got bored with the modular-arithmetic stuff about the bicycle chain in p. 204 ff, and just skipped to the next chapter. Modular arithmetic **is** boring, until you get to quadratic reciprocity (which Stephenson doesn't), after which it gets terrifically fascinating—any math geek knows that.

10/5/06 -- Here's a "What's-on-the-exam" handout, to be distributed in class today:

58preexam1.doc -- Word version (4 pages)

58preexam1.htm -- html version (not checked)

It's a rough stream-of-consciousness thing, but probably better than nothing as a last-minute review checklist. I'll hand out the exam today, too, in envelopes, so that you can take it when and where you like.

10/5/06 -- Also, it's ancient history, but here are links to hw 7.

58homework7.doc

58homework7.htm

9/26/06 -- NEWS!

9/25/06 -- The schedule (linked to above) has been updated.

9/21/06 -- Overdue postings:

Homework 3 & 4 -- (Word version)

Homework 5 -- (Word version)

Homework 6 -- (Word version) (due
9/26/06)

What we have been doing:

Thursday 9/14/06: Finished proof of unique factorization.

Tuesday 9/19/06: Introduction to congruences, according to Section 4.1 (or Gauss, *Disquisitiones
Arithmeticae,* 1801, Book 1, Section 1).

Thursday 9/21/06: We can solve a congruence of the form ax=c (mod m) if we can find a multiplicative inverse for a --- that is, b such that ba=1 (mod m). In fact, we can do that if (a,m)=1, and only then. (Just write ax+my=1; then x is the required b.) That means that all the integers from 1 to p-1 have inverses mod p, and we can pair them off with their inverses to show that (p-1)!=-1 mod p. That is, if we can show that the only values that are their own inverses are 1 and -1, and we left that issue hanging.

What's coming up: (a) How to solve ax=c (mod m) when (a,m) isn't 1 and (b) the Chinese Remainder Theorem (which is just a generalization of problem 9 in homework 6).

9/12/06 -- Here are solutions to homework 2 (html). (Word version) These solutions aren't very good, especially for problems 1-3, but maybe it's better to post them than not to post them.

9/12/06 -- Today we proved that every positive integer can be expressed
uniquely (up to order) as a product of primes. That's Section 3.5, and it uses
one key lemma from Sections 3.3 and 3.4. Your
homework for 9/19 is essentially the same thing. Your homework for Thursday
is shorter but has one hard problem.

Homework 3-4 (web version) ---
(Word version)

According to Prof. Maurer, there is some dispute as to whether Euclid knew the unique factorization theorem. Apparently it isn't in the Elements, but some see enough there to suggest that he knew it in some sense.

Thursday we'll look at the distribution of the primes and at some simple
theorems and conjectures about primes, mostly from Sections 3.1 and 3.2 and
from the book by Crandall and Pomerance, *Prime Numbers - A Computational
Perspective.* Among other things, we'll find that there are at least
43 Mersenne primes, and therefore at least 43 perfect numbers.

9/10/06 -- Your answers to homework 1 were essentially perfect.

9/7/06 -- Today we introduced the axioms in Appendix A. For more on induction, see Section 1.3. We also introduced perfect numbers. Euclid knew that even perfect numbers are of the form (2^q-1)(2^(q-1)) where (2^q-1) is prime. That can only happen when q itself is prime, but it doesn't always happen even if q is prime. Euclid didn't know which numbers (2^q-1) are prime. We still don't know that, or whether there are any odd perfect numbers.

Tuesday we'll start on primes (Section 3.1, and maybe 3.2, and work toward 3.5).
The big issues are

(a) proving that every positive integer is uniquely a product of primes
(the fundamental theorem, 3.5) and

(b) how dense are the primes? (3.2)

Another question: Note that the primes 5, 11, 17, 23, 29 are evenly spaced. Does
it ever occur that six primes are evenly spaced? How about twelve primes?

Here is homework 2, a giant pile of proofs, in Word form (one page) and in web form (html). It's due Tuesday 9/12. If there are too many problems, it's better to do some of them well than all of them poorly.

9/5/06 -- Here is homework 1, in Word form (one page) and in web form (html). It's due Thursday 9/7. For homework, you're free to collaborate and use any resources at all. (Links include very slight clarifications as of 3pm 9/6.)

Highlights from today: Given positive integers a and b, we can find their gcd by a series of divisions-and-subtractions called the Euclidean Algorithm. By reversing the same steps, we can write the gcd as a linear combination, xa + yb. Using this technique, we proved that if a is a divisor of bc, and if gcd(a,b)=1, then a is a divisor of c. Plan for Thursday: We'll introduce axioms for integers (Appedix A and Section 1.3) so that we'll have a solid foundation for our proofs.

If you want to keep up in the text, begin with Section 1.5 and then jump to Sections 3.3 and 3.4; OR begin with Appendix A. By the end of week 2, we will have done Sections 1.3-1.5 and 3.1-3.5 (with bits from 1.1, 1.2, and decimal-binary translations from 2.1). A that point, as homework, you'll write your own proofs from scratch of the Fundamental Theorem of Arithmetic (unique factorization into primes). Then we'll move on to congruences (Sections 4.1-4.3).

Sept. 1 -- FWIW, here's the topic list that I posted on my bulletin board last May. (WORD version) As noted, this may be more than we can do; I want to save time for a detailed treatment of RSA encryption and some advanced factoring algorithms, so we might go light on, e.g., Pell and multiplicative functions.

August 1, 2006 -- Here are some problems to whet your appetite for the first week of number theory:

- 1. Do 1,625,650 and 34,191,171 have a common factor? (I mean, of course, a common factor bigger than 1.)
- 2. If we subtract a multiple of 91 from a multiple of 140, is it possible for the result to be 77 ?
**3. Show that if bc is a multiple of a, and if a and b have no common factors bigger than 1, then c is a multiple of a.**

We'll spend the first week on the theory of divisibility, and problem #3 is the key result that we'll need to carry forward to the second week. We'll use it to prove that every positive integer can be written uniquely as a product of primes. So, we'll need to prove #3 without using unique factorization in our proof.

We have a textbook:

Kenneth H. Rosen, "Elementary Number Theory and its Applications," 5th edition, Pearson/Addison-Wesley, 0-321-23707-2I chose this text because I enjoyed using an earlier edition at Bryn Mawr, and because it has almost all of the topics I want to cover. In particular, I studied its treatments of (a) the proof of the fundamental theorem of arithmetic, (b) representation of integers as sums of squares, and (c) factoring algorithms, and on these points it came out ahead of some other texts. Here are three other good texts that will be on reserve at Cornell when the semester starts:

Niven, Zuckerman, and Montgomery, "An Introduction to the Theory of Numbers," 5th edition, John Wiley & Sons, 1991, 0-471-62546-9 (much more challenging than Rosen's book)

James J. Tattersall, "Elementary Number Theory in Nine Chapters," 2nd edition, Cambridge University Press, 0-521-61524-0 (fun to read)

John Stillwell, "Elements of Number Theory," Springer-Verlag, 2003, 0-387-95587-9 (also fun to read)

May, 2006 -- Here's the course catalog entry for Math 58:

MATH 058. Number Theory

The theory of primes, divisibility concepts, and multiplicative number theory will be developed. Students are also expected to learn how to construct a mathematical proof.

Prerequisites: Linear algebra and several-variable calculus or permission of the instructor.

1 credit.

Back to top

**Course documents:**
(back to top)

Topics for Number Theory.doc - Word version (2 pages)

58schedule.htm or 58schedule.xls -- schedule (PENDING - LINKS DON'T WORK)

58courseinfo.html -- syllabus (PENDING - LINK DOESN'T WORK)

back to Walter Stromquist's page

back to Math Department page