Prove on Theory of Congruences

Question

Prove in elementary way: Prove that if $ab \equiv cd \pmod n$ and $b \equiv d \pmod n$, with $\gcd(b,\ n) = 1$. Then how do I prove that $a \equiv c \pmod n$.

Answer 1

Hint:

Observe that

$$ab-cd=a(b-d)+d(a-c)$$

Answer 2

By Bézout, write $1=bx+ny$ and $d=b+nz$; then $$ a\equiv a1\equiv a(bx+ny)=abx+ayn\equiv abx\equiv cdx\equiv c(b+nz)x \equiv cbx\equiv c(1-ny)\equiv c $$

More easily, $b$ has an inverse modulo $n$, call it $x$; then $1\equiv bx\equiv dx$, so from $ab\equiv cd$ we get $$ abx\equiv cdx $$ so $$ a\equiv c $$

(All congruences are modulo $n$.)