I'm sorry if a similar question has been posted before, but I was unable to find one based on my searches. This is an extra practice problem for a number theory class. I've been trying to prove this out, and I'm getting stuck on the transitivity step. This is also a check on myself to make sure that I understand what I need to demonstrate in order to show a congruence.
Here is the full question. I include the last sentence for extra context:
For a submonoid $S$ of a commutative monoid $(M,*)$, define a relation $\equiv$ on the monoid $M\times S$ by $(a,s)\equiv(b,t)$ if there is a $u\in S$ such that $a*t*u=b*s*u$. Show that $\equiv$ is a congruence on $M\times S$. $M$ is a commutative monoid $M$ and $S$ is an arbitrary submonoid of $M$.
Here's what I've written so far. Since I'm dealing with monoids, I don't think I need the part that starts "And finally" (that only applies to groups). Please let me know if I'm mistaken:
We want to see that $\equiv$ is a congruence. That means we need to demonstrate that $\equiv$ is an equivalence relation. Then we want to see that for any $(a,s),(a',s'),(b,t),(b',t') \in M \times S$, if $(a,s) \sim (a',s')$ and $(b,t) \sim (b',t')$, then $(a,s)*(b,t) \sim (a',s')*(b',t')$. And finally, we want to see that for any $(a,s),(a',s') \in M \times S$, if $(a,s) \sim (a',s')$, then $(a,s)^{-1} \sim (a',s')^{-1}$. Note that $a*t*u=b*s*u$ implies that $u \in S$ is at least right cancellable. And since $S$ is a submonoid of a commutative monoid $M$, $u$ is left cancellable, thus cancellable in general.
First, we'll demonstrate that $\equiv$ is an equivalence relation.
Reflexivity
Suppose that $a*s*u=a*s*u$. Then it follows immediately that $(a,s) \equiv (a,s)$.
Symmetry
Suppose that $a*t*u=b*s*u$. Then $(a,s),(b,t) \in M \times S$, and $(a,s) \equiv (b,t)$. Since $=$ is an equality, we have $(b,t) \equiv (a,s)$.
Transitivity
Suppose that $a*t*u_1=b*s*u_1$ and $b*v*u_2=c*t*u_2$ where $u_1,u_2 \in S$.
At this point, I'm stuck trying to show how $(a,s) \equiv (c,v)$. I've tried writing this out multiplicatively, and I thought I would have to use the fact that $u$ is cancellable, but I don't know how to proceed without violating rules.
For instance, I've written on scratch paper: $\frac{a}{t}*\frac{1}{u_1}=\frac{b}{s}*\frac{1}{u_1}$ and $\frac{b}{v}*\frac{1}{u_2}=\frac{c}{t}*\frac{1}{u_2}$. I know that I want to be able to say $\frac{a}{v}*\frac{1}{u_3}=\frac{c}{s}*\frac{1}{u_3}$, but I'm not sure how to get there. I've also written this additively but that led to a dead end as well.
Thanks ahead of time for any help / hints / clues.
Let $atu_1=bsu_1$ and $bvu_2=ctu_2$ for some $a,b\in M$, $s,t,u_1,u_2\in S$.
Multiplying the first equation by $u_2v$, and noting that multiplication is associative and commutative in this setting, we get $$(av)(u_1u_2t)=atu_1u_2v=bsu_1u_2v=(bvu_2)u_1s=(ctu_2)u_1s=(cs)(u_1u_2t).$$ Observe that $u_1u_2t\in S$ since $S$ is a submonoid.