solve the system

Printable View

February 17th 2009, 03:25 AM
Sally_Math

solve the system

x=2 (mod 5), 2x=3 (mod 7), 3x=4 (mod 11)
February 17th 2009, 03:27 AM
Moo

hello,

Quote:

Originally Posted by Sally_Math

x=2 (mod 5), 2x=3 (mod 7), 3x=4 (mod 11)

$2x \equiv 3 \bmod 7 \equiv 10 \bmod 7 \Rightarrow x \equiv 5 \bmod 7$

$3x \equiv 4 \bmod 11 \equiv 15 \bmod 11 \Rightarrow x \equiv 5 \bmod 11$

now use the chinese remainder theorem.
February 17th 2009, 03:44 AM
Sally_Math

Quote:

Originally Posted by Moo

hello,

$2x \equiv 3 \bmod 7 \equiv 10 \bmod 7 \Rightarrow x \equiv 5 \bmod 7$

$3x \equiv 4 \bmod 11 \equiv 15 \bmod 11 \Rightarrow x \equiv 5 \bmod 11$

now use the chinese remainder theorem.

ok i know that u start this way:-
using a=b+km (for eq. 1)
which is x=2+5k
then substituting into eq. 2, u get
2(2+5k)=3 (mod 7)
then we get
4+20k=3 (mod 7)

and then that's where i get stuck
so please help me understand the way we finish it. (Punch)
February 17th 2009, 09:30 PM
ThePerfectHacker

Quote:

Originally Posted by Sally_Math

x=2 (mod 5), 2x=3 (mod 7), 3x=4 (mod 11)

The congruence, $2x\equiv 3(\bmod 7)$ is equivalent to $4(2x)\equiv 4\cdot 3 (\bmod 7)$ which becomes $x\equiv 5(\bmod 7)$ . The congruence, $3x\equiv 4(\bmod 11)$ is equivalent to $4(3x)\equiv 4\cdot 4(\bmod 11)$ which becomes $x\equiv 5(\bmod 11)$ .

Thus, you have to solve,
$x\equiv 2(\bmod 5)$
$x\equiv 5(\bmod 7)$
$x\equiv 5(\bmod 11)$

Combine the last two congruences and so,
$x\equiv 2(\bmod 5)$
$x\equiv 5(\bmod 77)$

This is equivalent to,
$x\equiv 2 + 16\cdot 5(\bmod 5)$
$x\equiv 5 + 77(\bmod 77)$

We get,
$x\equiv 82(\bmod 5)$
$x\equiv 82(\bmod 77)$

Combine,
$x\equiv 82(\bmod 385)$