Given multiplication on natural number s.t. a * b = r where r is the remainder when the product of ab is divided by divisor n.
I need to show that the operation is associative. Based on the definition of the associative, I get (a * b) * c = [c(ab % n)] % n and a (b * c) = [a(bc % n)] % n. How can I proceed? Is c(ab % n) = a(bc % n)?
The thing to notice is if $p$ and $q$ have the same remainder when divided by $n$ then for any $d$, $dp$ and $dq$ will have the same remainders.
Pf: Let $p= kn + r_1$ and $q=jn + r_1$ where $r_1$ is the remainder of $p$ and $q$. Let $a = mn+r_2$ where $r_2$ is the remainder of $a$. ANd let's do a premptive strike and assume that $r_1r_2 = vn + s$ where $s$ is the remainder of $r_1r_2$.
Now we just do it.
$ap = (mn+r_2)(kn+r_1) = mkn^2 + r_2kn + r_1mn + r_1r_2 = n(mkn +r_2k + r_1m) + vn + s = n(mkn+r_2k + r_1m + v) + s$
and $s$ is the remainder of $ap$.
And $aq=(mn+r_2)(jn+r_1) = mjn^2 + r_2jn + r_1mn + r_1r_2 = n(mjn +r_2j + r_1m) + vn + s = n(mjn+r_2j + r_1m + v) + s$
and $s$ is the remainder of $aq$.
....
And now we can prove that $*$ is associative.
Suppose $a$ has remainder $a'$ and $b$ has remainder $b'$ and $c$ has remainder $c'$.
Not $a$ and $a'$ both have $a'$ as a remainder and $b$ and $b'$ have $b'$ as remainder and $c$ and $c'$ have $c'$ as a remainder.
So $(a*b)*c = $[remainder of ($ab$)]$*c = $[remainder of ($ab'$)$*c =$[remainder of ($a'b'$)$*c =$[remainder of (remainder of $(a'b')$)$\cdot c$]=[remainder of $(a'b')\cdot c$]$ =$
[remainder of $(a'b'c)$]=[remainder of $(a'b'c')$]
And likewise:
$a*(b*c)= a*$[remainder of $bc$]=$a*$[remainder of $b'c$]=$a*$[remainder of $b'c'$]=
[remainder of ($a\cdot $[remainder of $b'c'$])]=
[remainder of ($a \cdot (b'c')$)]=
[remainder of ($a'b'c'$)]$.
And that's that
$(a*b)*c = a*(b*c) = $remainder of $a'b'c'$