I am new to Abstract Algebra and understand how to solve when the mods are relatively prime, but I am struggling when they aren't relatively prime.
I have a system of of linear congruences that I need to solve:
x = 1 (mod 8)
x = 5 (mod 10)
I know the solution is x = 25 (mod 40), but each time I work through the problem, I do not get the answer. Help please!
An elementary proof: notice that
$$x \equiv 1 \pmod 8 \iff \exists k \in \Bbb Z, \ x-1 = 8k \iff 5x - 5 = 40 k \\ x \equiv 5 \pmod {10} \iff \exists l \in \Bbb Z, \ x-1 = 10l \iff 4x - 20 = 40 l .$$
Subtract the second from the first to get $x + 15 = 40 (k-l)$, which is readily seen to be $x \equiv 25 \pmod {40}$ (because $-15 \equiv 25 \pmod {40}$).
So, if $x$ is a solution to that system, then it is of the form $x \equiv 25 \pmod {40}$.
Conversely, if $x$ is of the form above, then it is easy to check that it verifies the system (for instance,
$$x \equiv 25 \pmod {40} \implies \exists k \in \Bbb Z, \ x - 25 = 40k \implies \\ x - 1 = 40k + 24 = 8(5k + 3) \implies x \equiv 1 \pmod 8$$
and similarly for the second one).
Therefore, all the solutions are $40 \Bbb Z + 25$.