Solution
(related to Problem: Applications of the Jacobi Symbol)
Ad 1
- $443$ is a prime number, and the solvability of the quadratic congruence can be decided by the calculating the Legendre symbol $\left(\frac{383}{443}\right).$
- In order to do this, we can use the properties of the Jacobi symbol:
$$\begin{array}{rcll}
\left(\frac{383}{443}\right)&=&-\left(\frac{443}{383}\right)&\text{reciprocity law}\\
&=&-\left(\frac{60}{383}\right)&\text{equal residues}\\
&=&-\left(\frac{2}{383}\right)^2\left(\frac{15}{383}\right)&\text{definition of the Jacobi symbol}\\
&=&-\left(\frac{15}{383}\right)&\text{second supplementary law}\\
&=&\left(\frac{383}{15}\right)&\text{reciprocity law}\\
&=&\left(\frac{8}{15}\right)&\text{equal residues}\\
&=&\left(\frac{2}{15}\right)^3&\text{definition of the Jacobi symbol}\\
&=&1&\text{second supplementary law}\\
\end{array}$$
- It follows that the quadratic congruence $x^2\equiv 383\mod 443$ is solvable.
Ad 2
- $87$ is not a prime number, however, $35$ and $87$ are co-prime.
- We use again the properties of the Jacobi symbol:
$$\begin{array}{rcll}
\left(\frac{35}{87}\right)&=&-\left(\frac{87}{35}\right)&\text{reciprocity law}\\
&=&-\left(\frac{17}{35}\right)&\text{equal residues}\\
&=&-\left(\frac{35}{17}\right)&\text{reciprocity law}\\
&=&-\left(\frac{1}{17}\right)&\text{equal residues}\\
&=&-1\\
\end{array}$$
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927