0
$\begingroup$

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$
  • $\begingroup$ How about trying $x=1$, $x=2$ etc., until you find one that works? $\endgroup$ – Lord Shark the Unknown Mar 5 '18 at 19:48
1
$\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$
3
$\begingroup$

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

$\endgroup$
1
$\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:

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

$\endgroup$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.