$x^2$ is congruent to $-1 \bmod p$

Question

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}$

Answer 1

$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.

Answer 2

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.$$

Answer 3

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}. $$

Answer 4

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.