Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

  1. 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.

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

share|cite|improve this question
up vote 8 down vote accepted

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$.

share|cite|improve this answer
Is there a general form of the first sentence you stated? – AlanH Jun 2 '13 at 4:53
One can get generalization to $x^k\equiv a\pmod{p}$, criterion for existence of solution, a count on the number of solutions. Not as well developed as the theory of quadratic residues, but pretty good. Might google power residues, indices. – André Nicolas Jun 2 '13 at 5:10

Starting with $2,$ the minimum natural number $>1$ co-prime with $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}$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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