Find all $x \in \Bbb Z_{143} $ so $x^{2}\equiv1 \pmod{143}$

Question

$143=11\cdot13$

$\varphi(143)=120$ and $gcd(120,2)=2$

How do I continue?

Answer 1

Here we go :

First notice that $143=11\times 13$.

The method is that we will solve the equation $x^2 \equiv 1 \pmod{11}$ and $x^2\equiv 1 \pmod{13}$ and after we'll apply the CRT.

This equivalent to solve :

$(x-1)(x+1)\equiv 0 \pmod{11}$ and $(x-1)(x+1)\equiv 0 \pmod{13}$. We know that $\mathbb{Z}/11\mathbb{Z}$ and $\mathbb{Z}/13\mathbb{Z}$ are fields. But easier, $11$ and $13$ are prime numbers so you can apply Euclid's lemma. For each equation you have $11\mid (x-1)$ or $(x+1)$ and $13 \mid (x-1)$ or $(x+1)$.

It gives you four possibilities (or four systems) :

$\left\{\begin{array}{rl} x_1 &\equiv 1 \pmod{11} \\ x_1 &\equiv 1 \pmod{13} \\ \end{array} \right.$ $\Rightarrow \ x_1\equiv 13y_1+11z_1 \pmod{143}$.

$\left\{\begin{array}{rl} x_2 &\equiv -1 \pmod{11} \\ x_2 &\equiv 1 \pmod{13} \\ \end{array} \right.$ $\Rightarrow \ x_2\equiv -13y_2+11z_2 \pmod{143}$.

$\left\{\begin{array}{rl} x_3 &\equiv 1 \pmod{11} \\ x_3 &\equiv -1 \pmod{13} \\ \end{array} \right.$ $\Rightarrow \ x_3\equiv 13y_3-11z_3 \pmod{143}$.

$\left\{\begin{array}{rl} x_4 &\equiv -1 \pmod{11} \\ x_4 &\equiv -1 \pmod{13} \\ \end{array} \right.$ $\Rightarrow \ x_4\equiv -13y_4-11z_4 \pmod{143}$.

Now by the conditions of the CRT we must have :

$13y_1\equiv 1 \pmod{11}\Rightarrow y_1\equiv 6 \pmod{11}$ and $11z_1 \equiv 1 \pmod{13} \Rightarrow z_1 \equiv 6 \pmod{13}\Rightarrow x_1\equiv 1\pmod{143}$.

$13y_2\equiv 1 \pmod{11}\Rightarrow y_2\equiv 6 \pmod{11}$ and $11z_2 \equiv 1 \pmod{13} \Rightarrow z_2 \equiv 6 \pmod{13}\Rightarrow x_2\equiv -12=131\pmod{143}$.

$13y_3\equiv 1 \pmod{11}\Rightarrow y_3\equiv 6 \pmod{11}$ and $11z_3 \equiv 1 \pmod{13} \Rightarrow z_3 \equiv 6 \pmod{13}\Rightarrow x_3\equiv 12\pmod{143}$.

$13y_4\equiv 1 \pmod{11}\Rightarrow y_4\equiv 6 \pmod{11}$ and $11z_4 \equiv 1 \pmod{13} \Rightarrow z_4 \equiv 6 \pmod{13}\Rightarrow x_4\equiv -1=142\pmod{143}$.

Answer 2

$x^2 \equiv 1 \mod 143$

$x^2 -1 \equiv 0 \mod 11*13$

$11*13|(x+1)(x-1)$

So there are four cases: where either $11|x \pm 1$; $13|x \pm 1$.

Case 1: $11*13|x-1< 142$. $x=1$

Case 2: $11*13|x+1.$ $x= 142$

Case 3: $11|x-1; 13|x+1$

$x = 11m + 1; x = 13j -1$ so $13j-11m = 2$ and $13(j + 11i) - 11(m + 13i) = 2$. So $(j,m) = (1,1);x = 12$ or $(1+11i,1+13i); x=12+ 143i$.

Case 4: $13|x-1$. $11|x+1$

$x=13m +1 = 11j - 1; 13(m+11i)- 11(j+13i) =-2;$ so $(j,m) =(-1,-1);x=-12 + 143i$ or $x = 131$.

So $x = 1,12,131,142$

Which is basically the chinese remainder theorem without knowing the chinese remainder theorem.