189-346 / 377B: Number Theory
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.