Question

Suppose \([a],[b] \in \mathbb{Z}_{n},\) and \([a]=\left[a^{\prime}\right]\) and \([b]=\left[b^{\prime}\right] .\) Alice adds \([a]\) and \([b]\) as \([a]+[b]=\) \([a+b] .\) Bob adds them as \(\left[a^{\prime}\right]+\left[b^{\prime}\right]=\left[a^{\prime}+b^{\prime}\right]\). Show that their answers \([a+b]\) and \(\left[a^{\prime}+b^{\prime}\right]\) are the same.

Short answer

The results obtained by Alice and Bob are indeed the same, \( [a+b] = [a'+b'] \), as the sum of two equivalence classes in \( Z_n \), based on representative elements is shown to be the same. This demonstrates the properties of addition in modulo arithmetic involving equivalence classes.

Step-by-step solution

Identify the equivalence classes

Define the equivalence classes \( [a] \) and \( [b] \) that are subsets of \( Z_n \). Here, \( [a] \) denotes the set of all integers equivalent to \( a \) modulo \( n \), similarly for \( [b] \). The elements \( a' \) and \( b' \) are respective representatives for \( [a] \) and \( [b] \).

Define Operations

Alice adds \( [a] \) and \( [b] \) as \( [a]+[b] = [a+b] \). Bob adds them as \( [a']+[b']=[a'+b'] \). Define these operations on equivalence classes.

Equality Modulo n

Since \( a' \) is a representative of \( [a] \) and \( b' \) of \( [b] \), we have \( a' \equiv a (mod\ n) \) and \( b' \equiv b (mod\ n) \). Adding the two equations gives \( (a'+b') \equiv (a+b) (mod\ n) \). Thus, \( a'+b' \) and \( a+b \) are equivalent in modulo n, meaning \([a'+b'] = [a+b] \).

Conclusion

This proves that regardless of the representative element chosen, the addition operation on equivalence classes under modulo n will yield the same equivalence class. Therefore, Alice's and Bob's results are the same.