189-346/377B: Number Theory Assignment 1

Due: Monday, January 15

1. Let M_{n} = 2^{n} − 1 denote the nth Mersenne number. Show that if r divides n, then M_{r} divides M_{n}.

2. Show that if 2^{k} + 1 is prime, then k must be a power of two. Write down 2^{2^{n}} + 1 for n = 0, 1, 2, 3, and 4, and show that these numbers are prime.

377: Show that, if p is a prime divisor of 2^{2^{n}} + 1, then p is of the form p = 2^{n+1}k + 1.

3. Let li(x) = ∫_{2}^{x} \frac{dt}{log(t)} be the function that occurs in Gauss’s statement of the Prime Number Theorem. Show that

lim_{x⟶∞} \frac{li(x)}{x/ log(x)} = 1,

and conclude that li(x) can be replaced by the simpler function x/log(x) in the statement of the PNT.

4. Show that 55 can be written as a difference of two perfect squares in exactly two different ways, and write down those expressions.

The following two questions will require you to use a computer algebra system.

5. Show that 2^{2^{k}} + 1 is not prime for k = 5, 6, 7, and 8, by producing the factorisation. This is a calculation that Fermat was not able to do, since he did not have access to a computer! Based on the outcome of question 2, he rashly predicted that 2^{2^{n}} + 1 is prime for all n; it is now believed that in fact this number is never prime for n ≥ 5, a statement that seems a likely candidate for a true fact that could forever elude proof. For n ≥ 9, it becomes more dificult to factor these numbers. The fact that 2^{2^{9}} + 1 is not prime was known for quite some time, but its full factorisation is a computational tour de force that was only achieved in 1990. The full factorisation of 2^{2^{12}} + 1 is still not known; this number has a composite factor with 1187 digits which has not been factored to this day.

6. Compute e^{π\sqrt{163}} with 30 significant digits on Pari. (For this, enter the Pari command \p30.) What do you observe? Repeat the calculation with 40 significant digits. (This exercise is meant to get you familiar with using Pari, and also as a cautionary tale about drawing conclusions too hastily based on experimental data.)