# Thread: Finding square roots mod n

1. ## Finding square roots mod n

Hi, how can I find all four solutions to x^2 133 (mod 143)?

2. Hello posix_memalign
Originally Posted by posix_memalign
Hi, how can I find all four solutions to x2 133 (mod 143)?
I cheated, I suppose, and used a spreadsheet to do the arithmetic, by looking at the values of $\displaystyle 143n+133$, to see where the perfect squares came. This gave answers of $\displaystyle x = 43, 56, 87, 100.$ But, perhaps you want a more mathematical method ...

Hello posix_memalignI cheated, I suppose, and used a spreadsheet to do the arithmetic, by looking at the values of $\displaystyle 143n+133$, to see where the perfect squares came. This gave answers of $\displaystyle x = 43, 56, 87, 100.$ But, perhaps you want a more mathematical method ...

Thanks.
I wrote a program prior to asking which determined the correct answers as well -- they are the same as yours -- although yes, I was looking for the 'right' way of doing this, i.e. mathematical approach.

4. Originally Posted by posix_memalign
Hi, how can I find all four solutions to x^2 133 (mod 143)?
I was looking for the 'right' way of doing this, i.e. mathematical approach.
There is no 'right' way, but there are several approaches that ease the pain.
Notice that 143 is composite and its factors are 11 & 13.

133 mod 11 is 1
133 mod 13 is 3

You are looking for a number that is both
$\displaystyle x^2 \equiv 1 mod 11$
&
$\displaystyle x^2 \equiv 3 mod 13$

The chinese remainder theorem will assist in finding the answers.

5. ## Chinese Remainder Theorem

Hello everyone

Thanks to aidan for this helpful posting:
Originally Posted by aidan
There is no 'right' way, but there are several approaches that ease the pain.
Notice that 143 is composite and its factors are 11 & 13.

133 mod 11 is 1
133 mod 13 is 3

You are looking for a number that is both
$\displaystyle x^2 \equiv 1 mod 11$
&
$\displaystyle x^2 \equiv 3 mod 13$

The chinese remainder theorem will assist in finding the answers.
This does indeed give the solutions without any particular pain!

$\displaystyle x^2\equiv 1 \mod 11$

$\displaystyle \Rightarrow x \equiv1, 10 \mod 11$

and

$\displaystyle x^2\equiv 3 \mod 13$

$\displaystyle \Rightarrow x \equiv 4,9\mod 13$

Using the Euclidean Algorithm, we find that $\displaystyle 6\times11+(-5)\times13 = 1$

and using the Chinese Remainder Theorem for the 4 pairs of values of $\displaystyle x$ that we've found above we get:

$\displaystyle x\equiv1\mod11$ and
$\displaystyle x\equiv4\mod13$

$\displaystyle \Rightarrow x=66\times4+(-65)\times1$

$\displaystyle =199$

$\displaystyle \equiv56\mod143$

$\displaystyle x\equiv1\mod11$ and $\displaystyle x\equiv9\mod13$

$\displaystyle \Rightarrow x=66\times9+(-65)\times1$

$\displaystyle =529$

$\displaystyle \equiv100\mod143$

... and so on.