## A community for students. Sign up today

Here's the question you clicked on:

## anonymous one year ago 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).

• This Question is Closed
1. anonymous

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

2. anonymous

similarly $$11=3\cdot3+2\equiv2\pmod 3$$

3. anonymous

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

4. ganeshie8

In general : $$a\equiv b\pmod{n}$$ and $$c\equiv d\pmod{n}$$ implies $$ac\equiv bd \pmod{n}$$

5. anonymous

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

6. jim_thompson5910

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)

7. anonymous

@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)?

8. ikram002p

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

9. anonymous

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

10. anonymous

@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?

11. anonymous

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

12. jim_thompson5910

$\Large \frac{11}{3} = 3 \text{ remainder } {\color{red}{2}}$ $\Large 11 \equiv {\color{red}{2}} \ (\text{mod } 3)$

13. ganeshie8

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

14. anonymous

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

15. ganeshie8

use transitivity : basically if $$a\equiv b\pmod n$$ and $$b\equiv c\pmod n$$ then $$a\equiv c\pmod n$$, it's transitivity

16. jim_thompson5910

|dw:1438392886462:dw|

17. anonymous

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

18. jim_thompson5910

|dw:1438392895131:dw|

19. jim_thompson5910

|dw:1438392929478:dw|

20. ganeshie8

ok, so 325n ≡ 11 (mod 3) and 11 ≡ 2 (mod 3), by transitivity, we have 325n ≡ 2 (mod 3) this looks good, apply transitivity again : 325n ≡ 2 (mod 3) and 325n ≡ n (mod 3), by transitivity, we have n ≡ 2 (mod 3)

21. anonymous

:O ohhhhhhhh.... I see it now. thank you @ganeshie8 @jim_thompson5910

22. ganeshie8

notice that we're also using commutative property $$a\equiv b\pmod{n} \implies b\equiv a\pmod{n}$$

23. anonymous

So so let me recap all this. Given 325n ≡ 11 (mod 3). Since 325n ≡ n (mod 3), by commutative rule, n ≡ 325n (mod 3) by transitivity n ≡ 11 (mod 3) but then 11 ≡ 2 (mod 3), by transitivity n ≡ 2 (mod 3)

24. ganeshie8

Looks good, fun fact : when divided by $$n$$, If $$a$$ leaves a remainder of $$a'$$ and $$b$$ leaves a remainder of $$b'$$, then $$a*b$$ leaves a remainder of $$a'*b'$$.

25. anonymous

thank you. I might find that fact useful :) @ganeshie8 The author certainly left too many details out. Would have nice to at least mention 325n ≡ n (mod 3). From here, I might be able to see why 11 ≡ 2 (mod 3) is used.

26. ganeshie8

in the start, it can be helpful to keep referring back to the definition every time a congruence appears in the textbook : $a\equiv b\pmod{n} \iff n\mid (a-b)$

#### Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy