FINAL EXAM SOLUTIONS MATH 115: NUMBER THEORY

Problem 1. The congruence implies that p^{k} | (x^{2} − 1) = (x − 1)(x + 1). Now, if p is an odd prime such that p | (x − 1) and p | (x + 1), then p | (x − 1) + (x + 1) = 2x so since p is odd, p | x. Thus p | x − (x − 1) = 1, a contradiction. Therefore either p^{k} | (x − 1) or p^{k} | (x + 1), hence x ≡ ±1 (mod p^{k}).

Alternatively, we know that f(x) = x^{2} − 1 ≡ 0 (mod p) which has only the solutions x ≡ ±1 (mod p); by Hensel’s lemma, since f′(±1) = ±2 ≢ 0 (mod p), these lift uniquely, so there are exactly two solutions modulo p^{k}, hence they must be x ≡ ±1 (mod p^{k}).

[N.B. There is also a solution which uses the fact that p^{k} has a primitive root!]

Problem 2. First, the congruence has the solution x ≡ 1 (mod 3) for p = 3. Now assume p ≠ 3, so that x ≡ 1 (mod p) is not a solution. Note that

(x − 1)(x^{2} + x + 1) = x^{3} − 1 ≡ 0 (mod p).

Therefore the original congruence has a solution if and only if there is a nontrivial solution to this congruence, i.e. an element of order 3. This happens if and only if 3 | (p − 1), i.e. p ≡ 1 (mod 3).

Alternatively, note that by a homework exercise (completing the square), the original congruence has a solution if and only if y^{2} ≡ d ≡ 1^{2}−4(1)(1) = −3 (mod p) has a solution. This has the solution y ≡ 0 (mod 3) if p = 3, and otherwise, we need (−3/p) = 1, which again by a homework exercise (using quadratic reciprocity) we see that p ≡ 1 (mod 3).

Problem 3. We note that

σ(n) = σ(pq) = (p + 1)(q + 1) = pq + p + q + 1 = 51809 + p + q + 1 = 52416,

so p + q = 606. Thus p, q are the roots of

(x − p)(x − q) = x^{2} − (p + q)x + pq = x^{2} − 606x + 51809 = 0

so

p, q = \frac{606 ± \sqrt{606^{2} − 4(51809)}}{2} = 303 ± 200 = 103, 503.

Problem 4. For (a), suppose m, n ∈ ℤ_{≥1} with gcd(m, n) = 1. Note that

f(mn) = (−1)^{mn−1}

and

f(m)f(n) = (−1)^{m−1}(−1)^{n−1} = (−1)^{(m−1)+(n−1)} = (−1)^{m+n}

hence we need to show that

mn − 1 ≡ m + n (mod 2).

Date: August 12, 2004.

Since gcd(m, n) = 1, not both of m, n are even. Without loss of generality, then, we may assume m ≡ 0, 1 (mod 2) and n ≡ 1 (mod 2). The congruence is true in both of these cases.

For (b), the easiest method is to use the homework: if n = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}, then

∑_{d|n} μ(d)f(d) = (1 − f(p_{1})) ⋯ (1 − f(p_{r})).

Now if one p_{i} is odd, then f(p_{i}) = 1 so the sum is zero.

To essentially reprove this result, argue as follows: since f is multiplicative and μ is multiplicative, so is their product μf. Therefore, since g is the summatory function of μf, so is g.

So suppose n = p^{e} is an odd prime power, e ≥ 1. Then

g(p^{e}) = ∑_{d|p^{e}} μ(p^{e})f(p^{e}) = μ(1)f(1) + μ(p)f(p) + ⋯ + μ(p^{e})f(p^{e})
= f(1) + f(p) = (−1)^{1−1} − (−1)^{p−1} = 1 − 1 = 0

since p is odd.

Now suppose that n is not a power of 2. Then there is an odd prime p which divides n. Write n = p^{e}m where p ∤ m. Then by multiplicativity,

g(n) = g(p^{e})g(m) = 0.

