Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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


using [2]

$C \mod 7= \left(\begin{array}{cc} 2 & 11 \\ 3 & 6 \\ \end{array}\right)$

This doesn't result in the same matrix.

share|cite|improve this question
up vote 3 down vote accepted

Once you take pass into modular arithmetic, you're stuck there: $C \mod{7}$ has values in the integers $\mod{7}$, not in the integers themselves.

But modulo 7, $\left(\begin{matrix}2&11\\3&6\end{matrix}\right)=\left(\begin{matrix}2&4\\3&6\end{matrix}\right)$ simply because $11\equiv 4 \mod{7}$.

And in general, yes, you can apply $[2]$; you can even get $C\mod{7}\equiv(A\mod{7})(B\mod{7})\mod{n}$.

All this follows from the facts that $$ab \mod{n}\equiv (a\mod{n}b\mod{n}) \mod {n}$$ and $$a+b \mod{n}\equiv (a\mod{n}+b\mod{n}) \mod{n}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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