Solve the simultaneous congruences

2x = 1 (mod7)

x= 3(mod5)

x= 3(mod8)

those aren't supposed to be equal signs- they are three slashes(congruences).

Printable View

- Nov 7th 2007, 04:33 AManncarcongruences
Solve the simultaneous congruences

2x = 1 (mod7)

x= 3(mod5)

x= 3(mod8)

those aren't supposed to be equal signs- they are three slashes(congruences). - Nov 7th 2007, 05:32 AMangel.white
$\displaystyle 2x \equiv 1 (mod7)\\

x\equiv 3(mod5)\\

x\equiv 3(mod8)$

I would do the first one, but I'm out of time, gotta get ready for work, and wouldn't want to steer you wrong.

For the second one, you can see that 3=5*0+3, so when x = 3, it is congruent to 3(mod5). So find the next in the progression by just adding 5, so x=3+5n for any integer n (this creates the series ...,3,8,13...)

For the third one, you can see that 3=8*0+3, so when x=3 it is congruent to 3(mod8). So find the next progression by just adding 8, so x=3+8n for any integer n (this creates the series ...3,11,19...) - Nov 7th 2007, 05:34 AMtopsquark
See here.

First let's solve the first congruence for x:

$\displaystyle 2x \equiv 1~\text{mod 7}$

$\displaystyle 4 \cdot 2x \equiv 2 \cdot 1~\text{mod 7}$

$\displaystyle 8x \equiv 2~\text{mod 7}$

$\displaystyle x = 2~\text{mod 7}$

So we need to solve

$\displaystyle x = 2~\text{mod 7}$

$\displaystyle x = 3~\text{mod 5}$

$\displaystyle x = 3~\text{mod 8}$

The modulos are pairwise coprime, so we may state a solution exists by the Chinese Remainder Theorem.

Use the extended Euclidean algorithm to find integer r1 and s1 such that

$\displaystyle 5r_1 + (7 \cdot 8)s_1 = 1$

One such pair is $\displaystyle r_1 = -11$ and $\displaystyle s = 1$.

Now do the same for

$\displaystyle 7r_2 + (5 \cdot 8)s_2 = 1$ <-- r2 = -17 and s2 = 3

and

$\displaystyle 8r_3 + (5 \cdot 7)s_3 = 1$ <-- r3 = -13 and s3 = 3

Now, define $\displaystyle e_1 = (7 \cdot 8)s_1 = 56$, $\displaystyle e_2 = (5 \cdot 8)s_2 = 120$, and $\displaystyle e_3 = (5 \cdot 7)s_3 = 105$.

Then a solution to the system will be:

$\displaystyle x = 3 \cdot 56 + 2 \cdot 120 + 3 \cdot 105 = 723$

which you may verify is a correct solution.

Edit: Whoops! I just noticed. This answer will be correct a modulo 5 x 7 x 8 = 280. So we have a smaller answer which is equivalent to $\displaystyle 723 \equiv 163~\text{mod 280}$. So we can use x = 163 as the solution.

-Dan

(See, you can teach an old dog new tricks!) - Nov 7th 2007, 09:14 AMangel.white
Oh, my apologies, I looked at it as three independent equations, just ignore my earlier post.