Problem 5. We first note that p ≡ 1 (mod 4). This follows since

p ≡ a^{2} + 5b^{2} ≡ a^{2} + b^{2} ≡ 0, 1, 2 (mod 4)

but p is an odd prime, so p ≡ 1 (mod 4).

Therefore by quadratic reciprocity, since a is an odd prime,

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

and since a^{2} + 5b^{2} ≡ 5b^{2} (mod a), and (b^{2}/a) = 1 clearly, we have

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

which by quadratic reciprocity is

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

Therefore a is a quadratic residue modulo p if and only if (\frac{a}{5}) = 1. This latter holds if and only if a ≡ ±1 (mod 5), which implies that

p ≡ a^{2} ≡ 1 (mod 5).

Problem 6. By Euler’s theorem, we note that

a^{ϕ(p_{i}^{e_{i}})} ≡ 1 (mod p_{i}^{e_{i}}).

Therefore since ϕ(p_{i}^{e_{i}}) | m, we have

a^{m} ≡ 1 (mod p_{i}^{e_{i}}).

By the Chinese remainder theorem, this implies that

a^{m} ≡ 1 (mod n).

Therefore o(a mod n) | m. This solves (a).

For (b), the answer is “no”. Indeed, if we take n = 8 = 2^{3}, there is no element of order ϕ(8) = 4 modulo 8.

Problem 7. Note first that p ∤ a. Now since o(−a^{2} mod p) | p − 1 = 2q, we have o(−a^{2} mod p) ∈ {1, 2, q, 2q}.

First, suppose o(−a^{2} mod p) | 2, so that

(−a^{2})^{2} ≡ a^{4} ≡ 1 (mod p).

Hence o(a mod p) = 1, 2, 4. If o(a mod p) = 1, 2, then a^{2} ≡ 1 (mod p), so a ≡ ±1 (mod p), a contradiction. If o(a mod p) = 4, then 4 | (p − 1) so p ≡ 2q + 1 ≡ 1 (mod 4), a contradition since q is odd.

Therefore we only need to rule out o(−a^{2} mod p) = q. If so, then

(−a^{2})^{q} ≡ −a^{2q} ≡ 1 (mod p).

But ϕ(p) = p − 1 = 2q, so by Fermat’s little theorem, since p ∤ a, we know that a^{2q} ≡ 1 (mod p). Therefore −a^{2q} ≡ −1 ≡ 1 (mod p), a contradiction since p is odd. Thus o(−a^{2} mod p) = 2q = ϕ(p), so −a^{2} mod p is a primitive root.

Problem 8 (Bonus). [N.B. Note that ϕ(1) = 1 = \sqrt{1}, ϕ(4) = 2 = \sqrt{4} but ϕ(2) = 1 < \sqrt{2} and ϕ(6) = 2 < \sqrt{6}.]

For any real number x ≥ 3, we claim that

x − 1 > \sqrt{x}.

This follows since it is equivalent to

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

and this is equivalent to

f(x) = x^{2} − 3x + 1 > 0.

Note that f is a continuous function; f′(x) = 2x − 3 > 0 for x > 3/2, so f is increasing there; so since f(3) = 9 − 9 + 1 > 0, f(x) > 0 for x ≥ 3.

Now, suppose n = p^{e} is an odd prime power, with e ≥ 1. Then

ϕ(p^{e}) = p^{e−1}(p − 1) > p^{e−1}\sqrt{p}

and since e − 1/2 ≥ e/2 (this is equivalent to e/2 ≥ 1/2, or e ≥ 1), we have

p^{e−1}\sqrt{p} = p^{e−1/2} ≥ p^{e/2} = \sqrt{p^{e}}.

Finally, if n is odd, then

ϕ(n) = ϕ(p_{1}^{e_{1}}) ⋯ ϕ(p_{r}^{e_{r}}) > \sqrt{p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}} = \sqrt{n}.

To conclude, one must treat the case that n is even! We leave it as a challenge to the reader to modify the above argument appropriately.