# Find all solutions to $x^2\equiv 1\pmod {91}$

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: CRT. See link – user160069 Dec 3 '16 at 2:38

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.

• Thank you! I figured out the other solutions to be $\pm 27$. – J. Doe Dec 3 '16 at 3:40

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.

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)\,$$ mod $$(7,13),$$ cf. Remark below. The first $$2$$ have obvious solutions $$\,\color{#c00}{\bf 1}\,$$ and $$\,\color{#0a0}{-1}\,$$ so you need only solve the $$(1,-1)$$ case, then note $$(-1,1)\equiv -(1,-1)$$ is its negative, i.e. $$\,x\equiv 1\pmod{\!7},\,x\equiv -1\pmod{\!13}\,\Rightarrow\,-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.

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