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.
Best Answer
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} $$