KMB, 15/12/99

M3/4P14 Elementary Number Theory—Problem Sheet 5

1) Let p > 2 be a prime. Say p has the property that for all a ∈ ℤ,

(\frac{a}{p}) = −1 ⇒ a is a primitive root.

Prove that p is a Fermat prime.

2) Let n > 1 be odd. Which of the following can happen? Proofs or counterexamples required!

i) (\frac{a}{n}) = 1 and a is a square mod n.

ii) (\frac{a}{n}) ≠ 1 and a is a square mod n.

iii) (\frac{a}{n}) = 1 and a is not a square mod n.

iv) (\frac{a}{n}) ≠ 1 and a is not a square mod n.

3) It’s a theorem that a non-negative integer can be written as the sum of three squares if and only if the integer is not of the form 4^{t}(8n + 7) for t, n ≥ 0. Prove the easier implication! That is, show that integers of the form 4^{t}(8n + 7) are not the sums of three squares.

4) In this question, a “cube” is the cube of a non-negative integer. Prove that only finitely many primes are the sum of two cubes. Do you think that infinitely many primes are the difference of two cubes?

5)

a) Which integers are of the form a^{2} + 2b^{2}? This is a really good question to do if you want to understand the proof in lectures which classified which integers are of the form a^{2} + b^{2}. You will have to go through the same ideas of that proof, mutatis mutandis. The only places that you are likely to get stuck is that at one stage you might find a prime p such that 2p = a^{2} + 2b^{2} and you will want to deduce that p is of the form c^{2} + 2d^{2}. This can be done though—if 2p = a^{2} + 2b^{2} then a must be even so you can divide the entire equation by 2.

b) Which integers are of the form a^{2} + 3b^{2}? Again, if you get stuck at all, you are likely to get stuck in the same place—but it is possible to get unstuck.

c) In general these tricks won’t work though. For an arbitrary fixed n > 0, the question “which primes are of the form a^{2} + nb^{2} has been studied for centuries, and has produced an astounding amount of mathematics, some classical and some very modern and technical. So go and read the book “Primes of the form x^{2} + ny^{2}” by Cox and do all the exercises in that.