# $a \equiv b \pmod n$ and $c\equiv d \pmod n$ implies $ac \equiv bd \pmod n$

Given that $a \equiv b \pmod n$ and $c\equiv d \pmod n$, I need to prove that $ac \equiv bd \pmod n$

So far, I've only managed to deduce that $a+b \equiv c+d \pmod n$. I don't know if this is usable, but it's there, at least.

Any hint would be greatly appreciated!

• @DonAntonio - You're absolutely right. Thanks for pointing it out! – Alec May 30 '14 at 20:17

$\begin{eqnarray} {\bf Hint}\! &&\ \ a\, &=& b\,+\,n\,j\\ &&\ \ c &=& d\,+\,n\,k\\ \Rightarrow\ &&ac &=&\!\!\! bd\,+\,n(\_\_) \end{eqnarray}$

Remark $\$ If $\,n = 10\,$ then this generalizes a units digit rule well-known from decimal arithmetic, viz. mod $10,\,$ the units digit of a product is congruent to the product of the unit digits, e.g. $\,1\color{#c00}3\cdot 1\color{#0a0}6 = 208\,$ has units digit $\,\color{#c00}3\cdot\color{#0a0}6\equiv 8.\,$ Said in the language of the Congruence Product Rule

$$\begin{eqnarray}{\rm mod}\ 10\!: &&1\color{#00}{3}\equiv \color{#00}3,\ \ 1\color{0a0}{6}\equiv \color{0a0}6\\ \Rightarrow\ &&1\color{c00}{3}\cdot 1\color{0a0}{6}\equiv 3\cdot 6\equiv 8\end{eqnarray}\qquad$$

The Congruence Product Rule may be viewed as a radix $\,n\,$ generalization of the units digit product rule. However, it is more general, since the "units digits" $\,b,d\,$ need not lie in the interval $\,[0,n\!-\!1].$

Hint:

$$ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)=\;\ldots$$

• Thanks! That sorted it out. Took me a few minutes to recognize where you were going with it, but that just defines a good hint. :) – Alec May 30 '14 at 20:42

a ≡ b (mod n) means a = b + xn for some x. Work with that definition.

• For some integer $\;x\;$ ... – DonAntonio May 30 '14 at 20:21

Like Gauss did in his Disquisitiones Arithmeticae: $$a\equiv b\pmod{n}$$ implies $$ak\equiv bk\pmod{n}$$ for all $k$.

Suppose now $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$. Then $$ac\equiv bc\pmod{n}$$ and $$bc\equiv bd\pmod{n}.$$ By transitivity, $$ac\equiv bd\pmod{n}.$$