Question

Compute (4 + 2^200) mod 3.

Answer 1

2^(200) = 2^(2*100) (mod 3)
2^(200) = (2^2)^100 (mod 3)
2^(200) = 4^100 (mod 3)
2^(200) = 1^100 (mod 3) ... since 4 = 1 (mod 3)
2^(200) = 1 (mod 3)

Answer 2

why do you want to get 2^(2*100) (mod 3)?

Answer 3

because I wanted to get to (2^2)^100

Answer 4

I used the identity (a^x)^y = a^(x*y)

Answer 5

My professor has an example so I set it up like that and I got stuck on (1 mod 3 + 2^200) mod 3.

Answer 6

why would you want to get (2^2)^100?

Answer 7

because I know that 4 = 1 (mod 3)

Answer 8

so 4^100 = 1^100 (mod 3)

1 to any power = 1, so

4^100 = 1^100 = 1 (mod 3)

Answer 9

how is 4 = 1 (mod 3)?

Answer 10

because they both leave the same remainder when divided by 3

4/3 = 1 remainder 1
1/3 = 0 remainder 1

Answer 11

another example

10 = 4 (mod 3)

since
10/3 = 3 remainder 1
4/3 = 1 remainder 1


or you can use this rule

a = b (mod m) if and only if m | (a-b)
in english: if m is a factor of (a-b) then a = b (mod m)

Answer 12

using this rule `a = b (mod m) if and only if m | (a-b)`

we know 4 = 1 (mod 3) because 3 is a factor of (4-1)

same with 10 = 4 (mod 3) since 3 is a factor of (10-4)

Answer 13

how did 2^(2*100) (mod 3 go to (2^2)^100 (mod 3)? I don't really get what you are trying to obtain at the end.

Answer 14

Like I said, I used this identity `(a^x)^y = a^(x*y)`

Answer 15

its not much different, but u may also work it like this :

(4 + 2^200) mod 3

= `4 mod3` + `2^200 mod3`

= `1` + `(-1)^200 mod3`

= `1` + `1`

= 2

Answer 16

@ganeshie8 's method is much more effective

Answer 17

do did you get (-1)^200 mod3?

Answer 18

how did*

Answer 19

2 = -1 (mod 3) since they both lie in the same equivalence class

Answer 20

set of numbers that when you divide them by 3, you get remainder 0
{..., -9, -6, -3, 0, 3, 6, 9, ...}


set of numbers that when you divide them by 3, you get remainder 1
{..., -8, -5, -2, 1, 4, 7, 10, ...}


set of numbers that when you divide them by 3, you get remainder 2
{..., -7, -4, -1, 2, 5, 8, 11, ...}

these sets are known as equivalence classes

so for example, 4 and 7 are from the same equivalence class mod 3, which is why 4 = 7 (mod 3)