2
$\begingroup$

I am trying to solve the following problem: find all solutions to the congruence $x^2 \equiv 1 \pmod {91}$.

I have solved already the congruence $x^2 \equiv 1 \pmod 7$ and $\!\!\pmod {13}$, and I am trying to use the Chinese Remainder Theorem. However, I am puzzled by how exactly to use it in this case. I do know that $x \equiv \pm 1 \pmod 7$ and $\!\!\pmod {13}$, since $7$ and $13$ are both prime.

Any help is appreciated here.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/… gives an example. You need (the inverse of 7) mod 13 and (the inverse of 13 mod 7). $\endgroup$ – Christopher Carl Heckman Sep 24 '15 at 6:24
  • $\begingroup$ Ah so I have computed the following: (1) $a \equiv 1$ (mod 7) and $a \equiv 0$ (mod 13) implies $a \equiv 78$. (2) $b \equiv 0$ (mod 7) and $b \equiv 1$ (mod 13) implies $b \equiv 105$. Are these inverses? $\endgroup$ – letsmakemuffinstogether Sep 24 '15 at 6:26
  • 1
    $\begingroup$ No. You need to solve (1) 7 * a = 1 (mod 13) and 13 * b = 1 (mod 7). $\endgroup$ – Christopher Carl Heckman Sep 24 '15 at 6:27
  • $\begingroup$ Ah yes, thank you. My mistake. $\endgroup$ – letsmakemuffinstogether Sep 24 '15 at 6:29
2
$\begingroup$

If $x\equiv 1\pmod 7$ and $x\equiv 1\pmod {13}$ then $x\equiv 1\pmod {91}$.

If $x\equiv -1\pmod 7$ and $x\equiv -1\pmod {13}$ then $x\equiv -1\pmod {91}$.

If $x\equiv 1\pmod 7$ and $x\equiv -1\pmod {13}$ then $x\equiv 64\pmod {91}$.

If $x\equiv -1\pmod 7$ and $x\equiv 1\pmod {13}$ then $x\equiv 27\pmod {91}$.

In each case, the chinese remainder theorem guarantees that the solution you found (by trial-and-error) $\pmod{91}$ is the only one.

$\endgroup$
  • 1
    $\begingroup$ The OP wants to know how you got 1, -1, 64, and 27. $\endgroup$ – Christopher Carl Heckman Sep 24 '15 at 6:26
  • $\begingroup$ @ Sonner - Please explain why you are constructing those ``if...then..." statements as it is not clear how you got those numbers and why they are significant. $\endgroup$ – letsmakemuffinstogether Sep 24 '15 at 18:53
  • $\begingroup$ Let's consider the 3rd case for example. The procedure is this: $x\equiv 1\pmod 7$, so write $x=7a+1$. Now substitute in the second equation: $7a\equiv -2\pmod{13}$. The inverse of $7$ mod $13$ is $2$, so $a\equiv -4\equiv 9\pmod 13$, that is $a=13b+9$. Therefore $x=7(13b+9)+1=91b+64$. However for small cases like these, you can just find which one of $12,25,38,\dots$ is $\equiv 1\pmod 7$, and you'll quickly arrive to $64$. $\endgroup$ – Sonner Sep 24 '15 at 19:44

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.