Question

The book doesn't provide a clear explanation.

Find an integer n that satisfies 325n ≡ 11 (mod 3). It just says Since 325 ≡ 1 (mod 3) and 11 ≡ 2 (mod 3), we must find an integer n such that n ≡ 2 (mod 3).

Answer 1

\(325n=(3\cdot 108+1)n=3\cdot108n+n\equiv 0+n=n\pmod 3\)

Answer 2

similarly \(11=3\cdot3+2\equiv2\pmod 3\)

Answer 3

hence if \(325n\equiv 11\pmod 3\) then \(n\equiv 11\pmod 3\) and ultimately \(n\equiv 2\pmod 3\)

Answer 4

In general :

\(a\equiv b\pmod{n}\) and \(c\equiv d\pmod{n}\) implies \(ac\equiv bd \pmod{n}\)

Answer 5

basically if \(a\equiv b\pmod n\) and \(b\equiv c\pmod n\) then \(a\equiv c\pmod n\), it's transitivity

Answer 6

Because we're dealing with mod 3, we can use this trick:

Add up the digits of 325 to get 3+2+5 = 5+5 = 10

so 325 = 10 (mod 3)

10/3 = 3 remainder 1 which is why 325 = 10 = 1 (mod 3)

The same happens with 11
1+1 = 2 which is why 11 = 2 (mod 3)

Answer 7

@oldrin.bataku ok, let me think through your answer

so 325n = (3 * 108 + 1)n = 3(108)n + n. Ok this I get

How did you get 3(108)n + n ≡ 0 + n (mod 3). Did you use the fact that n ≡ n (mod 3)?

Answer 8

first think to reduce 11 .-.
in order of 3 set of residues are {0,1,2}

Answer 9

@sourwing well, clearly \(3\cdot k\equiv 0\pmod 3\) so the \(3\cdot108n\) term is congruent to \(0\)

Answer 10

@oldrin.bataku oh, so
3(108n) ≡ 0 (mod 3) and n ≡ n (mod 3).

adding the two congruences gives
108n + n ≡ 0 + n (mod 3)

325n ≡ n (mod 3).

And how does 11 ≡ 2 (mod 3) come in place?

Answer 11

I guess it has something to do with what @ganeshie8 said earlier.

325 ≡ 1 (mod 3) and n ≡ n (mod 3), then
325n ≡ n (mod 3).

But what about 11 ≡ 2 (mod 3)?

Answer 12

\[\Large \frac{11}{3} = 3 \text{ remainder } {\color{red}{2}}\]

\[\Large 11 \equiv {\color{red}{2}} \ (\text{mod } 3) \]

Answer 13

11 and 2 leave same remainder when divided by 3, so they are congruent.

keep subtracting 3 until you get a nonnegative integer less than 3

Answer 14

well, yes but how do we go from 325n ≡ n (mod 3) to n ≡ 2 (mod 3) using 11 ≡ 2 (mod 3)

Answer 15

use transitivity :

basically if \(a\equiv b\pmod n\) and \(b\equiv c\pmod n\) then \(a\equiv c\pmod n\), it's transitivity

Answer 16

ok, so 325n ≡ 11 (mod 3) and 11 ≡ 2 (mod 3), by transitivity, we have
325n ≡ 2 (mod 3)