Show that if $ab \equiv ac$ mod $n$ and $d=(a,n)$, then $b \equiv c$ mod $\frac{n}{d}$ What I know so far: 
We know by the definition of congruence that $n$ divides $ab-ac$. So, there exists an integer $k$ such that $a(b-c)=kn$, and since $d=(a,n)$ we know that $a=ds$ and $n=dt$ from some integers $s$ and $t$.  Then substituting for $a$ and $n$, we see that $ds(b-c)=k(dt)$.

Let $\,x=b\!-\!c.\ $ Then $\ n\mid ax\!\iff\! n\mid ax,nx$ $\iff\! n\mid(ax,nx)=(a,n)x\!\iff\! \dfrac{n}{(a,n)}\mid x$
