189-346 / 377B: Number Theory

Assignment 1

Due: Monday, January 18.

Read Chapter 1 (Introduction) of the textbook and do:

From the textbook:

Section 1.1, Problems 1, 2.

Section 1.2, Problem 2.

Section 1.3, Problems 5, 11.

Section 1.4, Problems 2, 10, 12.

Optional Problem. Using the ideas of problem 12, section 1.4, write a computer program which takes as input an integer N congruent to 1 mod 4, and tests for its primality. Try to make your program as efficient as possible. Test it on the first few "Fermat primes" N = 2^(2^k)+1. Around which value of k does your program get stuck? If your program reveals that N can be expressed as a sum of two squares in two different ways, explain how this information might be used to derive a non-trivial factorization of N.