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$.

Question

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.

Answer 1

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} $$

Answer 2

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.