I'm trying to solve x^2 \equiv 4 \mod 105.
This is of course equivalent to (x+2)(x-2) \equiv 0 \mod 105
which is also equivalent to the system of congruences
(x+2)(x-2) \equiv 0 \mod 3
(x+2)(x-2) \equiv 0 \mod 5
(x+2)(x-2) \equiv 0 \mod 7
which have solutions of x \equiv 1\ \text{or}\ 2
x \equiv 2\ \text{or}\ 3,\ \text{and}
x \equiv 2\ \text{or}\ 5
respectively.
Now, I could in principle take each combination of {1,2}, {2,3}, and {2,5} and use the Chinese Remainder Theorem to solve each system, but that seems incredibly tedious.
Is there a simpler way?
I'll note that this is a homework question, so it seems likely that there's a trick. Unfortunately I can't spot one.
No comments:
Post a Comment