The background is this. I encountered a problem in algorithm: given several integers of finite amount, exactly one of which occurs once, and all other numbers occurs twice. How to find this number using algorithm with complexity $O(n)$.
There is an elegant way to do this. Let's say all the numbers are $x_1,x_2,...,x_n$, we can do the "xor" operation of all these numbers in binary number system, and the result is the answer. Let's denote $\wedge$ as "xor". The reason behind is, for any integer, $x\wedge x = 0$, and $x \wedge 0 = x$. Further more, if we have three integers $a,b,c$, if we have $a\wedge b=c$, then we can get $a\wedge c=b$, $b\wedge c=a$ and so on. And $\wedge$ is both commutative and associative. Thus $(\mathbb{Z}, \wedge)$ is an abelian group. The identity element is $0$, and $x^{-1}=x$.
I want to generalize this method to solve similar problem. Let's say we have several integers, exactly one of which occurs once and all other numbers occurs three times. The similar idea here is to look for a group with integers as its elements, and with all elements except identity have order $3$. Or basically what we need to do is to look for an operation, let's denoted it by "$\cdot$", such that there exists an "identity" $1$, for any integer $n$, we have $n\cdot n\cdot n=1$ and $n\cdot 1=n$. And this operation is both commutative and associative. I am even not sure such group exists or not. Could anyone give me some hint? Thank you so much!
One way to think of xor is as bitwise mod 2 addition. Thus it would be natural to take tritwise mod 3 addition for your new operation.
To be more explicit. Define our new operation $n*m$ by writing both numbers in base 3, $$n=\sum_{i=0}^\infty a_i3^i,\text{ $a_i\in\{0,1,2\}$},$$ $$m=\sum_{i=0}^\infty b_i3^i,\text{ $b_i\in\{0,1,2\}$},$$ then define $c_i\equiv a_i+b_i\pmod{3}$, where $c_i\in\{0,1,2\}$ as well.
Then define $$n*m = \sum_{i=0}^\infty c_i 3^i.$$
You'll find that $n*0=n$, and $n*n*n=0$, as desired.