# chinese remainder theorem

• May 29th 2008, 01:29 PM
skystar
chinese remainder theorem
how would i solve

$x\equiv 2mod3 , x\equiv 5mod8 , x\equiv 11mod13$ im getting confused around the mod 13 and finding its inverse would appreciate answer..exam revision!thanks
• May 29th 2008, 01:35 PM
Moo
Hello,

Quote:

Originally Posted by skystar
how would i solve

$x\equiv 2mod3 , x\equiv 5mod8 , x\equiv 11mod13$ im getting confused around the mod 13 and finding its inverse would appreciate answer..exam revision!thanks

The inverse of 11 mod 13 ?

Euclidian algorithm :
$13=11+2 \implies 2=13-11$

$11=2*5+1 \implies 1=11-2*5=11-(13-11)*5=11*6-13*5$

Therefore, $11*6=13*5+1$

--> $11*6=1 \mod 13$

The inverse of 11 is... ? :)
• May 29th 2008, 02:08 PM
galactus
$x\equiv{2(mod3)}$......[1]
$x\equiv{5(mod8)}$......[2]
$x\equiv{11(mod13)}$........[3]

From [1], we have $x=3t+2$

Sub into [2]:

$3t+2\equiv{5(mod8)}$

$3t\equiv{3(mod8)}$

$t\equiv{1(mod8)}$

$t=8s+1$

Sub into x=3t+2, 3(8s+1)+2=24s+5

$24s+4\equiv{11(mod13)}$

$24s-6\equiv{(mod13)}$

$\frac{24s-6}{13}$

This must be an integer. That occurs first at s=10

By resubbing, we get 8(10)+1=82, 3(81)+2=245

x=245

We can check this and see it checks on our congruencies

(245-2)/3=81
(245-5)/8=30
(245-11)/13=18

Make sure I didn't go astray somewhere. Make sure this is the smallest.
• May 29th 2008, 02:34 PM
skystar
where did 3t+2 come from,,typo on [1]?
• May 29th 2008, 02:38 PM
galactus
I had 13 instead of 3 in the first one. Should be mod 3. I had mod 13
• May 29th 2008, 03:20 PM
galactus
Hey, check what I just found. I ran our problem through it and it checks

That reminds me, the solutions should be written as 245 mod 312. I just posted the smallest.

Section 7.3: Solving Lots of Congruences