 Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2021/1/d/solution

Complete the square to obtain the equivalent quadratic congruence

(x + 3)^{2} \equiv 1111 (mod 8093) .

Here

g cd (1111, 8093) = 1

316, 163, 153, 10, 3, 1

(1111/8093)

would be

1

1

at every prime factor. Calculate instead, using Jacobi reciprocity and reduction of numerators,

(\frac{1111}{8093}) = (\frac{8093}{1111}) = (\frac{316}{1111}) = (\frac{4}{1111}) (\frac{79}{1111}) = (\frac{79}{1111}) = - (\frac{1111}{79}) = - (\frac{5}{79}) = - (\frac{79}{5}) = - (\frac{4}{5}) = - 1. (8093 \equiv 1 (mod 4)) (8093 = 7 \cdot 1111 + 316) (79 \equiv 1111 \equiv 3 (mod 4)) (1111 = 14 \cdot 79 + 5)

Therefore there is no solution. This obstruction does not require a separate primality test for

8093

; the Jacobi symbol suffices.

 New to topics? Read the docs here!