Prove that if a ≡ b mod m and c ≡ d mod m, then ac ≡ bd mod m.

Question

Prove that if a ≡ b mod m and c ≡ d mod m, then ac ≡ bd mod m.

In previous attempts I have tried to express a as b + mk and c as d + ml and I have also shown that m|a-b and m|c-d but I was unable to reach a complete proof.

Just a problem I have been trying to solve out of interest.

Answer 1

By hypothesis, $a=b+km$ and $c=d+lm$. Then

$ac = (b+km)(d+lm) = bd + blm + dkm + klm^2 = bd + m(bl+dk+klm)$

and so

$ac\equiv bd\mod m$.

Answer 2

When you set $a=b+mk$ and $c=d+mk$, you imply that the $k$ is the same in both cases. There is nothing to suggest that this is the case. Apart from that, this is a good approach.

If we set $a=b+ms$ and $c=d+mt$ for integers $s,t$, then $$ ac=(b+ms)(d+mt)=bd+m(bt+cs+msc) $$ which implies that $$ ac\equiv bd\pmod m$$ as their difference is a multiple of $m$.

Alternately, if $m\mid b-a$ and $m\mid d-c$, then we also have that $$ d(b-a)+a(d-c)=bd-ad+ad-ac=bd-ac $$ is a multiple of $m$.

Answer 3

Just continue.

If $a = b + mk$ and $c=d + mj$ (you shouldn't assume $a$ and $b$ and $c$ and $d$ are both off by the same multiple of $m$)

Then $ac = (b+mk)(d+mj) = bd+dmk + bmj + kjm^2 = bd + m(dk+bj + kjm)$. So.... that's it.

And $m|b-a$ and $m|c-d$ means that for any integers $j,k$ we have $m|(b-a)j + (c-d)k = bj -aj + ck - dk$. And if we let $j=-c$ (to turn $-aj$ into $ac$) and $k = b$ (to turn $-dk$ into $-bd$) we get $m|(b-a)(-c) + (c-d)b = -bc +ac +bc -bd = ac-bd$.

Or in other word $ac -bd = ac-bc + bc -bd = (a-b)c + (c-d)b$ and as $m|a-b$ and $m|c-d$ we have $m| (a-b)c + (c-d)b=ac-bd$.

That's a little harder to see and requires a bit of cleverness. But the first $ac = (b+mj)(d+mk)$ happens automatically.