Solutions of the quadratic congruence $x^2\equiv 35\pmod{67}$

Question

What are the solutions of the following quadratic congruence?

$$x^2\equiv 35\pmod{67}$$

I can prove that the congruence has a solution but I can't find the solutions.

Answer 1

A particular solution is $x^2 = 2*67 + 35 = 169$, giving $x = \pm 13$.

Hence the general solution is $x \equiv 13 \pmod {67}$ or $x \equiv -13 \equiv 54 \pmod{67}$.

Answer 2

Given prime $p = 4k+3$ and $a,x$ such that $x^2 \equiv a \pmod{p}$:

  $(a^{k+1})^2 \equiv x^{4k+4} \equiv x^2 \equiv a \pmod{p}$.

Therefore $(35^{17})^2 \equiv 35 \pmod{67}$.

$35^{17} \equiv 54 \pmod{67}$.