2

My lecturer's powerpoint has the following proof but I feel like it's missing a step. Could I get some help with how the final conclusion is reached. Thank you.

For multiplication, since we know that $m|(b-a)$ we also know $m|(b-a)c$, that is, $ac \equiv bc \mod m$.

Similarly, we get $bc \equiv bd \mod m$.

(missing a step?)

Then we can conclude that $ac \equiv bd \mod m$.

ireallydonknow
  • 1,415
  • 2
  • 14
  • 33
user2979879
  • 55
  • Equivalence modulo $m$ is transitive, so if $ac \equiv bc \pmod m$, and $bc \equiv bd \pmod m$, then $ac \equiv bd \pmod m$. – Michael Albanese Jan 11 '14 at 13:15
  • ah yeah looking at my notes on transitivity I can see why. Thank you for your help! – user2979879 Jan 11 '14 at 13:18
  • No worries. I will put my comment as an answer so this question does not remain unanswered. If you think it is acceptable, you can click the check mark on the left of the answer, or you can up/down vote it using the relevant arrows. – Michael Albanese Jan 11 '14 at 13:21

3 Answers3

1

Equivalence modulo $m$ is transitive, so if $ac \equiv bc \pmod m$, and $bc \equiv bd \pmod m$, then $ac \equiv bd \pmod m$.

Michael Albanese
  • 99,526
0

"Similarly, we get $bc \equiv bd \mod m$"

The step is similar to the previous one.

Since we have $c \equiv d \mod m \iff m|(c-d) \implies m|(bc-bd) \iff bc \equiv bd \mod m$

Combining what you have, i.e (And applying the symmetrical properties of the modulo relation)

$$ac \equiv bc \mod m$$ and

$$-bd \equiv -bc \mod m$$

Using the addition rule, we have

$$(ac-bd) \equiv 0 \mod m \iff ac \equiv bd \mod m$$

ireallydonknow
  • 1,415
  • 2
  • 14
  • 33
0

HINT:

Observe that $$ac-bd=c\underbrace{(a-b)}+b\underbrace{(c-d)}$$

Similarly, $$ad-bc=d\underbrace{(a-b)}-b\underbrace{(c-d)}$$

lab bhattacharjee
  • 274,582