# Chinese Remainder Theorem: solving $x^2 \equiv 1 \pmod {91}$.

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.

• en.wikipedia.org/wiki/… gives an example. You need (the inverse of 7) mod 13 and (the inverse of 13 mod 7). Sep 24 '15 at 6:24
• 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? Sep 24 '15 at 6:26
• No. You need to solve (1) 7 * a = 1 (mod 13) and 13 * b = 1 (mod 7). Sep 24 '15 at 6:27
• Ah yes, thank you. My mistake. Sep 24 '15 at 6:29

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.

• The OP wants to know how you got 1, -1, 64, and 27. Sep 24 '15 at 6:26
• @ 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. Sep 24 '15 at 18:53
• 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$. Sep 24 '15 at 19:44