Materials Covered and Suggested Readings, Week 2, 1/17--1/21


In the second week, we gave two proofs of the Chinese Remainder theorem. Then we went back to chapter 2 of Rosen. We introduced the big-O notation, and used it to discuss the complexity of integer operations. It takes O(n) operations to add two n-digit integers. It takes O(n^2) operations to multiply two n-digit integers using the standard algorithm. There are faster algorithms for integer multiplication. This can be a project at the end of the semester.


A challenge problem.
Suppose you are given a homogenous quadratic polynomial with integer coefficients, and a non-trivial integer solution of it. For instance, the polynomial may be 7*x^2 + y^2 - 3*z^2 - 5*w^2=0, and (1,1,1,1) is an integer solution. Then you can find a formula, so that "most" integers solutions are given by that formula. (The solutions are never unique though.)
[This is a generalization of an example we gave at the first lecture. The solutions of the equation x^2+y^2-z^2=0 can be given by the formula x=u^2-v^2, y=2*u*v, z=u^2+v^2.]

If you think you have gotten somewhere on this problem, or you would like to have some hint, please come to my office hours.