Math 567 -- Elementary Number Theory

From UW-Math Wiki
Revision as of 19:05, 12 February 2020 by Andreic (talk | contribs)
Jump to navigation Jump to search

MATH 567

Elementary Number Theory

MWF 1:20-2:10, Van Vleck B119

Professor: Andrei Caldararu (andreic@math.wisc.edu) Office Hours: Wednesdays 2:30-3:30, Van Vleck 605.

Grader: TBA Office Hours: TBA.

Math 567 is a course in elementary number theory, aimed at undergraduates majoring in math or other quantitative disciplines. A general familiarity with abstract algebra at the level of Math 541 will be assumed, but students who haven't taken 541 are welcome to attend if they're willing to play a little catchup. We will be using William Stein's new (and cheap) textbook Elementary Number Theory: Primes, Congruences, and Secrets, which emphasizes computational approaches to the subject. If you don't need a physical copy of the book, it is available as a free legal .pdf. We will be using the (free, public-domain) mathematical software SAGE, developed largely by Stein, as an integral component of our coursework. There is a useful online tutorial. You can download SAGE to your own computer or use it online.

Topics include some subset of, but are not limited to: Divisibility, the Euclidean algorithm and the GCD, linear Diophantine equations, prime numbers and uniqueness of factorization. Congruences, Chinese remainder theorem, Fermat's "little" theorem, Wilson's theorem, Euler's theorem and totient function, the RSA cryptosystem, Rabin's encryption scheme, Diffie-Hellman key exchange protocol. Number-theoretic functions, multiplicative functions, Möbius inversion. Primitive roots and indices. Quadratic reciprocity and the Legendre symbol. Perfect numbers, Mersenne primes, Fermat primes. Pythagorean triples, Special cases of Fermat's "last" theorem. Fibonacci numbers. Continued fractions. Distribution of primes, discussion of prime number theorem. Primality testing and factoring algorithms.

Course Policies: Homework will be due on Fridays. It can be turned in late only with advance permission from your grader. It is acceptable to use calculators and computers on homework (indeed, some of it will require a computer) but calculators are not allowed during exams. You are encouraged to work together on homework, but writeups must be done individually.

Many of the problems in this course will ask you to prove things. I expect proofs to be written in English sentences; the proofs in Stein's book are a good model for the level of verbosity I am looking for.

Grading: The grade in Math 567 will be composed of 50% homework, 25% midterm, 25% final. The midterm will be on March 11, in class. The final exam will be on 5/8/2020, 7:45AM-9:45AM in room TBA.

Syllabus: (This may change as we see what pace works well for the course. All section numbers refer to Stein's book.)

  • Jan 22-31: Prime numbers, prime factorizations, Euclidean algorithm and GCD (1.1-1.2)
  • Feb 3-7: The integers mod n, Euler's theorem, the phi function (2.1-2.2)
  • Feb 10-14: Modular exponentiation, primality testing, and primitive roots (2.4-2.5)
  • Feb 17-21: Public-key cryptography and RSA (3.1-3.4)
  • Feb 24-28: Rabin's algorithm (not in the book); algebraic numbers
  • Mar 2-6: Quadratic reciprocity (4.1-4.4)
  • Mar 9, Mar 13: Finite and infinite continued fractions (5.1-5.3)
  • Mar 11: Midterm exam
  • Mar 23-30: Continued fractions and diophantine approximation (5.4-5.5)
  • Apr 1-3: Diophantine equations I: Pell's equation and Lagrange's theorem
  • Apr 6-10: More diophantine equations, elliptic curves (6.1)
  • Apr 13-17: Applications of elliptic curves (6.2-6.3)
  • Apr 20-24: More applications of elliptic curves (6.4)
  • Apr 27-May 1: advanced topic TBD: maybe additional discussion of cryptographic techniques?

Homework: Homework is due at the beginning of class on the specified Friday. Typing your homework is not a requirement, but if you don't already know LaTeX I highly recommend that you learn it and use it to typeset your homework. I will sometimes assign extra problems, which I will e-mail to the class list and include here.

  • Jan 31: 1.1, 1.3, 1.5, 1.7 (use SAGE), 1.8, 1.14.

Problem A: Use SAGE to compute the number of x in [1..N] such that x^2 + 1 is prime, for N = 100, N = 1000, and N = 10000. Let f(N) be the number of such x.

a) Can you formulate a conjecture about the relationship between f(N) and N/log N?

b) What if x^2 + 1 is replaced with x^2 + 2? Can you explain why x^2 + 2 appears less likely to be prime? (Hint: consider x mod 3.)

c) Prove that f(N) is at most (1/2)N+1. (Hint: consider x mod 2.)

d) Give as good an upper bound as you can for f(N).

Note that, despite the evident regularities you'll observe in this problem, we do not even know whether there are infinitely many primes of the form x^2 + 1! You would become very famous if you proved this.

  • Feb 7: 2.6 (the formulation of numerical evidence should be done by Sage if you've got Sage working, and by calculator if not; you can use an online tool like this to test whether a number is prime.) 2.8,2.9,2.11,2.12,2.14,2.19
  • Feb 17: 2.15, 2.18, 2.23, 2.26, 2.30.

Problem A: Prove that if n=pq, with p,q prime, then n is not a Carmichael number.


Retrieved from "https://wiki.math.wisc.edu/index.php?title=Math_567_--_Elementary_Number_Theory&oldid=19008"