Solving linear congruent system

Question

Consider the following congruences system:

$$3x \equiv 1 \pmod{8} \\ x \equiv 7 \pmod {12} \\ x \equiv 4 \pmod {15}$$ Find a minimal solution for the system

I was able to show using the Euclidean algorithm that $(-5)\cdot 3\equiv 1 \pmod 8$. so every solution for the first congruence must be of the form $$x = -5 +8k$$

So our system can be written as:

$$x = -5 +8k_1 \\ x = 7 + 12k_2 \\ x = 4 + 15k_3$$

I have found the relations between the $k$'s, but I'm not sure how to extract the general form of a solution for $x$.

I'd be glad for help!

Answer 1

HINT reduce the system to $\pmod {p_i}$ and apply CRT

You can expand in this way:

$\begin{cases} 3x \equiv 1 \pmod{2^3} \\ x \equiv 7 \pmod {2^2\cdot3} \\ x \equiv 4 \pmod{3\cdot5} \end{cases}$

$\begin{cases} x \equiv 3 \pmod{2^3} \\ x \equiv 3 \pmod {2^2} \\x \equiv 1 \pmod {3} \\ x \equiv 4 \pmod{5} \end{cases}$

$\begin{cases} x \equiv 3 \pmod{2^3} \\x \equiv 1 \pmod {3} \\ x \equiv 4 \pmod{5} \end{cases}$

CRT guarantees that solution exist unique $\pmod{120}$

https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Answer 2

from the last two equations we have $$12m-15n=-3$$ or $$5n-4m=1$$ solving this Diophantine equation we get $$m=1+5k$$ $$n=1+4k$$ with $$k \in \mathbb{Z}$$ and $$x=7+12(1+5k)=19+60k$$

Answer 3

You should use the Chinese Remainder Theorem, and you get $x\equiv19\pmod{120}$