Numbers, equations, and proofs

Fall 2008

Tu-Thu 11:00 AM--12:20 PM (Fine 314)
Office Hour: T-Thu 4--5 PM (510 Fine)

Books

  • I. Niven, H. S. Zuckerman, H. L. Montgomery, An introduction to the theory of numbers.
  • W. J. LeVeque, Fundamentals of number theory. (With more historical remarks.)
  • K. Ireland, M. Rosen, A classical introduction to modern number theory. (If you want to learn modern number theory, you can start with this book. Part of it will be studied in the Junior seminar guided by Professor Skinner. )

Schedule

This is a tentative schedule for the course. If necessary, I might change it.

  • 11 Sep:
    Introduction: Primes and factorization.
    Read: 1.2,1.3
  • 15 Sep -- 19 Sep:
    Unique factorization, Euclid's algorithm, and Congruences.
    Read: 1.2 and 1.3 again
  • 22 Sep -- 26 Sep:
    Units and primes in a "System of numbers", and Euler's ϕ function: Euler's theorem and Fermat's ``little'' theorem. and modular arithmetic. Mod m numbers.
    Read: 2.1
  • 29 Sep -- 3 Oct:
    Chinese Remainder Theorem, Number theory and public-key cryptography: the RSA algorithm.
    Read: 2.3, 2.5
  • 6 Oct -- 10 Oct:
    Solutions of polynomials modulo prime powers, Hensel's lemma.
    Read: 2.6, 2.7
  • 13 Oct -- 17 Oct:
    Multiplicative order, Primitive roots.
    Read: 2.8
  • 7. 20 Oct -- 24 Oct:
    p-valuation, Primitive roots (continued), Quadratic residue, Midterm.
    Read: 2.8, 3.1
  • 3 Nov -- 7 Nov:
    Polynomials over Z/pZ (review), Quadratic reciprocity.
    Read: 2.7, 3.2
  • 9. 10 Nov -- 14 Nov:
    Quadratic reciprocity (continued), Great integer function, Arithmetic functions.
    Read: 3.2, 4.1, 4.2
  • 17 Nov - 21 Nov:
    Convolution, and Möbius inversion.
    Read: 4.3
  • 25 Nov:
    Geometry of numbers, Sum of two squares.
    Read: 6.4
  • 1 Dec -- 5 Dec:
    Cyclotomic polynomials and its relation with primitive elements mod p, Beatty sequence and its generalization, Continued fractions.
    Read: 7.1, 7.2
  • 8 Dec -- 12 Dec:
    Continued fractions (continued).
    Read: 7.3, 7.4, 7.5, 7.6

More information.

Here are more information on the course, including the name and the e-mail address of the grader. pdf

