How many solutions of $\mod 63$ : $x^2=1 \pmod7 $ and $x^3=1\pmod 9$ [closed]

How many solutions $\mod 63$ , we have for:

$$x^2=1 \pmod 7$$ and $$x^3=1 \pmod 9$$

Need to find them also.

Solution 1:

Once you find $\,x^2\equiv 1\iff x\equiv \pm1 \pmod 7\,$ and $\,x^3\equiv 1\iff x\equiv 1,4,7\pmod{9},\,$ you can lift each possible combination of values using the Chinese Remainder Theorem (CRT). It's usually quicker to do it generically first, i.e. solve $\,x\equiv a\pmod 7,\,$ $\,x\equiv b\pmod 9,\,$ then substitute all possible combinations of the above values for $\,a,b,\,$ i.e. for all $\,a\in \{1,-1\}\,$ and all $\,b \in \{1,4,7\}.\ $ So let's do the generic CRT.

${\rm mod}\ 7\!:\,\ x \equiv a\iff x = a+7j\,$ for some $\,j\in \Bbb Z.\,$

${\rm mod}\ 9\!:\,\ b \equiv x \equiv a+7j\equiv a-2j\iff 2j\equiv a-b\iff j\equiv 4(b-a)$

Thus $\,x = a + 7j = a+7(4(b-a)+9k) \equiv a+28(b-a)\pmod{\!63}$

For $\,a\ \equiv\ 1\pmod{\! 7}\!:\ x\ \equiv\ 1+28(b\!-\!1) \equiv\ \, 1,22,43\pmod{\!63}\, $ for $\, b \equiv 1,4,7 \pmod{\!9}$

For $ a \equiv -1\!\pmod{\! 7}\!:\ x \equiv -1\!+\!28(b\!+\!1) \equiv 55,13,34\pmod{\!63}\, $ for $\, b \equiv 1,4,7 \pmod{\!9}$

Remark $ $ If $\,m,n\,$ are coprime then, by CRT, each combination of a root $\,r_i\,$ mod $\,m\,$ and a root $\,s_j\,$ mod $\,n\,$ corresponds to a unique root $\,t_{ij}\,$ mod $\,mn\,$ i.e.

$$\begin{eqnarray} \begin{array}{}f(x)\equiv 0\pmod m\\g(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{\large \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$$