Hi, how can I find all four solutions to x^2 ≡ 133 (mod 143)?
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 ...
Grandad
There is no 'right' way, but there are several approaches that ease the pain.I was looking for the 'right' way of doing this, i.e. mathematical approach.
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.
Hello everyone
Thanks to aidan for this helpful posting: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.
Grandad