A community for students.
Here's the question you clicked on:
 0 viewing
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).
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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0\(325n=(3\cdot 108+1)n=3\cdot108n+n\equiv 0+n=n\pmod 3\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0similarly \(11=3\cdot3+2\equiv2\pmod 3\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0hence if \(325n\equiv 11\pmod 3\) then \(n\equiv 11\pmod 3\) and ultimately \(n\equiv 2\pmod 3\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0In general : \(a\equiv b\pmod{n}\) and \(c\equiv d\pmod{n}\) implies \(ac\equiv bd \pmod{n}\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0basically if \(a\equiv b\pmod n\) and \(b\equiv c\pmod n\) then \(a\equiv c\pmod n\), it's transitivity

jim_thompson5910
 one year ago
Best ResponseYou've already chosen the best response.1Because 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)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@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)?

ikram002p
 one year ago
Best ResponseYou've already chosen the best response.0first think to reduce 11 .. in order of 3 set of residues are {0,1,2}

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@sourwing well, clearly \(3\cdot k\equiv 0\pmod 3\) so the \(3\cdot108n\) term is congruent to \(0\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@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?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I 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)?

jim_thompson5910
 one year ago
Best ResponseYou've already chosen the best response.1\[\Large \frac{11}{3} = 3 \text{ remainder } {\color{red}{2}}\] \[\Large 11 \equiv {\color{red}{2}} \ (\text{mod } 3) \]

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.011 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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0well, yes but how do we go from 325n ≡ n (mod 3) to n ≡ 2 (mod 3) using 11 ≡ 2 (mod 3)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0use transitivity : basically if \(a\equiv b\pmod n\) and \(b\equiv c\pmod n\) then \(a\equiv c\pmod n\), it's transitivity

jim_thompson5910
 one year ago
Best ResponseYou've already chosen the best response.1dw:1438392886462:dw

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ok, so 325n ≡ 11 (mod 3) and 11 ≡ 2 (mod 3), by transitivity, we have 325n ≡ 2 (mod 3)

jim_thompson5910
 one year ago
Best ResponseYou've already chosen the best response.1dw:1438392895131:dw

jim_thompson5910
 one year ago
Best ResponseYou've already chosen the best response.1dw:1438392929478:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0ok, 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)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0:O ohhhhhhhh.... I see it now. thank you @ganeshie8 @jim_thompson5910

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0notice that we're also using commutative property \(a\equiv b\pmod{n} \implies b\equiv a\pmod{n}\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0So 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)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0Looks 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'\).

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0thank 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.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.0in 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 (ab)\]
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.