Introduction to Number Theory, Math 104, Spring quarter 2011:

Course material: We use the book `Fundamentals of number theory' by William LeVeque. We plan to go through chapters 7 (Sums of Squares), 8 (quadratic equations and quadratic fields) and 9 (diophantine approximation and continued fractions). Some additional topics will be covered time permitting.

Office hours: M6-7 T3-4(Tuesday time may change)

Office: APM 5256, tel. 534-2734, email:

Teaching assistant: Joel Dodge, office hours: M 11-12, W 12-1, office APM 6351 email:

Computation of grade: Final 50%, Midterm 25%, Homework 25%

Dates of exams:

midterm: Wednesday, May 11

final: June 9, 3:00-5:59pm

Homework assignments: To be turned in on Wednesdays 5pm. You can put it into a mailbox on the 6th floor on APM, or give it to me in class. The exam problems will be similar to homework problems. So doing the homework problems is part of your preparation for exams, and is far more important than the 25% what they count for the grade.

for 4/6: 1. Let n=p_1p_2 ... p_rM^2, where p_1, p_2, ... p_r are prime numbers. Show that n can NOT be written as a sum of two squares if at least one of the primes is congruent to 3 mod 4. This is the missing implication of the theorem stated in class. You may use the theorems in the book which we proved in class (such as Theorem 7.3), but not theorems we did NOT prove.

2. Use the Fermat descent procedure twice, starting from 557^2 + 55^2= 26 x 12049, to write the prime 12049 as the sum of two squares. (I will distribute a sheet with an example of the descent procedure on Friday which contains the example which we did in class).

3. Find two distinct ways to write 25549 as the sum of two squares. Hint: You may use that 881=25^2+16^2, which we showed in class.

4. Show that if c is a product of primes congruent to 1 mod 4, there exist integers a and b such that (a,b,c) is a primitive Pythagorean triple (i.e. they are integers satisfying a^2+b^2=c^2 with (a,b)=1). Find such a triple for c=25549. ---------------------------------------------------------------------------------------------------------------------------

for 4/13: 1. We proved the corollary of Theorem 7.1 on page 180 of the book under the assumption that (a,m)=1. Show that this assumption is necessary by producing a counter example to the corollary as stated. (Hint: You should be able to find a counter example with m<10, and with \lambda = \sqrt{m} = the positive square root of m).

2. Do the problems 2bcd on page 183. (Hint: Proceed as in the proof of Theorem 7.4, using the corollary as stated in Problem 1, to find x and y with x^2 + 2y^2 = Ap, with A=1,2. Then try to deduce from this a solution in the case A=2 by considering divisibility properties of x and y. Proceed similarly for case (c), where A=1,2,3.

3. Define for any complex number z=a+ib the number N(z)= a^2+b^2. You can use that N(z_1z_2)=N(z_1)N(z_2). Consider the ring R= Z[i], i.e. all complex numbers z=a+ib with a,b integers. We say that an element z is irreducible in R if the only elements dividing it are elements of the form u or uz, where u=1,-1,i,-i.

(a) Determine all prime numbers p for which there exists a z in R with N(z)=p. Here determine could mean something like all primes p which are congruent to, say 5 mod 7 (though this is not the solution).

(b) Determine all primes p in Z which are not irreducible in Z[i] (Hint: Use that if p=z_1z_2 in R, then p^2=N(p)=N(z_1)N(z_2)).

4. Let now R=Z[\sqrt{-5}], i.e. all complex numbers of the form z=a+b\sqrt{-5}, where N(z)=a^2+5b^2.

(a) Show that for z= 2 and for z= 1 + \sqrt{-5} the only divisors in R are 1, -1, z and -z, in each case, i.e. these elements are irreducible. (Again use N(z)).

(b) Show that the unique factorization property does not hold for 6 in the ring R. For this, it suffices to write 6=p_1p_2=q_1q_2, where all the factors are irreducible elements such that p_1 is not equal to uq_1 or uq_2 with u a unit in R (you may use that for our R the units are just 1 and -1).

Remark: The fact that the unique factorization property does not hold for rings as in Problem 4 spoiled an approach to prove Fermat's Last Theorem, which was attempted in the 19th century. It did show, however, that x^p + y^p = z^p does not have an integer solution for certain primes p. --------------------------------------------------------------------------------------------------------------

for 4/20: 1. (a) Let R=Z[i] and let z= 11+17i, and x= 5+3i. Find q and r in R such that z=qx+r with N(r) < N(x) (or r=0).

(b) Find the greatest common divisor of x= 8+38i and y= 9+59i.

Find a decomposition into prime factors of the element -5+11i in Z[i].

2. Consider the ring R= Z[\sqrt{3}], i.e. the collection of all numbers of the form a + b\sqrt{3} with a and b being integers, and define N(a+b\sqrt{3})= a^2-3b^2. (I hope everyone is familiar with the notation by now - if not, please ask).

(a) Show that N(z_1z_2)=N(z_1)N(z_2) for all z_1, z_2 in R

(b) Show that if z is a unit in R, then N(z)=1 (Hint: first show that N(z) must be equal to 1 or -1, and then find a reason why it can not be the second case). Also show that if N(z)=1, then z must be a unit.

(c) Find at least eight units in R.

(d) Extra credit: Show that R has infinitely many units, and that the equation x^2-3y^2=1 has infinitely many integer solutions. (Hint: Show that any product of units is again a unit). As usual, you are allowed to use hints and previous parts of a problem regardless whether you could prove them or not.

Fourth assignment, due 4/27

Fifth assignment, due 5/4

for 5/11: We will have our midterm in class. You will be allowed a cheat sheet, but no calculator, books or other notes. The material goes over the first five homework assignments. So you could expect questions concerning sums of two (or more) squares, Pell's equation, units and factorization questions concerning rings in quadratic extensions, such as Z[i], Z[\sqrt{d}], Z[(1+\sqrt{d})/2]. Below are a few problems to review sums of two squares and Gaussian integers.

A few practice problems

Solution for midterm problem 2d

Sixth assignment, due 5/18

Seventh assignment, due 5/25

Eighth assignment, due 6/1

Final: The final will take place Thursday, June 9 from 3-6pm in the class room. The usual rules apply: One cheat-sheet, no calculators or books. The material is cumulative, with more emphasis on the latter part (i.e. continued fraction expansion, best approximation, connection to Pell's equation). I will have office hours on Wednesday, 2-4. I will be around during the exam week (mostly afternoon), so you can also try to catch me in my office (email or call first). Check the homework problems again! Here are also a few review exercises:

A few practice problems for final

Here are some more solutions of homework problems:

Some homework solutions