 Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2023/1/c/ii/solution

For

f (x) = x^{2} - n

p

is nonzero because

p ∤ n

2 x

is therefore nonzero modulo

p

. Part (i) gives exactly one lift of each root. A nonzero quadratic residue modulo an odd prime has two distinct roots,

x

and

- x

; a nonresidue has none. Hence

# {x (mod p^{l}) : x^{2} \equiv n} = 1 + (\frac{n}{p}) \in {0, 2} .

 New to topics? Read the docs here!