How to find least positive integer

Question

A university exam paper gave a short question of this type-

Find least positive integer $x$ such that $13|(x^2+1)$.

It may be an easy problem but I am clueless that without anymore conditions how to determine the value of $x$.

I understand how to apply congruence basics but here in the problem I don't know where to start and how to determine $x$.

What I think if $13$ divides $x^2+1$ then by divisibility rule, there exist a positive integer $m$ such that, $x^2+1=13.m$, which implies

$$x^2=13.m-1 $$.
$$\Rightarrow x=\sqrt{13.m-1}$$
Now for the consecutive positive interger values of $m$, if $x$ is not exceeding $13$, then positive interger values of $x$ are $2,3,4,....$ and so on and the least positive interger becomes $2$, when $m=1$.

I have doubt in my process. Any help is appreciated.

Answer 1

You want $x^2 \equiv -1 \mod 13$. There aren't that many numbers to check: since $(13-x)^2 \equiv x^2 \mod 13$, if there is such an $x$ it has to be one of $0, 1, 2, \ldots, 6$.

Answer 2

$13$ divides $x^2+1$ if and only if $13$ divides $x^2+1-26=x^2-25=(x+5)(x-5)$

Answer 3

You are effectively asked to solve $x^2 = -1 \pmod{13}$.

This is easiest by trial and error, because you will only have to try $2,3,4,5,6$. The answer is $x=5$.

If $13$ were replaced by some generic large prime so that the trial and error would be too time consuming, see Cipolla's algorithm:

https://en.wikipedia.org/wiki/Cipolla%27s_algorithm

Answer 4

You can rewrite the congruence $x^2\equiv -1 \bmod 13$ as an equation $x^2+1=0$ in the field $\mathbb{F}_{13}$. There it factors, using Berlekamp, or just $x^2+1-26=0$ as $$ (x+5)(x+8)=0. $$ So we have $2$ solutions. Modulo $13$ we can represent the solutions as $5$ and $-5\equiv 8$.