What are the rules for modular arithmetic when multiplying two matrices? I want to calulate $C = AB \mod{n}.$ Aside from the obvious way of performing the modulo after the multiplication, when and where can i safely perform the modulo during the multiplication algorithm?
[1] Normally:
$C_{ij}=\displaystyle\sum\limits_{k=0}^m A_{ik}B_{kj}$
Can I take each of these summands $A_{ik}B_{kj} \mod{n}$, as follows?
[2]
$C_{ij}=\displaystyle\sum\limits_{k=0}^m [ A_{ik}B_{kj}\pmod{n} ]$
Here is an example:
$A = \left(\begin{array}{cc} 9 & 2 \\ 10 & 10 \\ \end{array}\right)$
$B = \left(\begin{array}{cc} 7 & 3 \\ 1 & 6 \\ \end{array}\right)$
$C = \left(\begin{array}{cc} 65 & 39 \\ 80 & 90 \\ \end{array}\right)$
$C \equiv \left(\begin{array}{cc} 2 & 4 \\ 3 & 6 \\ \end{array}\right) \mod{7}$
edit:
using [2]
$C \mod 7= \left(\begin{array}{cc} 2 & 11 \\ 3 & 6 \\ \end{array}\right)$
This doesn't result in the same matrix.