0
$\begingroup$

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!

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

$\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].$

$\endgroup$
2
$\begingroup$

Hint:

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

$\endgroup$
  • 2
    $\begingroup$ 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. :) $\endgroup$ – Alec May 30 '14 at 20:42
1
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.