Friday, 3 January 2014

elementary number theory - Solving the congruence x2equiv4mod105. Is there an alternative to using Chinese Remainder Theorem multiple times?

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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...