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?

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.
