Inlämningsuppgift 2 : Lösningar

3.2 Obs! It should be stated in the question that n > 1, because the result does not hold for n = 1.

If y = n − x then, for any integer a,

\{\frac{ay}{n} \} = \{a − \frac{ax}{n}\} = 1 − \{\frac{ax}{n}\} .

Hence, if ϕ(n) is even, we can pair up terms x and n − x, and each pair contributes exactly one to the sum. This implies that the total sum is then \frac{1}{2}ϕ(n), as desired.

Now it follows from the Chinese Remainder Theorem that ϕ(n) is even for all n > 2. Finally, for n = 2, there is only one term in the sum, namely x = 1, and since a must in this case be odd, this term is \frac{1}{2} = \frac{1}{2}ϕ(2), q.e.d.

3.5 Obs! We will in addition prove that there exists a primitive root modulo n if and only if n is a power of an odd prime, or twice such a number.

That there exists a primitive root modulo n just means that the group (Z/nZ)^{×} is cyclic. Now if

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

then we have seen that

(Z/nZ)^{×} ≅ ∏_{i=1}^{k}(Z/p_{i}^{α_{i}}Z)^{×}.

Now, in general, a direct product of groups is cyclic if and only if (i) each of the factors is cyclic (ii) the factors have coprime orders.

Now (i) is satisfied if and only if n is not divisible by 8, as we have seen in class. But (ii) is rarely satisfied, since ϕ(p^{α}) is even for all odd p, and for all α > 1 when p = 2 (see 3.2 above). This proves our claim about for which n there exist primitive roots modulo n.

Finally, suppose a primitive root exists, i.e.: that the group (Z/nZ)^{×} is cyclic. That the number of primitive roots is then ϕ(ϕ(n)) follows from the following general group-theoretic fact, also mentioned in class :

Fact : If G is a finite cyclic group, then the number of elements of G which are generators is just ϕ(|G|).

3.6 Låt K = \overline{F_{p}}, det algebraiska höljet av F_{p}. Betrakta funktionerna f, g : N → K som ges av

f(n) = summan av alla rötter av x^{n} − 1,  (1)
g(n) = summan av alla primitiva rötter av x^{n} − 1.  (2)

Direkt från dessa definitioner får man att

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

Då antyder Möbius inversion formeln (som gäller för funktioner till en godtycklig kropp, inte bara C) att

g(n) = ∑_{d|n} μ(d)f(\frac{n}{d}).  (4)

Men från enkel algebra vet vi att summan av alla rötterna till ett monic polynom av grad n är lika med minus koefficienten av x^{n−1}. Tillämpning till polynomet x^{n} − 1 antyder att

