2
$\begingroup$

The problem asks to find all simultaneous solutions to the system of equations.

$x^2 \equiv 1 \pmod 8$
$5x \equiv 15 \pmod {20}$
$5x \equiv 1 \pmod 6$

I really can't find any good examples of how to get beyond the first or second step, but this is what I was able to do so far.

($5x \equiv 15 \pmod {20}$) can be reduced to ($x \equiv 3 \pmod 4$)

and ($5x \equiv 1 \pmod 6$) can be reduced to ($x \equiv 5 \pmod 6$)

($x^2 \equiv 1 \pmod 8$) has solutions 1,3,5, and 7.

And I don't really know how to go from there, if I can apply the Chinese Remainder Theorem or not. Any tips would be appreciated.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Your reasoning is OK. Apply the Chinese Remainder Theorem for the last two modular equations. So we have:

$$x \equiv 3 \pmod 4 \implies x = 4k + 3$$ $$x \equiv 5 \pmod 6 \implies x = 6n + 5$$

$$4k + 3 = 6n + 5$$ $$4k = 6n + 2$$ $$2k = 3n + 1$$ $$2k \equiv 1 \equiv 4 \pmod 3$$ $$k \equiv 2 \pmod 3 \implies k=3s + 2$$

$$x = 4k + 3 = 4(3s + 2) + 3 = 12s + 11$$

So we have that $x$ satisfy this modular relations: $$x \equiv 11 \pmod {12}$$

From the first equation we have:

$$x^2 \equiv 1 \pmod 8 \implies x^2 = 8t + 1$$

Now we have:

$$(12s + 11)^2 = 8t + 1$$ $$144s^2 + 264s + 121 = 8t + 1$$ $$144s^2 + 264s + 120 \equiv 0 \pmod 8$$ $$18s^2 + 33s + 15 \equiv 0 \pmod 1$$

We know that every number for $s$ will do that means that the square of every number of the form $x=12 + 11$ will be equivalent to 1 modulo 8.

So the final form for x will be $$x=12s + 11; \forall x \in \mathbb{R}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .