Remainder problem

**Arka** · April 26th 2011, 06:23 AM

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

Thanks in advance.

**alexmahone** · April 26th 2011, 06:45 AM

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

Thanks in advance.

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

**Arka** · April 27th 2011, 10:19 AM

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 ?

**TheEmptySet** · April 27th 2011, 11:08 AM

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

Thread: Remainder problem

LinkBack

Thread Tools

Display

Remainder problem

Similar Math Help Forum Discussions

Another remainder problem

remainder problem

remainder problem

Remainder problem

remainder problem

Search Tags