= Solution
{c}
Complete the square to obtain the equivalent <quadratic congruence>
$$
(x+3)^2\equiv1111\pmod{8093}.
$$
Here $\gcd(1111,8093)=1$: the <Euclidean algorithm> has successive nonzero remainders $316,163,153,10,3,1$. If this <modular congruence> had a solution, the <Jacobi symbol> $(1111/8093)$ would be $1$, since a square <coprime> to an odd modulus has <Legendre symbol> $1$ at every <prime factor>. Calculate instead, using <Jacobi reciprocity> and reduction of numerators,
$$
\begin{aligned}
\left(\frac{1111}{8093}\right)
&=\left(\frac{8093}{1111}\right)&& (8093\equiv1\pmod4)\\
&=\left(\frac{316}{1111}\right)&& (8093=7\cdot1111+316)\\
&=\left(\frac4{1111}\right)\left(\frac{79}{1111}\right)=\left(\frac{79}{1111}\right)\\
&=-\left(\frac{1111}{79}\right)&& (79\equiv1111\equiv3\pmod4)\\
&=-\left(\frac5{79}\right)&& (1111=14\cdot79+5)\\
&=-\left(\frac{79}5\right)=-\left(\frac45\right)=-1.
\end{aligned}
$$
Therefore \b[there is no solution]. This obstruction does not require a separate primality test for $8093$; the <Jacobi symbol> suffices.
Back to article page
