A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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).

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  4. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  5. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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)?

  8. ikram002p
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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?

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  13. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  15. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1438392886462:dw|

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  18. jim_thompson5910
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1438392895131:dw|

  19. jim_thompson5910
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1438392929478:dw|

  20. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  22. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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)\]

  27. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.