Assignments.

  • Due Sep. 25:
    • Section 1.2, problems 47, 49, 51, 54;
    • Section 1.3, problems 23, 36, 39;
  • Due Oct. 2:
    • Section 2.1, problems 10, 14, 20, 28, 44.
    • Find all the Pythagorean triples, i.e. all triples of natural numbers (a,b,c) such that a2+b2=c2. (Hint:
      • Use lines passing through (0,1) with rational slope.
      • Rational points on the circle x2+y2=1.
      • Use extra parameters, and give formulas for a, b, and c in terms of those extra parameters, e.g. one can write all the integer solutions of 3a+2b=1 as a=2t+1 and b=-3t-1, where t can be any integer number (convince yourself why?))
    • Describe all the primes in Z/mZ. In particular, say under what condition, there is only one prime, up to multiplication by a unit, in Z/mZ.
    • Which prime numbers can be written as sum of two perfect squares? (Hint:
      • Look at a2+b2 modulo 4.
      • Use Wilson's theorem.
      • As most of you have already noticed the hard part of this problem is in Lemma 2.13 of your book. I expect you to think on this problem, yourself. After a while, you can read proof of this lemma, understand it, and then answer this problem. Again let me emphasis that you have to write down your solution without looking at your book, i.e. you have to recreat the argument. )
    • Let n be an integer with g.c.d.(n,10)=1. Show that the decimal expansion of 1/n is repeating. (Hint: Look at the following equalities.
      • 1/9 = 1/10 + 1/100 + 1/1000 + . . . = .11111 . . .
      • 1/99 = 1/100 + 1/10000 + 1/1000000 + . . . = .01010101 . . .
      • 1/999 = .001001001 . . .
      • 1/9999 = .000100010001 . . .
      Use their generalization, coupled with another theorem, to get the desired result.)
  • Due Oct. 9:
    • Section 2.1, problems 29, 30, 36, 49.
    • Section 2.3, problems 3, 7, 9, 13, 18, 21, 37, 41, 47.
  • Due Oct. 16:
    • Section 2.5: Problems 3, 4, 5.
    • Section 2.6: Problems 2, 7.
    • Section 2.7, Problem 10.
    • Show that there is no positive integer n for which 2n + 1 is divisible by 7.
    • Determine all integers n>1 such that (2n+1)/n2 is an integer.
    • Let n>3 be an odd number. Show that there is p a prime number such that
      • p | 2ϕ(n)-1,
      • p does not divide n.
      (Hint: Take a look at: Probem 35, section 2.3, Problem 49, section 1.2, and Problem 43, section 1.3.)
  • Due Nov. 6:
    • Problems 7, 8, 9, 10 from the midterm.
    • Section 2.8, Problems 20, 24, 29, 32.
  • Due Nov. 14:
    • Section 2.7, Problem 12.
    • Section 2.8, Problems 33, 34, 35
    • Section 3.1, Problems 11, 15, 21, 23, 24 (There is a misprint. It should be (a,m)=1 instead of (a,p)=1.)
    • Show that sum of quadratic residues mod p is divisible by p if p is an odd prime larger than 3.
  • Due Dec. 2: (Happy Thanksgiving) (Extended to Dec. 4:)
    • Section 3.1, Problem 20.
    • Section 3.2, Problems 1, 7, 13, 15, 19, 20, 21, 24.
    • Section 4.1, Problems 9, 20, 22, 23, 37.
    • Section 4.2, Problems 5, 10, 16, 19, 25.
    • Section 4.3, Problems 15, 23, 25, 26, 28, 29.
    • Let &Phin(x) be the nth cyclotomic polynomial.
      • a) Show that if p divides &Phin(x) for some integer x and (p,n)=1, then p is of the form nk+1.
      • b) Use the first part to show that there are infinitely many primes of the form nk+1.
  • Due Jan. 8: (Happy new year)
    • a) Let p be prime larger than 3. For some integer x, p divides x2+x+1 if and only if p is of the form 3k+1.
      b) Show that x2+xy+y2=1 is an ellipse. Its axis are lines y=x and y=-x, and find its area. (Hint: Rotate by angle 45 degree. So x=(X+Y)/Sqrt(2) and y=(Y-X)/Sqrt(2), and rewrite the equation.)
      c) If p is a prime of the form 3k+1, then there are integers x and y such that p=x2+xy+y2. (Hint: Use parts a, b, and Minkowski's convex body.)
    • Section 7.1, problem 3.
    • Section 7.3, problem 3.
    • Section 7.4, problem 1.
    • Section 7.5, problems 3,4.
    • Section 7.6, problems 3,4,5.

Midterm

You can find a pdf version of the exam here. It should be handed in on Thursday, Oct. 23. Good luck!

Final

  • Office hour during the reading week: Thursday, Jan 8, 1-3:30 pm. Your last problem set is also due at the end of the office hour.
  • The final exam consists of two separate parts.
    • Theorems and problems from the weekly problem sets (2/3 of the full grade). For this part, you are not allowed to use any book, your notebook, internet, etc.
    • New problems (1/3 of the full grade). For this part, you are allowed to look at your book, notebook, or weekly problems; but not any other book, internet, etc.
  • For each part, you will have 6 hours.
  • These exams cover almost all the materials discussed in the class.
  • I will post the exams by Tuesday, Jan 13. You have to hand me your exams by Friday, Jan 16, 7:00 pm.
  • Here is a pdf version of the first part of the final exam (on theorems and previous problem sets).
  • Here is a pdf version of the second part of the final exam (new problems).