**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.