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?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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. "Combining" below. The first 2 have solutions $\,\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}$

Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and 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].

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$$