1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Are you familiar with the Chinese Remainder Theorem? $\endgroup$ Oct 13, 2015 at 21:59
  • $\begingroup$ Yes I am familiar with it. $\endgroup$ Oct 13, 2015 at 22:04
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Oct 13, 2015 at 22:05

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.