• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Showing associativity for a particular set

1,000
76
1. Homework Statement
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. Homework 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 ?
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,522
3,505
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 ?
Two ideas:

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

Perhaps you could use the associativity of normal multiplication.
 
1,000
76
Two ideas:

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

Perhaps you could use the associativity of normal multiplication.
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.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,522
3,505
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.
Well, you'll have to think of something else then!
 
1,000
76
Well, you'll have to think of something else then!
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.
 

fresh_42

Mentor
Insights Author
2018 Award
11,133
7,652
Write the numbers as ##q_in+r_i## as suggested in post #2.
 
1,000
76
Write the numbers as ##q_in+r_i## as suggested in post #2.
Thanks, got it. Getting One side as r1r2r3 and other also as some r1r2r3. Which proves associativity.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,522
3,505
1,000
76
What if ##r_2r_3 > n##?
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?
 

fresh_42

Mentor
Insights Author
2018 Award
11,133
7,652
Write down what you already have and then what you want to have.
 
1,000
76
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
 

fresh_42

Mentor
Insights Author
2018 Award
11,133
7,652
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
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?
 
1,000
76
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?
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.
 

fresh_42

Mentor
Insights Author
2018 Award
11,133
7,652
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##.)
 

Want to reply to this thread?

"Showing associativity for a particular set" You must log in or register to reply here.

Related Threads for: Showing associativity for a particular set

Replies
11
Views
938
Replies
21
Views
5K
Replies
4
Views
1K
Replies
2
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top