Prove that whenever ## ab\equiv cd\pmod {n} ## and....

[Math100]

Homework Statement

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

Relevant Equations

None.

Proof:

Suppose $ab\equiv cd\pmod {n}$ and $b\equiv d\pmod {n}$, with $gcd(b, n)=1$.
Then $n\mid (ab-cd)\implies nk=ab-cd$ and $n\mid (b-d)\implies nq=b-d$ for some $k, q\in\mathbb{Z}$.
This means $d=b-nq$.
Now we substitute $d=b-nq$ into the equation $nk=ab-cd$.
Observe that
\begin{align*}
nk=ab-c(b-nq)\\
nk=ab-bc+cnq\\
nk-cnq=b(a-c)\\
n(k-cq)=b(a-c)\\
nr=b(a-c)\\
\end{align*}
where $r=k-cq$ is an integer.
Thus $n\mid [b(a-c)]$.
Note that $b\mid m$ if $b\mid (mn)$ and $gcd(b, n)=1$.
Since $n\mid [b(a-c)]$ and $gcd(b, n)=1$, it follows that $n\mid (a-c)$.
Thus $a\equiv c\pmod {n}$.
Therefore, $a\equiv c\pmod {n}$ whenever $ab\equiv cd\pmod {n}$ and $b\equiv d\pmod {n}$, with $gcd(b, n)=1$.

 

[fresh_42]

That's correct.

You hadn't to introduce $m$ since $m=a-c$ has already names.

You used the fact that $gcd(b,n)=1$ is equivalent to the fact that $b$ has a multiplicative inverse modulo $n$ which is equivalent to the fact that $1=sb+tn$ for some integers $s,t.$ Once you have shown these equivalences ($b$ and $n$ are coprime, $b$ has an inverse element modulo $n$, Bézout's lemma: there are $s,t$ such that $1=sb+tn$), you can use all of them, i.e. the one that fits best.

E.g., since $b$ has an inverse, we get from $nr=b(a-c)$ that $b^{-1}nr=a-c$ and thus $a-c\equiv 0\pmod n.$

Or, even simpler:
\begin{align*}
gcd(b,n)=1 &\Longrightarrow \exists \,b^{-1} \pmod n \\&\Longrightarrow ab\equiv cd \equiv cb \pmod n\\
&\Longrightarrow a\equiv abb^{-1}\equiv cbb^{-1}\equiv c\pmod n
\end{align*}

You should show that they are equivalent in order to practice proof writing. This can be done e.g. by
$b$ and $n$ are coprime $\Longrightarrow$ there are $s,t$ such that $1=sb+tn$ $\Longrightarrow$ $b$ has an inverse element modulo $n$ $\Longrightarrow$ $b$ and $n$ are coprime

 

[Math100]

That's correct.

You hadn't to introduce $m$ since $m=a-c$ has already names.

You used the fact that $gcd(b,n)=1$ is equivalent to the fact that $b$ has a multiplicative inverse modulo $n$ which is equivalent to the fact that $1=sb+tn$ for some integers $s,t.$ Once you have shown these equivalences ($b$ and $n$ are coprime, $b$ has an inverse element modulo $n$, Bézout's lemma: there are $s,t$ such that $1=sb+tn$), you can use all of them, i.e. the one that fits best.

E.g., since $b$ has an inverse, we get from $nr=b(a-c)$ that $b^{-1}nr=a-c$ and thus $a-c\equiv 0\pmod n.$

Or, even simpler:
\begin{align*}
gcd(b,n)=1 &\Longrightarrow \exists \,b^{-1} \pmod n \\&\Longrightarrow ab\equiv cd \equiv cb \pmod n\\
&\Longrightarrow a\equiv abb^{-1}\equiv cbb^{-1}\equiv c\pmod n
\end{align*}

You should show that they are equivalent in order to practice proof writing. This can be done e.g. by
$b$ and $n$ are coprime $\Longrightarrow$ there are $s,t$ such that $1=sb+tn$ $\Longrightarrow$ $b$ has an inverse element modulo $n$ $\Longrightarrow$ $b$ and $n$ are coprime

I like the one you've used under "Or, even simpler:".

 

[fresh_42]

I like the one you've used under "Or, even simpler:".

But it was written a bit sloppy. Better would have been:

\begin{align*}
ab\equiv cd \pmod n \wedge b\equiv d \pmod n &\Longrightarrow ab\equiv cd \equiv cb \pmod n\\
gcd(b,n)=1 &\Longrightarrow \exists \,b^{-1} \pmod n \\
&\Longrightarrow a\equiv abb^{-1}\equiv cbb^{-1}\equiv c\pmod n
\end{align*}