FINAL EXAM REVIEW SOLUTIONS MATH 115: NUMBER THEORY

Problem 1. If p is odd, then without loss of generality, a is even and b is odd. Therefore

p = a^{2} + b^{2} ≡ 0 + 1 ≡ 1 (mod 4).

For (b), note that since p ≡ 1 (mod 4) is prime and a is prime as well, by quadratic reciprocity,

(\frac{a}{p}) = (\frac{p}{a}) = (\frac{a^{2} + b^{2}}{a} ) .

Now the Legendre symbol only depends on the numerator modulo a, so since a^{2} + b^{2} ≡ b^{2} (mod a), we have

(\frac{a^{2} + b^{2}}{a} ) = (\frac{b^{2}}{a} ) = 1.

Problem 2. We compute using quadratic reciprocity:

(\frac{103}{229}) = (\frac{229}{103}) = (\frac{23}{103}) = − (\frac{103}{23}) = − (\frac{11}{23}) = (\frac{23}{11}) = (\frac{1}{11}) = 1.

Problem 3. Since 3^{p} + 1 ≡ 0 (mod n), we have 3^{p} ≡ −1 (mod n), hence 3^{2p} ≡ 1 (mod n). Therefore h = o(3 mod n) | 2p, hence h ∈ {1, 2, p, 2p}. If h = 1, then 3^{1} = 3 ≡ 1 (mod n), so n | (3 − 1) = 2, but we see that n ≥ 28, so this is impossible. Similarly, if h = 2, then 3^{2} = 9 ≡ 1 (mod n), so n | 8, impossible. Finally, if h = p, then 3^{p} ≡ 1 ≡ −1 (mod n), which is again impossible. Therefore h = o(3 mod n) = 2p.

For (b), first note that the arguments above work with n replaced by q. We have the same congruences (except modulo q), and now we cannot have 3 ≡ 1 (mod q) or 9 ≡ 1 (mod q) since q is odd. So o(3 mod q) = 2p. Therefore 2p | (q − 1), so 2pk = q − 1, hence q = 1 + 2pk.

Problem 4. Let n = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}, with e_{i} > 0, p_{i} prime. Then

ϕ(n) = p_{1}^{e_{1}−1}(p_{1} − 1) ⋯ p_{r}^{e_{r}−1}(p_{r} − 1) | 3p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}.

Cancelling the common factors from both sides, we see this can happen if and only if

(p_{1} − 1) ⋯ (p_{r} − 1) | 3p_{1} ⋯ p_{r}.

Now note that if p is odd, then p − 1 is even. Therefore the left-hand side is divisible by at least r − 1 factors of 2, since only one of the primes can be 2. On the other hand, the right-hand side is divisible by at most 2 (at not 4) for the same reason. Therefore n can have at most one odd prime divisor, so either n = 2^{e}, n = p^{f}, or n = 2^{e}p^{f} for some odd prime p and e, f ≥ 1. In the first case, we have ϕ(2^{e}) = 2^{e−1} | 2^{e} indeed. In the second case, we have ϕ(p^{f}) = p^{f−1}(p − 1) ∤ p^{f}, since p − 1 is even but p^{f} is odd. In the last case, we have

(2 − 1)(p − 1) = (p − 1) | 3 · 2 · p.

Since gcd(p − 1, p) = 1, this implies p − 1 | 6, so p = 2, 3, 4, 7, hence p = 3, 7. Checking these, we conclude that n = 1, n = 2^{e}, n = 2^{e}3^{f}, or n = 2^{e}7^{f} for e, f ≥ 1.

Problem 5. We take log_{3} of both sides to get

log_{3}(x^{40}) = 40 log_{3} x ≡ log_{3} 2 (mod 78).

Now log_{3} 2 = 4 since 3^{4} = 81 ≡ 2 (mod 79). Therefore we solve

40 log_{3} x ≡ 4 (mod 78).

Now gcd(40, 78) = 2 | 4, so this becomes

20 log_{3} x ≡ 2 (mod 39).

Note that 20^{−1} ≡ 2 (mod 39), since 20 · 2 ≡ 1 (mod 39), hence

log_{3} x ≡ 20^{−1}2 ≡ 4 (mod 39).

