Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers 2

up vote 7 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|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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.