$x^2$ is congruent to $-1 \bmod p$ In general, how do you solve $x^2$ is congruent to $-1 \bmod p$, where $p$ is an odd prime and $x$ is an integer.
Specifically, I need to solve $x^2\equiv-1 \pmod{29}$
 A: Since you can figure out
$$ 29 = 25 + 4 = 5^2 + 2^2 $$
in your head, you see
$$ 5^2 + 2^2 \equiv 0 \pmod {29}, $$
$$ 5^2 \equiv - 2^2 \pmod {29}. $$
Bothe 2 and 5 are relatively prime to $29,$ either one has a multiplicative inverse mod 29.
$$ \frac{5^2}{2^2} \equiv -1 \pmod {29},  $$
$$ \left( \frac{5}{2} \right)^2 \equiv -1 \pmod {29}.  $$
So, you need to figure out the multiplicative inverse of $2 \pmod {29}$ and multiply that by $5.$ whatever that becomes $\pmod {29}$ is what you need.
Not a coincidence: the other square root is
$$ - \frac{5}{2} \equiv \frac{2}{5} \pmod{29}.  $$
A: If $x^2 \equiv -1 \mod 29$ then $(-x)^2 \equiv -1 \mod 29$  So I only need to check $x = \pm 1.... \pm 14$
If $x^2 \equiv -1 \mod 29$ then $x^2 = 29m - 1$. And $m \le 14 \implies 29m - 1 \le 14^2 = 28*7 \approx 29*7 -1$ so we just need to check the first $7$ multiples of $29$.
They are $28, 57, 86, 115, 144, 173, 202$.  Of those only $144 = (\pm 12)^2$ is a perfect square.
So $x = 12, 17$.
I'm not sure how to do this other than trial and error. 
A: $a\equiv b(m\acute{o}d\, p)$ iff $p|(a-b)$ thus $x^2\equiv-1(m\acute{o}d\,29)$ implies $29|x^2+1$ then exists $m\in\mathbb{Z}$ such that $x^2+1=29m$ so, $x=\pm\sqrt{29m-1}$, then you need $29m-1\geq 0$ so, $m\in \mathbb{N}$ it's sufficient.
A: As $29$ is a small prime, you simply compute the first squares modulo $29$:
$$\begin{array}{c|cccccc}
n&\pm1&\pm 2&\pm3&\pm4&\pm 5&\dotsm \\
\hline
n^2&1&4&9&16&-4&\dotsm
\end{array}$$
Now  we have $5^2=(-1)2^2$, whence $-1=(5\cdot2^{-1})^2$. As $2^{-1}=15$, we have
$$-1=(5\cdot15)^2=(-12)^2\enspace\text{and of course}\enspace 12^2.$$