Therefore log_{3} x = 4, 43, and x ≡ 3^{4}, 3^{43} (mod 79). We compute that 3^{4} ≡ 2 (mod 79), and although it would be painful to compute 3^{43} (mod 79), we notice that −2 is also a solution to the congruence, hence 3^{43} ≡ −2 (mod 79).

For part (b), note that by (a) we have 2^{40} ≡ 2 (mod 79), hence 2^{39} ≡ 1 (mod 79), hence o(2 mod 79) | 39. Hence o(2 mod 79) ≠ 78, so no, 2 is not a primitive root.

Problem 6. Let N = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}. Then

σ(N) = \frac{p_{1}^{e_{1}+1} − 1}{p_{1} − 1} ⋯ \frac{p_{r}^{e_{r}+1} − 1}{p_{r} − 1} = 2N = 2p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}.

Dividing both sides by p_{1}^{e_{1}+1} ⋯ p_{r}^{e_{r}+1} and multiplying by (p_{1} − 1) ⋯ (p_{r} − 1), we obtain

\frac{p_{1}^{e_{1}+1} − 1}{p_{1}^{e_{1}+1}} ⋯ \frac{p_{r}^{e_{r}+1} − 1}{p_{r}^{e_{r}+1}} = 2\frac{p_{1} − 1}{p_{1}} ⋯ \frac{p_{r} − 1}{p_{r}}

which rearranging becomes

(1 − \frac{1}{p_{1}} ) ⋯ (1 − \frac{1}{p_{r}} ) = \frac{1}{2}(1 − \frac{1}{p_{1}^{e_{1}+1}} ) ⋯ (1 − \frac{1}{p_{r}^{e_{r}+1}} ) < \frac{1}{2}.

Problem 7. We compute that ϕ(n) = 16 · 82 = 1312 and using the extended Euclidean algorithm that d ≡ e^{−1} ≡ 835^{−1} ≡ 11 (mod 1312). Thus P ≡ C^{d} ≡ 2^{11} ≡ 2048 ≡ 637 (mod 1411) is her PIN number.

Problem 8. Note that if a has order h and b has order k modulo p, with gcd(h, k) = 1, then ab has order hk modulo p. Together with the fact that −1 has order 2 modulo p, we conclude that

−53 · 39 ≡ 29 (mod 131)

has order 2 · 5 · 13 = p − 1 modulo p, so r = 29 is a primitive root.

Problem 9. Consider the equation x^{2} ≡ a (mod p). Taking log_{r} of both sides, we obtain

2 log_{r} x ≡ log_{r} a (mod p − 1).

This has a solution if and only if gcd(2, p − 1) = 2 | log_{r} a, so a is a quadratic residue if and only if log_{r} a is even.

For (b), we write a ≡ r^{log_{r} a} (mod p). Now r^{u} mod p is a primitive root if and only if gcd(u, p − 1) = 1. If a is quadratic residue, then u = log_{r} a is even, so gcd(u, p − 1) = 2, so a is not a primitive root.

For (c), all of the primitive roots modulo p are quadratic nonresidues by (a), so there are ϕ(ϕ(p)) such (of the (p − 1)/2 quadratic nonresidues).

Problem 10. We apply Möbius inversion; since σ_{k}(n) is the summatory function of f(n) = n^{k}, we conclude

∑_{d|n} μ(d)σ_{k}(n/d) = n^{k}.

For (b), we first note that f(n) = n^{k} is (completely) multiplicative (f(mn) = (mn)^{k} = m^{k}n^{k} = f(m)f(n)). Therefore σ_{k}(n) is multiplicative since it is the summatory function of f which is multiplicative. Now μ(n)σ_{k}(n) is multiplicative as well, since μ is multiplicative and hence

μ(mn)σ_{k}(mn) = μ(m)μ(n)σ_{k}(m)σ_{k}(n) = (μ(m)σ_{k}(m))(μ(n)σ_{k}(n)),

if gcd(m, n) = 1. Finally, S_{k}(n) is the summatory function of μ(n)σ_{k}(n), so it is also multiplicative.

Thanks everyone, you were a great class. Good luck on the final!