Inlämningsuppgift 2 Att lämnas in måndag den 16:e december

3.2 Prove that, for any positive integers a, n with (a, n) = 1 that

∑\{ax/n\} = \frac{1}{2}ϕ(n),

where the sum is over all x from 1 to n which are relatively prime to n. 3.5 Prove that, for every natural number n, either there is no primitive root modulo n, or there are ϕ(ϕ(n)) primitive roots modulo n. 3.6 Prove that, for any prime p, the sum of all the distinct primitive roots modulo p is congruent to μ(p − 1) modulo p. 3.8 Prove Wolstenholme’s theorem, namely that if p > 3 is a prime, then the numerator of

∑_{k=1}^{p−1} \frac{1}{k}

is divisible by p^{2}. 4.2 Show that if p is a prime ≡ 3 (mod 4) such that p′ = 2p + 1 is also prime, then 2^{p} ≡ 1 (mod p′). Deduce that 2^{251} − 1 is not prime. 4.4 Prove that if p is a prime ≡ 1 (mod 4) then

∑ r = \frac{1}{4}p(p − 1),

where the sum is over all quadratic residues r with 1 ≤ r ≤ p − 1. 4.6 Show that, for any integer d and any odd prime p, the number of solutions to the congruence x^{2} ≡ d (mod p) is 1 + (\frac{d}{p}). 4.7 Let f(x) = ax^{2} + bx + c, where a, b, c are integers, and let p be an odd prime that does not divide a. Further let d = b^{2} − 4ac. Show that, if p does not divide d, then

∑_{x=1}^{p} (\frac{f(x)}{p}) = − (\frac{a}{p}) .

4.8 Prove that if p′ is a prime ≡ 1 (mod 4) and p = 2p′ + 1 is a prime, then 2 is a primitive root modulo p. For which primes p′ with p = 2p′ + 1 prime is 5 a primitive root modulo p ?

S.1 How many solutions (mod 1708297) does the congruence

x^{2} ≡ 456781 (mod 1708297)

have ? (Hint : 1708297 = 1237 × 1381).

S.2 Show that, for Re(s) > 2,

\frac{ζ(s)}{ζ(s − 1)} = ∑_{n=1}^{∞} \frac{ϕ(n)}{n^{s}}.

S.3 Let p be an odd prime. Show that there is a positive n < 1 + \sqrt{p} such that (\frac{n}{p}) = −1.

S.4 Show that the group R̂ of CONTINUOUS group homomorphisms

χ : R → C^{×}

is canonically isomorphic to R (the latter as an abelian group under addition, the former under multiplication of characters).

S.5 Let a be any integer which is not a perfect square. Prove that there exist infinitely many primes p for which the congreunce

x^{2} ≡ a (mod p)

has (resp. has not) a solution.