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)$.
 A: Since $\gcd(a,n)=d$, we get
$$\gcd\bigg(\frac{a}{d},\frac{n}{d}\bigg)=1.$$ Write 
$$r=\frac{a}{d}\quad\text{and}\quad s=\frac{n}{d}.$$ Then $$\gcd(r,s)=1\quad\text{and}\quad \frac{a}{n}=\frac{r}{s}.$$ Also, we get
$$n\big|(ab-ac).$$ Hence,
$$\frac{ab-ac}{n}\in\Bbb Z.$$ But,
$$\begin{align}
\frac{ab-ac}{n}&=\frac{a(b-c)}{n}\\
&=\frac{r(b-c)}{s}.
\end{align}$$
Hence,
$$\frac{r(b-c)}{s}\in\Bbb Z.$$
Thus,
$$s\big|r(b-c).$$ 
Since $\gcd(r,s)=1$, using the Euclid's Lemma, we get
$$s\big|(b-c).$$
Hence, $$b \equiv c \mod s.$$
Thus, $$b \equiv c \mod{\frac{n}{d}}.$$
A: Note that since $d=(a,n)$
$$
a(b-c)=kn\implies\frac ad(b-c)=k\frac nd\tag{1}
$$
Since $\left(\frac ad,\frac nd\right)=\frac{(a,n)}d=1$, Bezout's Identity says there are $x,y\in\mathbb{Z}$ so that
$$
x\frac ad+y\frac nd=1\tag{2}
$$
Therefore, applying $(1)$ and $(2)$, we get
$$
\begin{align}
xk\frac nd
&=x\frac ad(b-c)\\
&=\left(1-y\frac nd\right)(b-c)\\
\left(xk+y(b-c)\right)\frac nd\tag{3}
&=b-c
\end{align}
$$
which says that
$$
b\equiv c\quad\left(\text{mod}\,{\frac nd}\right)\tag{4}
$$
A: 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$
