Friday, 3 January 2014

elementary number theory - Solving the congruence $x^2 equiv 4 mod 105$. 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}...