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.
Hello everyone
Thanks to aidan for this helpful posting:This does indeed give the solutions without any particular pain!
and
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
and
... and so on.
Grandad