Solving system of congruences using CRT

Question

$$4x \equiv 5 \pmod 7$$ $$7x \equiv 4 \pmod {15}$$

I need to solve this system of congruences using Chinese Reminder Theorem. It would be easy to use CRT if not those 4 and 7 near the x variables. How can I do this? Just divide both congruences by 4/7 and use CRT in something like:

$$x \equiv \frac54 \pmod 7$$ $$x \equiv \frac47 \pmod {15}$$

? It gives me $\frac{283}4 + 105k$ as the result.

Answer 1

HINT:

Method $1:$ $$4x\equiv5\pmod 7\equiv5+7=12\implies x\equiv3\pmod 7\text{ as } (4,7)=1$$

Again, $$7x\equiv4\pmod {15}=4+15\cdot3=47\implies x\equiv7\pmod {15}\text{ as } (7,15)=1$$

Method $2:$

As $4\cdot2-7=1,4\cdot2\equiv1\pmod 7\iff \frac14\equiv2\pmod 7$

$$\text{So, }x\equiv\frac54\pmod 7\equiv 5\cdot2\equiv3\pmod 7$$

Similarly as $15-2\cdot7=1,-2\cdot7\equiv1\pmod {15}\iff\frac17\equiv-2\pmod{15}\equiv13$

$$\text{So, }x\equiv\frac47\pmod{15}\equiv4\cdot13\equiv7\pmod{15} $$

Now, we can safely apply CRT as $(7,15)=1$

Answer 2

Rule number 1 : never just divide in congruences! Congruences don't have the same rules as integer for the simple reason that you don't work in the same ring (${\mathbb Z}/{m\mathbb Z}$ instead of $\mathbb Z$).

$$4x \equiv 5 \mod 7 \Longleftrightarrow 4x = 5 + 7k_1\text{ for some }k_1\in\mathbb Z$$ $$7x \equiv 4 \mod 15 \Longleftrightarrow 7x = 4 + 15k_2\text{ for some }k_2\in\mathbb Z$$

From here with certain $k_1$ and $k_2$, you can perform division as you are back in $\mathbb Z$.

For solving, I think lab gave you enough of a hint.