# 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}$.

• Are you familiar with the Chinese Remainder Theorem? Oct 13, 2015 at 21:59
• Yes I am familiar with it. Oct 13, 2015 at 22:04
• Or just use trial and error. $143$ is the product of two primes, so there are $4$ solutions. Two are obvious, one of the others is quite small.
– lulu
Oct 13, 2015 at 22:05

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.