0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ If you want to divide in modular arithmetics, then you need to do that by a common factor, also you must be careful not to divide with an integer that is congruent with 0 modulo n. You must add n to one of the sides and then try to find common factor. $\endgroup$
    – Stefan4024
    Aug 15, 2013 at 15:12

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

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