189-346/377B: Number Theory Assignment 5

Solutions

1. An integer n is said to be square-free if its prime factorisation is of the form

n = p_{1}p_{2} ⋯ p_{r},

where p_{1}, …, p_{r} are distinct primes. Show that for all real s > 1,

\frac{ζ(s)}{ζ(2s)} = ∑_{n∈S} \frac{1}{n^{s}} ,

where

ζ(s) = 1 + \frac{1}{2^{s}} + \frac{1}{3^{s}} + ⋯

is the Riemann zeta function, and S is the set of positive square free integers.

Solution: By the Euler product factorisation for the Riemann zeta-function,

\frac{ζ(s)}{ζ(2s)} = ∏_{p}(1 − p^{−s})^{−1}(1 − p^{−2s}) = ∏_{p}(1 + p^{−s}),

the products being taken as usual over all the primes. Expanding the last product as an infinite sum, one observes that one obtains a term of 1/n^{s} exactly once for each n which admits a factorisation as a product of distinct primes with multiplicity one:

∏_{p}(1 + p^{−s}) = ∑_{n∈S} \frac{1}{n^{s}} .

2. Using a Sieve argument (or otherwise), show that the number of squarefree integers that are less than or equal to x is equal to

ζ(2)^{−1}x + o(x).

Solution: For any integer r, let p_{1}, …, p_{r} denote the first r primes, and let s_{r}(x) denote the number of integers ≤ x that are not divisible by any of p_{1}^{2}, p_{2}^{2}, up to p_{r}^{2}. Then by the same sieve argument as was used in class to show that π(x) grows at most like x/ log log x, we can see that

s_{r}(x) = x ∏_{j=1}^{r}(1 − p_{j}^{−2}) + e(r, x),

where e(r, x) ≤ 2^{r}. Now, letting r = [log(x)], we have 2^{r} = o(x) as was seen in class, and ∏_{j=1}^{r}(1 − p_{j}^{−2}) = 1/ζ(s) + o(1). The result follows. (Note that this proof is less delicate than the argument we carried out in class, essentially because the infinite sum defining ζ(s) converges at s = 2 while it diverges at s = 1.

3. Show that any integer of the form 4n + 3 always has a prime divisor of the form 4k + 3. Use this to give a proof that there are infinitely many primes of the form 4k + 3, analogous to Euclid’s proof of the infinitude of primes that was recalled in class. Show by a similar argument that there are infinitely many primes of the form 3k + 2.

Solution: If all the prime divisors of an integer are of the form 4k + 1, then the same is true of the integer itself. Hence any integer of the form 4n + 3 must have a prime divisor of the form 4k + 3. To see that there are infinitely many primes of the form 4k +3, let q_{1}, …, q_{n} be any finite set of such primes and observe that the integer 4q_{1} ⋯ q_{n} −1 is necessarily divisible by a prime q of the form 4k + 3 which is not already in that set. The argument for primes of the form 3k + 2 is identical (and was also seen again in class.)

4. Let d be a prime. Show that any prime p which does not divide d but divides the integer

n^{d−1} + n^{d−2} + ⋯ + 1

(n ∈ Z) is necessarily of the form kd + 1. Use this to show that there are infinitely many primes of the form kd + 1. (Hint: assume otherwise, and study the asymptotics of #{n^{d−1} + ⋯ + n + 1, n ≤ x^{1/d}} as x⟶∞ in two different ways to derive a contradiction.)

Solution. If p divides n^{d−1}+⋯+1, then it also divides (n−1)(n^{d−1}+⋯+1) = n^{d} − 1. Hence the residue class of n modulo p is an element of order dividing d, hence either n = 1 or n is of order (exactly) d. If n ≡ 1 (mod p), then p would have to divide n^{d−1} + ⋯ + 1 ≡ 1 + ⋯ + 1 = d (mod p), which we have assumed is not the case. Hence the class of n is of order d in (Z/pZ)^{×}. In particular, the group (Z/pZ)^{×} has cardinality divisible by d, and therefore p ≡ 1 (mod d).

To show that there are infinitely many primes of the form kd+1, suppose on the contrary that there are only finitely many such primes, p_{1}, …, p_{r}, and consider the set S(X, d) of integers ≤ X of the form n^{d−1}+⋯+1. On the one hand, the cardinality of S(X, d) grows asymptotically like cX^{1/(d−1)} for some constant c as X gets large (as is true for the set of values of any polynomial of degree d − 1). On the other hand, every integer in S(X, d) is of the form p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}} where the exponents e_{j} are bounded by log_{p_{j}}(X) = c_{j} log(X). Hence there are at most c′ log(X)^{r} such integers for some other constant c′. This is a contradiction since, for all α > 0 (however small) and for all M > 0 (however large), we always have

lim_{X⟶∞}(X^{α} − (log(X))^{M}) = ∞.

Note that a similar idea was already used in a previous assignment...

The following exercises are taken from the textbook by Levesque.

5. (Section 6.2, exercise 7 from Levesque.) Show that, for all s > 1,

∑_{n=1}^{∞} \frac{1}{n^{s}} · ∑_{n=1}^{∞} \frac{μ(n)}{n^{s}} = 1,

where μ(n) is the Möbius function defined by μ(n) = (−1)^{t} if n is a product of t distinct primes, and μ(n) = 0 if t is divisible by the square of some prime.

Solution. This follows from the factorisation formula for ζ(s) after noting that

ζ(s)^{−1} = ∏_{p}(1 − p^{−s}) = ∑_{n} μ(n)n^{−s}.

6. Show that if f(x) is a continuous, monotonically decreasing function which tends to 0 as x⟶∞, and if the series ∑_{n=1}^{∞} f(n) diverges, then the function

F (n) := ∑_{j=1}^{n} f(j)

satisfies

F (n) ∼ ∫_{1}^{n} f(x)dx.

Proof. This follows from the trick we have already used a number of times in class, in which we approximate ∫_{1}^{n} f(x)dx both from above and below by a Riemann sum:

F (n) − f(1) = ∑_{j=2}^{n} f(j) ≤ ∫_{1}^{n} f(x)dx ≤ ∑_{j=1}^{n−1} f(j) ≤ F (n).

It follows from this that

|F (n) − ∫_{1}^{n} f(x)dx| ≤ f(1),

and therefore the ratio ∫_{1}^{n} f(x)dx/F (n) tends to 1 as n⟶∞.

7. (Section 6.4, exercise 9 from Levesque.) Let log_{k} x be the k-th iterate of the logarithm function, defined recursively by

log_{1} x = log x, log_{k} x = log log_{k−1} x.

Is there a continuous increasing function f(x) such that lim_{x→∞} f(x) = ∞, yet f(x) = o(log_{k} x) for all k ≥ 1? If so, exhibit such a function.

Solution: Let

h(m) = e^{e^{e^{···}}} (m times),

and let

f(x) = least m such that h(m) > x.

To see that f(x) grows more slowly than log_{k}(x), write

x = e^{e^{e^{^{···}^{y}}}} (k times),

which is always possible once x is sufficiently large. Then it is not hard to see that

log_{k}(x) = y, f(x) = f(y) + k,

and hence the result follows since clearly f(y)/y tends to 0.

Math 377 only:

8. Section 6.8., exercise 4 in Levesque.

Solution: The method of proof is very similar to what was worked out in class for the case q = 5. (The fact that all Dirichlet characters mod 8 have values in Z makes it easier to work with products throughout rather than taking the logarithm of the Dirichlet L-series as we did in class, but otherwise the ideas are the same.)