- #1

Math100

- 756

- 206

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

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