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.
$\endgroup$ 14 Answers
$\begingroup$$13$ divides $x^2+1$ if and only if $13$ divides $x^2+1-26=x^2-25=(x+5)(x-5)$
$\endgroup$ $\begingroup$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$.
$\endgroup$ 0 $\begingroup$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:
$\endgroup$ $\begingroup$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$.
$\endgroup$
