Find all solutions to $x^2\equiv 1\pmod {91},\ 91 = 7\cdot 13$ I split this into $x^2\equiv 1\pmod {7}$ and $x^2\equiv 1\pmod {13}$.
For $x^2\equiv 1\pmod {7}$, i did:
$$ (\pm1 )^2\equiv 1\pmod{7}$$ $$(\pm2 )^2\equiv 4\pmod{7}$$ $$(\pm3 )^2\equiv 2\pmod{7}$$ Which shows that the solutions to $x^2\equiv 1\pmod {7}$ are $\pm1$.
For $x^2\equiv 1\pmod {13}$, i did:
$$ (\pm1 )^2\equiv 1\pmod{13}$$ $$(\pm2 )^2\equiv 4\pmod{13}$$ $$(\pm3 )^2\equiv 9\pmod{13}$$ $$ (\pm4 )^2\equiv 3\pmod{13}$$ $$(\pm5 )^2\equiv {-1}\pmod{13}$$ $$(\pm6 )^2\equiv 10\pmod{13}$$Which shows that the solutions to $x^2\equiv 1\pmod {13}$ are $\pm1$.
Thus, I concluded that the solutions to $x^2\equiv 1\pmod {91}$ must be $\pm1$. I thought that $\pm1$ were the only solutions, but apparently I am incorrect! How do I go about finding the other solutions to this congruence?
 A: Hint: Consider the possibility that $x \equiv 1 \pmod 7$ but $x \equiv -1 \pmod {13}$, and so on. (In other words, your mistake was to assume that the $\pm1$ modulo $7$ was the same sign as $\pm1$ modulo $13$.)
Also note that for any prime $p$, if $x^2 \equiv 1 \pmod p$, then we can rewrite this as $$x^2 - 1 \equiv (x+1)(x-1) \equiv 0 \pmod p.$$
Thus we get $x \equiv \pm 1 \pmod p$, showing that it isn't necessary to run through all the values of $x^2$ to find the solution.
A: You have $x\equiv\pm1\mod7$ and $x\equiv\pm1\mod13$. For all the solutions, you have to consider the systems:
$$x\equiv1\mod7$$
$$x\equiv1\mod13$$
and
$$x\equiv-1\mod7$$
$$x\equiv1\mod13$$
and
$$x\equiv1\mod7$$
$$x\equiv-1\mod13$$
and
$$x\equiv-1\mod7$$
$$x\equiv-1\mod13$$
as each system will get you a valid answer. I think you only had the first and the last systems and that you only considered the cases where the signs were similar.
A: By CRT the solutions $\,x\equiv \pm1\pmod{\! 7},\ x\equiv \pm1\pmod{\!13}$ combine to  $\,4\,$ solutions mod $91,\,$ viz $\,x\equiv (\color{#c00}{{\bf 1,1}}),\,(\color{#0a0}{-1,-1}),\,(1,-1),\,(-1,1)\pmod{\!7,13},$ cf. "$\rm\color{#90f}{Combining}$" below. The first two  have solution $\,\color{#c00}{\bf 1}\,$ and $\,\color{#0a0}{-1}\,$ by CCRT. Finally solve $\,x\equiv (1,-1)$, and $(-1,1)\equiv -(1,-1)$ is its negative, i.e. $\,x\equiv 1\pmod{\!7},\,x\equiv -1\pmod{\!13}\ [\!\iff -x\equiv -1\pmod{\!7},\ {-}x\equiv 1\pmod{\!13}\:\!]$ to get $\,x\equiv \pm 27\pmod{91},\,$ the nontrivial $(\not\equiv \pm 1)$ sqrt's of $1,\bmod 91$.
Remark $ $ In more complex cases it's often easier to apply CRT  using generic (symbolic) values, then plug in specific values for all combinations, e.g. see here and here. and many here.
Conversely, given any nontrivial $(\not\equiv \pm1)$ square-root of $1\pmod{\!n}$ we can quickly compute a nontrivial factorization of $n\,$ [we can do that for any polynomial of $\,\deg k\,$ with $\,> k\,$ roots].

$\rm\color{#90f}{Combining}$ $ $ If $\,m,n\,$ are coprime then, by CRT, solving a polynomial $\,f(x)\equiv 0\pmod{\!mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n.\,$ By CRT, each combination of a root $\,r_i\bmod m\,$ and a root $\,s_j\bmod n\,$ corresponds to a unique root $\,t_{ij}\bmod mn,\,$ i.e.
$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{\!mn}&\overset{\,\,\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod{\! m}\\f(x)\equiv 0\pmod{\! n}\end{array} \\ 
&\,\,\iff&  \begin{array}{}x\equiv r_1,\ldots,r_k\pmod{\! m}\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod{\! n}\end{array}\\ 
&\,\,\iff& \left\{ \begin{array}{}x\equiv r_i\pmod{\! m}\\x\equiv s_j\pmod {\! n}\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\
&\overset{\,\,\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{\!mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\
\end{eqnarray}\qquad\qquad$$
