Prove that $a_1a_2 ≡ b_1b_2 \mod n$

Question

Prove that multiplication is well defined in arithmetic modulo n.
[Assume that $a_1 ≡ b_1 \mod n $ and $a_2 ≡ b_2 \mod n$. Prove that $a_1a_2 ≡ b_1b_2 \mod n$.]

So I know that the assumption means that $n|a_1 - b_1 $ and $n|a_2 - b_2$. It makes sense if both are multiples of n and then I need to get to somehow $n | a_1a_2 - b_1b_2$. Am I missing a theorem or of how if n divides both then I can multiply both together and it will still be a multiple of n?

I appreciate any help.

Answer 1

Note: $$a_1=b_1+pn; \ \ a_2=b_2+qn \ \ \Rightarrow$$ $$a_1a_2=b_1b_2+(b_1q+b_2p+pqn)n.$$

Answer 2

Hint: There's a helpful intermediate step: show that $$ a_1 a_2 \equiv b_1 a_2 \equiv b_1 b_2 \pmod n $$

Answer 3

Hint: $\,a_1a_2-b_1b_2=a_1a_2\color{red}{-b_1a_2+b_1a_2}-b_1b_2=(a_1-b_1)a_2+(a_2-b_2)b_1\,$.

Answer 4

\begin{align} a_1a_2-b_1b_2&=a_1a_2-a_1b_2+a_1b_2-b_1b_2 \\ &=a_1(a_2-b_2)+b_2(a_1-b_1) \end{align}

Answer 5

No, you're not missing any theorem. You're correct in your assumption that $n | a_1 - b_1$ and $n | a_2 - b_2$, but that isn't the part that you want to be thinking of.

Think of expressing $a_1$ as a combination of $n$ and $b_1$, and expressing $a_2$ as a combination of $n$ and $b_2$. What does it mean, numerically, for $a_1 \equiv b_2 \text{mod n}$?

Then, try to combine your expressions in such a way to help you get closer to $a_1a_2 - b_1b_2$.

What you want to be thinking about is: $a_1 = pn + b_1$ and $a_2 = qn + b_2$ for some integers $p$ and $q$.