Find all positive integers $x$ such that $13 \mid (x^2 + 1)$ I was able to solve this by hand to get $x = 5$ and $x =8$. I didn't know if there were more solutions, so I just verified it by WolframAlpha. I set up the congruence relation $x^2 \equiv -1 \mod13$ and just literally just multiplied out. This lead me to two questions:


*

*But I was wondering how would I do this if the $x$'s were really large? It doesn't seem like multiplying out by hand could be the only possible method.

*Further, what if there were 15 or 100 of these $x$'s? How do I know when to stop?

Starting with $2,$ the minimum natural number $>1$ co-prime with $13,$
$2^1=2,2^2=4,2^3=8,2^4=16\equiv3,2^5=32\equiv6,2^6=64\equiv-1\pmod{13}$
As $2^6=(2^3)^2,$ so $2^3=8$ is a solution of $x^2\equiv-1\pmod{13}$
Now, observe that $x^2\equiv a\pmod m\iff (-x)^2\equiv a$
So, $8^2\equiv-1\pmod {13}\iff(-8)^2\equiv-1$
Now, $-8\equiv5\pmod{13}$

If we need $x^2\equiv-1\pmod m$ where integer  $m=\prod p_i^{r_i}$ where $p_i$s are distinct primes and $p_i\equiv1\pmod 4$ for each $i$ (Proof)
$\implies x^2\equiv-1\pmod {p_i^{r_i}}$
Applying Discrete logarithm with respect to any primitive root $g\pmod  {p_i^{r_i}},$
$2ind_gx\equiv \frac{\phi(p_i^{r_i})}2  \pmod {\phi(p_i^{r_i})}$ 
as if $y\equiv-1\pmod {p_i^{r_i}}\implies y^2\equiv1 $
$\implies 2ind_gy\equiv0  \pmod {\phi(p_i^{r_i})}\implies ind_gy\equiv \frac{\phi(p_i^{r_i})}2  \pmod {\phi(p_i^{r_i})}$ as $y\not\equiv0\pmod { {\phi(p_i^{r_i})}}$
Now apply CRT, for relatively prime moduli $p_i^{r_i}$
For example, if $m=13, \phi(13)=12$ and $2$ is a primitive root of $13$ 
So, $2ind_2x\equiv 6\pmod {12}\implies ind_2x=3\pmod 6$
$\implies x=2^3\equiv8\pmod{13}$ and $x=2^9=2^6\cdot2^3\equiv(-1)8\equiv-8\equiv5\pmod{13}$
