<s>[INST] Number Theory: How to solve $x^2\equiv 4\pmod{143}$? I'm not sure how to solve this quadratic congruence:
$x^2 \equiv 4\pmod{143}$
Thanks!
So here's what I did, but the solution seems a bit long the way that I did it:
The four solutions are
1: $x\equiv 2\pmod{11}, x\equiv 2\pmod{13}$:
$x = 2 + 11k\implies 2+11k\equiv 2\pmod{13}\implies 11k\equiv 0\pmod{13}$
$\implies k\equiv 0\pmod{13}\implies k=13k\implies x=2+143k\implies x\equiv2\pmod{143}$.
2: $x\equiv -2\pmod{11}, x\equiv -2\pmod{13}$:
$x = -2 + 11k\implies -2+11k\equiv -2\pmod{13}\implies 11k\equiv 0\pmod{13}$
$\implies k\equiv 0\pmod{13}\implies k=13k\implies x=-2+143k\implies x\equiv-2 \equiv 141\pmod{143}$.
3: $x\equiv -2\pmod{11}, x\equiv 2\pmod{13}$:
$x=-2+11k\implies -2+11k\equiv 2\pmod{13}\implies 11k\equiv 4\equiv 121\pmod{13}$
$\implies k\equiv 11\pmod{13}\implies k=11+13i\implies x=119+143i\implies x\equiv 119\pmod{143}$.
4: $x\equiv 2\pmod{11}, x\equiv -2\pmod{13}$:
$x=2+11k\implies 2+11k\equiv -2\pmod{13}\implies 11k\equiv -4\equiv 22\pmod{13}$
$\implies k\equiv 2\pmod{13}\implies k=2+13i\implies x=24+143i\implies x\equiv 24\pmod{143}$.
So all incongruent solutions of $x^2\equiv 4\pmod{143}$ are:
$x\equiv 2, 24, 119, 141 \pmod{143}$.
 [/INST] The four possible solutions are
$x\equiv 2\ (mod\ 11)$ and $x\equiv 2\ (mod\ 13)$ 
$x\equiv 2\ (mod\ 11)$ and $x\equiv -2\ (mod\ 13)$ 
$x\equiv -2\ (mod\ 11)$ and $x\equiv 2\ (mod\ 13)$ 
$x\equiv -2\ (mod\ 11)$ and $x\equiv -2\ (mod\ 13)$ 
The solutions $2$ and $143-2=141$ are easy to get, a bit more
difficult are the other solutions.
Following the numbers $2,13,24$ of the form $11k+2$, we see that $24$
is a solution.
Following the numbers $9,20,31,42,53,64,75,86,97,108,119$ of the form $11k-2$, we finally
find $119$ to be the last solution. Note, that $24+119=143$, so the
last solution could be found more quickly this way.
</s>