Hi, how can I find all four solutions to x^2 ≡ 133 (mod 143)?
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
The chinese remainder theorem will assist in finding the answers.
Thanks to aidan for this helpful posting:
Using the Euclidean Algorithm, we find that
and using the Chinese Remainder Theorem for the 4 pairs of values of that we've found above we get:
... and so on.