Proving associative property, floor function

Question

I need to prove the following operation is associative:

$x*y = xy \pmod 5$

I came up with the equation that $x*y=xy-5[\![xy/5]\!]$

I'm having difficulty proving that $x*(yz)=(xy)*z$. After expanding and then trying to simplify, I have that $x*(yz)=xyz-5z[\![xy/5]\!]$ and $(x*y)*z=xyz-5x[\![yz/x]\!]$ , but cannot then show that the two are equal.

Answer 1

Try to build up $(x*y)*z$ and $x*(y*z)$ in small steps:

From your description we have $xy = 5a + (x*y)$ and $yz = 5b + (y*z)$ for suitable integers $a$ and $b$ (these were the values of the $\mathrm{floor}$ function but that is not really important here).

When you calculate

$$(x*y)z = (xy - 5a)z$$ and $$x(y*z) = x(yz - 5b)$$

you will find that both have the same remainder $\mod 5$.

Answer 2

Here's a different way of looking at this problem. By the Division Theorem, we can state any number $x$ as $5q+r$ where $q \in \mathbb{Z}$ and $0<r<5$. Here, $r$ is the remainder of dividing $x$ by $5$. We'll say that if $x=5q+r$, then $x \equiv r \pmod 5$.

Thus, $x*y \equiv xy \pmod 5$. We want to show that $x*(y*z)=(x*y)*z$. The key to doing this is letting $x=5q_x+r_x$, $y=5q_y+r_y$, and $z=5q_z+r_z$. This means the following:

$$xy=(5q_x+r_x)(5q_y+r_y)=25q_xq_y+5q_xr_y+5q_yr_x+r_xr_y=5(5q_xq_y+q_xr_y+q_yr_x)+r_xr_y$$

$$yz=(5q_y+r_y)(5q_z+r_z)=25q_yq_z+5q_yr_z+5q_zr_y+r_yr_z=5(5q_yq_z+q_yr_z+q_zr_y)+r_yr_z$$

Thus, $xy \equiv r_xr_y \pmod 5$, meaning $x*y=r_xr_y$, and $yz \equiv r_yr_z \pmod 5$, meaning $y*z=r_yr_z$. We can know multiply the former by $z$ and the latter by $x$ to find that this operation is associative.

$$x(y*z)=(5q_x+r_x)r_yr_z=5(q_xr_yr_z)+r_xr_yr_z$$ $$(x*y)z=r_xr_y(5q_z+r_z)=5(r_xr_yq_z)+r_xr_yr_z$$ Thus, as you can see, $x(y*z) \equiv (x*y)z \equiv r_xr_yr_z \pmod 5$. This means $x*(y*z)=(x*y)*z=r_xr_yr_z$, which proves associativity as we wanted to.

For more on modular arithmetic, I highly recommend Khan Academy. It's where I learned modular arithmetic and it's really helpful later on, especially in abstract algebra because cyclic groups have a lot to do with modular arithmetic.