1
$\begingroup$

i am trying to prove this statement of congruence which is not really hard, but i am stumbling across the simple step.

statement: $a \equiv b \mod m \land c \equiv d \mod m \Longrightarrow ac \equiv bd \mod m$

my steps are:

$a \equiv b \mod m \Longrightarrow a=km+b$ and $c \equiv d \mod m \Longrightarrow c=km+d$
so: $ac =(km+b)(km+d).. \Longrightarrow help$

i need help here how to come to $ac \equiv bd \mod m$

thanks for reading

2 Answers 2

3

You're on the right track, but it would be wise to say $c=jm+d$, to use a different constant from $k$. Then $ ac=(km+b)(jm+d)=kjm^2+bjm+dkm+bd=(kjm+bj+dk)m+bd. $ Since $(kjm+bj+dk)m$ is a multiple of $m$, you've shown $ac\equiv bd\pmod{m}$.

2

You're doing great. Now multiply it out.

  • 0
    :D great, thanks a lot2012-11-18