Inlämningsuppgift 1 : Lösningar

1.2 SGD(35, 55) = 5 so, running Euclid’s algorithm forward and back we can find integers x_{1}, y_{1} such that

35x_{1} + 55y_{1} = 5,

for example x_{1} = −3, y_{1} = 2.

Since SGD(5, 77) = 1 we can find integers k, z such that

5k + 77z = 1,

for example k = 31, z = −2. Finally, put x = kx_{1} = −93, y = ky_{1} = 62.

1.3 Denote the sum by S_{n}. Let k be the unique positive integer such that 2^{k} ≤ n < 2^{k+1}. Let P be the product of all odd integers up to n. Then consider

P · 2^{k−1} · S_{n} = ∑_{i=1}^{n} \frac{P · 2^{k−1}}{i} .

Then every term of the sum, except for one, namely that with i = 2^{k}, is an integer. Hence the sum is not an integer, and so neither is S_{n}.

1.4 If we represent every natural number by its’ set of prime divisors, one for each prime including repititions, then the equation reduces to the following relation on sets, which is easy to verify :

(A ∪ B) ∩ (B ∪ C) ∩ (C ∩ A) = (A ∩ B) ∪ (B ∩ C) ∪ (C ∩ A).

1.8 By repeated application of the identity

x^{2} − 1 = (x − 1)(x + 1),

we can in fact show that

2^{2^{m}} − 1 = ∏_{n=1}^{m−1} (2^{2^{n}} + 1) ,  (1)

which in particular implies that 2^{2^{n}} + 1 divides 2^{2^{m}} − 1 for all n < m. Then since

2^{2^{m}} + 1 = (2^{2^{m}} − 1) + 2

any common divisor of 2^{2^{n}} + 1 and 2^{2^{m}} + 1 must also divide 2. But 2^{2^{m}} + 1 is at the very least an odd number, so the GCD is indeed one.

1.9 That p_{n+1} ≤ 2^{2^{n}} + 1 now follows from the fact that the numbers 2^{2^{k}} + 1 have no common factor, for k = 0, ..., n.

Now let x ≥ 2 and let n be the unique integer such that

2^{2^{n}} + 1 ≤ x < 2^{2^{n+1}} + 1.

For all x ∈ R, a simple computation shows that

log_{2} log_{2} x − log log x = log log x (\frac{1}{log 2} − 1) − \frac{log log 2}{log 2}.

Clearly, the rhs is an increasing function of x and one may check, with a calculator if necessary, that it is ≥ 1 for all x ≥ 20. In addition, for all x ≥ \frac{e}{e−1}, we have that

log(x − 1) ≥ log x − 1.

Thus, assuming x ≥ 20, we have that

π(x) ≥ π(2^{2^{n}} + 1) ≥ n + 1 = log_{2} log_{2} 2^{2^{n+1}}
≥ (log log 2^{2^{n+1}}) + 1 ≥ (log log(2^{2^{n+1}} + 1) − 1) + 1
= log log(2^{2^{n+1}} + 1) > log log x.

This proves the desired inequality, at least for all x ≥ 20. For smaller x, it can be checked directly with a calculator.

2.2 (a) If

n = ∏_{i=1}^{k} p_{i}^{α_{i}}

then

∑_{d|n} Λ(d) = ∑_{i=1}^{k} α_{i} log p_{i} = log (∏_{i=1}^{k} p_{i}^{α_{i}}) = log n.

(b) We claim that, for Re(s) > 1,

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

One way to prove this as follows. First, by part (a) and the Möbius inversion formula, we have that

Λ(n) = ∑_{d|n} μ(d) log d.  (3)

Next, we have that

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

For a proof, see 2000 lecture notes, Sats 16, p.21. Thirdly, by differentiating the ζ-function termwise, we find that

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

Hence,

−\frac{ζ′(s)}{ζ(s)} = (∑_{n=1}^{∞} \frac{log n}{n^{s}}) (∑_{n=1}^{∞} \frac{μ(n)}{n^{s}}) = ∑_{n=1}^{∞} n^{−s} (∑_{d|n} μ(d) log d)

which, by (3), is precsiely the lhs of (2).