f(n) = \{ \begin{matrix}1, & om n = 1 \\ 0, & om n > 1. \end{matrix} (5)

Substitution av (5) i (4) ger att g(n) = μ(n), som ger det begärade resultatet om vi tar n = p − 1.

3.8 Täljaren i summan är

S := ∑_{k=1}^{p−1} \frac{(p − 1)!}{k}.

Betrakta polynomet

f(x) = ∏_{k=1}^{p−1}(x − k) = x^{p−1} + a_{p−2}x^{p−2} + ... + a_{1}x + a_{0}.

Notera att

(i) S = −α_{1}. (ii) a_{0} = (p − 1)!. (iii) f(x) ≡ x^{p−1} − 1 (mod p),

där (iii) följer från att x^{p−1} − 1 splittrar i en produkt av linjära faktorer över F_{p} (Fermats lilla sats).

Wilsons sats (s.20 i boken) säger att (p − 1)! ≡ −1 (mod p). Då från (ii) och (iii) får vi att

(iv) p | a_{i} för varje i, 1 ≤ i ≤ p − 2.

Betrakta nu f(p). Från produkt representationen av f ser vi att f(p) = (p − 1)!. Från (ii) följer det att

p^{p−1} + ∑_{i=1}^{p−1} a_{i}p^{i} = 0.  (6)

Vi tittar nu på (6) modulo p^{3}. Om p > 3 det följer från (iv) att (6) reducerar till a_{1}p ≡ 0 (mod p^{3}). Det följer att p^{2} | a_{1}, som bevisar det begärade resultatet, på grund av (i).

4.2 Since p = (p′ − 1)/2, Eulers criterion says that

2^{p} ≡ 1 (mod p′) ⇔ (\frac{2}{p′} ) = 1.

From Gauβ’ lemma, the latter holds if and only if p′ ≡ ±1 (mod 8). But p ≡ 3 (mod 4) and so p′ = 2p + 1 ≡ −1 (mod 8), which suffices !

4.4 Since p ≡ 1 (mod 4), r is a quadratic residue if and only if p − r is. Hence

∑ r = ∑(p − r),

which implies that

2 · ∑ r = ∑ p,

where the sum is taken over all quadratic residues. Since there are \frac{1}{2}(p − 1) of these, the last sum is just \frac{1}{2}p(p − 1). The result follows.

4.6 If p divides d, then there is just one solution, namely x ≡ 0. Otherwise, there is either no solution or two (x and p − x), depending on whether (\frac{d}{p}) = −1 or +1. That’s all there is to it !

4.7 (i) Notera att 4af(x) = (2ax + b)^{2} − d. Också, (\frac{4a}{p}) = (\frac{a}{p}). Då är den givna ekvationen ekvivalent med (vi antar här att d ≢ 0 (mod p))

∑_{x=1}^{p} (\frac{(2ax + b)^{2} − d}{p}) = −1.  (7)

Notera att, eftersom (a, p) = 1, när x rör över alla residue klasserna mod p, detsamma gäller för 2ax + b. Därför kan (7) skrivas om som

∑_{x=1}^{p} (\frac{x^{2} − d}{p}) = −1.  (8)

Det räcker att visa att summan är ≡ −1 (mod p). För varje term i summan är antingen +1 eller −1, så om summan är ≡ −1 (mod p), då måste den vara antingen −1 eller p − 1. Om den var p − 1, skulle det betyda att varje term i summan var +1, utom en term som var 0. Men att det finns en term = 0 är samma sak som att säga att x^{2} ≡ d (mod p) har en lösning. Men då har den två olika lösningar, ±x, eftersom d ≢ 0.

För att visa att summan är ≡ −1 (mod p), använder vi Euler’s kriterium. Det ger att, mod p,

∑_{x=1}^{p} (\frac{x^{2} − d}{p}) ≡ ∑_{x=1}^{p}(x^{2} − d)^{\frac{p−1}{2}} = ∑_{j=0}^{t} ( \begin{matrix}t \\ j \end{matrix} ) (−d)^{j} ∑_{x=1}^{p} x^{2(t−j)},

där t = \frac{1}{2}(p − 1). Men

∑_{x=1}^{p} x^{n} ≡ \{ \begin{matrix}−1, & om p − 1|n, \\ 0, & annars, \end{matrix}  (9)

någonting som följer från ekv. (44) i mina föreläsningsanteckningar från 2000. Ekv. (8) följer.

(ii) Om d ≡ 0 mod p, då får vi från (8) att ∑ (\frac{x^{2}−d}{p}) = ∑ (\frac{x^{2}}{p} ) = p − 1, så att

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

4.8 (i) By an argument similar to the solution of exercise 4.4 above, we find that 2 is not a quadratic residue modulo p. Now the order of 2 in (Z/pZ)^{×} must divide p − 1 = 2p′. Since p′ is prime, the only such divisors are 1, 2, p′ and 2p′. That 2 is not a quadratic residue rules out 1 and p′. Hence if 2 is not to be a primitive root, the only option left is that 2^{2} ≡ 1 (mod p) : in other words, that p = 3, which is plainly ridiculous. (ii) Following the same idea, 5 will be a primitive root modulo p if and only if

(a) 5^{2} ≢ 1 (mod p),

(b) (\frac{5}{p}) = −1.

(a) is not satisfied only if p = 2 or 3, both of which are ridiculous. For (b), since 5 ≡ 1 (mod 4), Gauβ reciprocity says that

(\frac{5}{p}) = (\frac{p}{5}) .

The latter is −1 if and only if p ≡ 2 or 3 (mod 5). Since p′ = (p − 1)/2, this corresponds to p′ ≡ 1 or 3 (mod 5).

S.1 There is a solution to the congruence

x^{2} ≡ 456781 (mod 1708297)  (10)

if and only if there are solutions to each of the congruences

x^{2} ≡ 456781 (mod 1237)  (11)
x^{2} ≡ 456781 (mod 1381),  (12)

in which case each of (11) and (12) has two solutions (note that 1237 and 1381 are both primes) and (10) has four. To check whether either of the congruences (11), (12) is solvable, we can manipulate Jacobi symbols using Jacobi reciprocity. However, I’m far too lazy to write out the computation here, and will do it in class instead.

S.2 Från ekv. (33) år 2000, har vi att

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

Resultatet följer nu från ekv. (26) år 2000.

S.3 Låt 0 < n < p vara den minsta kvadratiska icke-resten modulo p. Låt 0 < m < p vara det minsta talet så att mn > p. Då är 0 < mn − p < n så valet av n antyder att

1 = (\frac{mn − p}{p}) = (\frac{mn}{p}) = (\frac{m}{p}) (\frac{n}{p}) = − (\frac{m}{p}) ⇒ (\frac{m}{p}) = −1.

En gång till, valet av n antyder att m ≥ n. Men då har vi att

(n − 1)n ≤ (m − 1)n < p ⇒ n < 1 + \sqrt{p}, q.e.d.

S.4 The following is an exercise I have seen in several of those enormous American calculus textbooks :

Let ϕ : R → R be an additive function, i.e.:

ϕ(x + y) = ϕ(x) + ϕ(y), ∀ x, y ∈ R.

If ϕ is continuous, then it is linear, i.e.: there exists a real number r such that

ϕ(x) = rx, ∀ x ∈ R.  (13)

Note that the constant r in (13) equals ϕ(1). It follows that the correspondence ϕ ↔ ϕ(1) establishes an isomorphism between the additive group R and the group G of continuous, addtive functions on R.

The proof of the above result goes as follows : Let ϕ be continuous and additive. We have to show that, for all x ∈ R,

ϕ(x) = ϕ(1) · x.  (14)

Step 1 : x = n is a positive integer. Use induction on n. Additivity implies that

ϕ(n) = ϕ[(n − 1) + 1] = ϕ(n − 1) + ϕ(1) = (n − 1)ϕ(1) + ϕ(1) = nϕ(1).

Step 2 : x = 0. ϕ(0) = 0 since

ϕ(0) = ϕ(0 + 0) = ϕ(0) + ϕ(0) ⇒ ϕ(0) = 0.

Step 3 : x = −n is a negative integer. Then

0 = ϕ(0) = ϕ(−n + n) = ϕ(−n) + ϕ(n) ⇒ ϕ(−n) = −ϕ(n) = −nϕ(1).

Step 4 : x = p/q is a rational number. Then additivity yields

pϕ(1) = ϕ(p) = ϕ(q · \frac{p}{q}) = qϕ̇(p/q) ⇒ ϕ(p/q) = \frac{p}{q}ϕ(1).

Step 5 : x is an irrational number. Then x is the limit of a sequence of rational numbers, for all of which (14) holds. So use continuity !!

OK, we’ve solved the US calculus book problem : so what has this to do with exercise S.4 ? Well, if χ is a continuous character of R, then

ϕ := \frac{1}{2πi} log χ

is a continuous additive function on R. Work it out from here for yourself !

S.5 I will present this solution in class, as it’s a bit ‘krånglig’ to write down.