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?
 A: If $p$ is  an odd prime, and $a$ is not divisible by $p$, then the congruence $x^2\equiv a\pmod{p}$ has $0$ or $2$ solutions modulo $p$. You have found two incongruent solutions. So you have all of them: all solutions are of the form $x=5+13k$ or $x=8+13k$, where $k$ ranges over the integers.
Actually, finding one solution would be enough, for if $x$ is a solution, automatically so is $-x$.  
For prime $p$, there are good algorithms for computing solutions of $x^2\equiv a \pmod{p}$, that are feasible even for enormous $p$. 
If the modulus is not prime, things get more complicated. Suppose that $m$ is an odd number $\gt 1$. Let  the number of distinct prime divisors of $m$ be $e$. Then the congruence $x^2\equiv a\pmod{m}$, where $a$ and $m$ are relatively prime, either has $0$ solutions or $2^e$ solutions.
Finding the solutions can be computationally difficult. If $m$ is the product of two distinct primes, then finding the solutions is essentially equivalent to factoring $m$. This is believed to be in general computionally very difficult for enormous $m$. 
A: 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}$
A: We can do this avoiding the congruence machinery,although it is essentially
the same idea. Let x = 13a + b, where 0<=b<=12.
Then x^2 +1 = 169a^2 + 26ab + b^2 +1.You only need to find values of b such
that b^2 + 1 is divisible by 13.This is a very small sample,as you found that
b = 5 or b =8.Then x =13a +5 or x = 13a +8,and you have infinitely many answers.
Edwin Gray
