Modular multiplication

Dependencies:

1. Modular Equivalence

If $a_1 \equiv b_1 \pmod{n}$ and $a_2 \equiv b_2 \pmod{n}$, then $a_1a_2 \equiv b_1b_2 \pmod{n}$.

Proof

\begin{align} & a_1 \equiv b_1 \wedge a_2 \equiv b_2 \pmod{n} \\ &\Rightarrow n \mid (a_1-b_1) \wedge n \mid (a_2-b_2) \\ &\Rightarrow n \mid b_2(a_1-b_1) + a_1(a_2-b_2) \\ &\Rightarrow n \mid (a_1a_2 - a_1b_2 + a_1b_2 - b_1b_2) \\ &\Rightarrow n \mid (a_1a_2 - b_1b_2) \\ &\Rightarrow a_1a_2 \equiv b_1b_2 \pmod{n} \end{align}

Dependency for:

1. Zn is a ring
2. Gauss' Lemma

Info:

• Depth: 1
• Number of transitive dependencies: 1

Transitive dependencies:

1. Modular Equivalence