Modulus simplification $(mn) \bmod d = ab$?

383 Views Asked by At

I have a modulus question that needs me too prove whether two different statements are true or false.

The information I have been given is that: \begin{align} m \bmod d &= a\\ n \bmod d &= b\\ \end{align} \begin{align} m &= dk+a\\ n &= dl+b \end{align}

(..where $k,l,$ and $d$ are integers, with $d>0$.)

I need to demonstrate that $(dkdl-dkb-adl+ab) \bmod d = ab$ by using $(mn)\mod d = ab$. However, I am unsure on how to simplify the LHS.

I also need to show why $(mn) \bmod d = (ab) \bmod d.$

2

There are 2 best solutions below

2
On

Hint: note that $d \equiv 0 \pmod{d}$. Thus, any term like $dkdl \equiv 0\cdot k\cdot 0 \cdot l\equiv 0 \pmod{d}$

Does this help simplify $dkdl-dkb-adl+ab \pmod{d}$?

0
On

For any set of integers $a,b,m,n,d$ $$m\equiv a\pmod d, n\equiv b\pmod d$$

$$\implies mn-ab=m\underbrace{(n-b)}_{\text{ divisible by }d}+b\underbrace{(m-a)}_{\text{ divisible by }d}\equiv0\pmod d$$