Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$. 
Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$.

From this we know that $\gcd(d, n) = 1$. I can't derive anything else. Please help. Is there some basic theorem which points to this? Can we cut out $b$ and $d$ in $ab \equiv cd \pmod{n}$ if we know they leave the same residues $\pmod n$?
Thanks.
 A: Lemma. If $xz\equiv yz \pmod{n}$, then $x\equiv y\pmod {\frac{n}{d}}$, where $d=\gcd(n,z)$.
Proof. $n|z(y-x)\implies \frac{n}{d}\big| \frac{z}{d}(y-x)$. Hence, $\gcd(\frac{n}{d},\frac{z}{d})=1$, which implies that $\frac{n}{d}\big|(y-x)$.//
Now, since $\gcd(b,n)=\gcd(d,n)=1$, we can use the above lemma as follows:
$$
\begin{aligned}
ab\equiv cd\pmod{n}\text{ and }b\equiv d\pmod {n} &\implies abd\equiv cbd\pmod {n}\\
&\implies ab\equiv cb\pmod {n}\qquad\text{by the lemma}\\
&\implies a\equiv c\pmod{n}\qquad\text{by the lemma}.
\end{aligned}
$$ 
A: For some reason I think it is fun solving problems like this using Bezout's lemma: since ${\rm gcd}(b,n) = 1$ there exist integers $x$ and $y$ with 
$$\tag 1 bx + ny = 1.$$
Since $ab \equiv cd \bmod n$ there is an integer $s$ such that $$\tag 2 ab = cd + ns$$ and since $b \equiv d \bmod n$ there is an integer $t$ such that $$\tag 3 b = d + nt.$$ 
Multiply line (1) by $a$ and $c$ individually to get 
\begin{align} \tag 4 abx + any &= a \\ \tag 5 bcx + cny &= c.\end{align}
Multiply line (2) by $x$ to get $$\tag 6 abx = cdx + nsx$$ and multiply line (3) by $cx$ to get $$\tag 7 bcx = cdx + cntx.$$ Now subtract (7) from (6) to get $$abx - bcx = n(sx - ntx)$$ and use this result to subtract (5) from (4):
$$n(sx - ntx) + n(ay - cy) = a-c.$$ Thus $n$ divides $a-c$ as you wanted.
