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.
Best Answer
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.