# congruence theorem prove

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

-
add comment

## 2 Answers

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}$.

-
thanks, short and clear! –  doniyor Nov 18 '12 at 9:35
add comment

You're doing great. Now multiply it out.

-
:D great, thanks a lot –  doniyor Nov 18 '12 at 9:20
add comment