1. ## Remainder problem

An integer when divided by 3 gives remainder 2, when divided by 4 gives remainder 1 ,when divided by 7 gives remainder 4. What will be the remainder when the integer divides 84 ?

I have no clue of how to go about in solving this. Need some help

2. Originally Posted by Arka
An integer when divided by 3 gives remainder 2, when divided by 4 gives remainder 1 ,when divided by 7 gives remainder 4. What will be the remainder when the integer divides 84 ?

I have no clue of how to go about in solving this. Need some help

$x\equiv 2\ (mod\ 3)$

$x=3a+2$

------------------------------------------------------------

$x\equiv 1\ (mod\ 4)$

$3a+2\equiv 1\ (mod\ 4)$

$3a\equiv -1\ (mod\ 4)$

$a\equiv 1\ (mod\ 4)$

$a=4b+1$

$x=3a+2=3(4b+1)+2=12b+5$

------------------------------------------------------------

$x\equiv 4\ (mod\ 7)$

$12b+5\equiv 4\ (mod\ 7)$

$12b\equiv -1\ (mod\ 7)$

$b\equiv 4\ (mod\ 7)$

$b=7c+4$

$x=12b+5=12(7c+4)+5=84c+53$

$x\equiv 53\ (mod\ 84)$

3. I have a confusion regarding how you went from step 5 to step 6 and from step 11 to step 12 . Would you please explain ? I mean what logic or theorem did you use ?

4. Originally Posted by Arka
I have a confusion regarding how you went from step 5 to step 6 and from step 11 to step 12 . Would you please explain ? I mean what logic or theorem did you use ?
Alexmahone used the fact that
$[3]^{-1}_{4}=[3]_4,\quad [3]_4[3]_4=[9]_4=[1]_4$

So when you multiply by 3 you get

$3a\equiv -1(\text{mod}4) \iff 9a\equiv -3(\text{mod}4) \iff a\equiv 1(\text{mod}4)$

Negative 3 and 1 are in the same equivalence class mod 4