# System of 3 congruences (linear and non-linear)

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.

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}$$