2.4 Obs! The result does not hold for n = 1, so it should state in the question that n > 1.

You learned in school that

∑_{a=1}^{n} a^{3} = (\frac{n(n + 1)}{2})^{2} .

Let

f(n) := \frac{1}{n^{3}} ∑_{a=1}^{n} a^{3} = \frac{n}{4} + \frac{1}{2} + \frac{1}{4n},

and

g(n) := \frac{1}{n^{3}} ∑_{a=1, (a,n)=1}^{n} a^{3}.

The essential point is that

f(n) = ∑_{d|n} g(d),

which you should be able to see directly. Then the Möbius inversion formula implies that

g(n) = ∑_{d|n} μ(d)f(n/d)

= ∑_{d|n} μ(d) (\frac{n}{4d} + \frac{1}{2} + \frac{d}{4n})

= \frac{n}{4} ∑_{d|n} \frac{μ(d)}{d} + \frac{1}{2} ∑_{d|n} μ(d) + \frac{1}{4n} ∑_{d|n} dμ(d).

The desired result will now follow if we can prove each of the following relations :

∑_{d|n} \frac{μ(d)}{d} = \frac{ϕ(n)}{n},  (4)
∑_{d|n} μ(d) = 0,  (5)

∑_{d|n} dμ(d) = (−1)^{k}p_{1} ⋯ p_{k} \frac{ϕ(n)}{n}.  (6)

First, (5) follows from the fact that the function ν(n), as defined in class and in Baker, p.10, is identically zero for all n > 1. The other two relations both follow easily from the identity (proven in class)

\frac{ϕ(n)}{n} = ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} ) .

(4) follows immediately, was proven in class, and is on the middle of p.11 in Baker. For (6), observe that the lhs is just

∏_{i=1}^{k}(1 − p_{i}),

and work it out for yourself from there.

2.6 (i) It suffices to prove the identity for x an integer. Let [x] denote the set of integers from 1 to x (this notation is common in combinatorics, but not in number theory where it can be confused with ‘integer part of x’). Suppose there are k primes up to and including x, say p_{1}, ..., p_{k}. For i = 1, ..., k let

A_{i} := {t : 1 ≤ t ≤ x and p_{i}|t}.

Observe that

|A_{i}| = ⌊\frac{x}{p_{i}} ⌋.

The only number in the set [x] which is not in the union of the A_{i} is the number 1. Then the point is that the sum

∑_{n≤x} μ(n)⌊\frac{x}{n}⌋

counts this one-element set by the Inclusion-Exclusion principle.

(ii) Recall that, for a real number t, {t} denotes t − ⌊t⌋. Then part (i) implies that

1 = ∑_{n≤x} μ(n) (\frac{x}{n} − \{\frac{x}{n}\})

⇒ ∑_{n≤x} \frac{μ(n)}{n} = \frac{1}{x} (1 + ∑_{n≤x} μ(x) \{\frac{x}{n}\}) .

Hence, it suffices to prove the double inequality

−x − 1 ≤ ∑_{n≤x} μ(n) \{\frac{x}{n}\} ≤ x − 1.

The left-hand inequality follows trivially from the fact that there are only x terms in the sum, and the absolute value of each is less than one. Similarly for the right-hand inequality, since the term for n = 2 is negative.

2.8 The formula for a geometric sum gives

∑_{m=0}^{∞} x^{m} = \frac{1}{1 − x}.  (7)

Using this, the lhs of the identity we must prove can be written as the double sum

∑_{n=1}^{∞} ϕ(n)x^{n} ( ∑_{m=0}^{∞} x^{mn})

= ∑_{n=1}^{∞} ϕ(n) ( ∑_{m=1}^{∞} x^{mn}) .

Interchanging the order of summation, we can rewrite this expression as

∑_{m=1}^{∞} x^{m} (∑_{d|m} ϕ(d)) .

But (as we saw in class, or see p.10 of Baker)

∑_{d|m} ϕ(d) = m.

Finally, differentiating (7) w.r.t. x leads to

∑_{m=1}^{∞} mx^{m} = \frac{x}{(1 − x)^{2}} ,

as required.