1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Showing associativity for a particular set

  1. Nov 13, 2016 #1
    1. The problem statement, all variables and given/known data
    Let Zn denote the set of integers {0,1,2,...n-1}. Let * be a binary operation on Zn such that a*b is the remainder of ab divided by n.

    Show that (Zn,*) is a semigroup for any n .

    2. Relevant equations


    3. The attempt at a solution
    For showing the algebraic system to be a semi-group, we have to show that binary operation * is associative.
    So if a,b,c ∈ Zn,
    We have to show, a * (b * c) =(a * b) * c
    Now, a * (b * c) = a * rem(bc/n) (This is closed under Zn )
    = rem ( (a rem(bc/n) )/n)
    Similarly, (a * b) * c = rem(ab/n) * c
    =rem ( (rem(ab/n) c )/n)
    Now , how to show here rem ( (a rem(bc/n) )/n) = rem ( (rem(ab/n) c )/n) ?
    or a rem(bc/n) =rem(ab/n) c ?
     
  2. jcsd
  3. Nov 13, 2016 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Two ideas:

    Perhaps you need some way to express the remainder as a number.

    Perhaps you could use the associativity of normal multiplication.
     
  4. Nov 13, 2016 #3
    For writing remainder as a number I have to use Euclid's division lemma, but it then brings 1 more variable quotient into account here.
    Associativity of multiplication I can use but remainder hinders it.
     
  5. Nov 13, 2016 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, you'll have to think of something else then!
     
  6. Nov 13, 2016 #5
    Modulo operation I can think of but it is essentially just a operator. I have tried doing this question in many ways. Can this associativity be shown mathematically by equations? Since, by equations I am getting stuck, but I want it to solve using equations.
     
  7. Nov 13, 2016 #6

    fresh_42

    Staff: Mentor

    Write the numbers as ##q_in+r_i## as suggested in post #2.
     
  8. Nov 13, 2016 #7
    Thanks, got it. Getting One side as r1r2r3 and other also as some r1r2r3. Which proves associativity.
     
  9. Nov 13, 2016 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What if ##r_2r_3 > n##?
     
  10. Nov 13, 2016 #9
    Hmm.. then it's wrong. Suppose if number are 1,2,3. then 1*2*3 should be 2 but from r1r2r3 answer would be 6 which is essentially 2 for modulo 4. I thought I got an answer from equations. What should I do?
     
  11. Nov 13, 2016 #10

    fresh_42

    Staff: Mentor

    Write down what you already have and then what you want to have.
     
  12. Nov 13, 2016 #11
    a= nq1 + r1
    b= nq2 + r2
    c=nq3 + r3
    a*(b*c) = a * r2r3 = r1r2r3
    (a* b) * c = r1r2 * c = r1r2r3
    This is showing associativity but this is wrong as if we take a =1, b=2, c=3, then, 1*2*3= 2
    but r1r2r3 = 6
    Edit:
    for n = 4 here
     
  13. Nov 13, 2016 #12

    fresh_42

    Staff: Mentor

    You have ##r_1(r_2r_3)+\text{ something with n }=(r_1r_2)r_3+\text{ something with n }##.
    Now what will you have to do, in order to get ##r_1r_2r_3## into your required area between ##0## and ##n-1##?
    And what will happen, if you do this on both sides of the equation?
     
  14. Nov 13, 2016 #13
    No, that is okay we can do mod n on both sides or in programming languages (% n).
    But that we should have get from a*b*c. Why, we have to add something with n on our own?
    %n or mod n should have come on its own while solving the equation.
     
  15. Nov 13, 2016 #14

    fresh_42

    Staff: Mentor

    No, you should not add something on your own. It is what you get without modulos. It's the reason why you can have different numbers and what happened in your example.

    But you can always add or subtract n's by shifting them between the "something with n reservoir" and the ##r_1r_2r_3## term.
    That's the way to get this term into the required range ##0,\ldots,n-1##. The only question is: After doing it, can there be two different remainders left? (Remember that ##6## in your example is too big by one ##n=4##, so we have to write ##6 + 0\cdot n= 2+1\cdot n##.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted