How do addition and multiplication work in modular arithmetic, and what is the key computational rule?

You can reduce mod N at any point during a calculation — this is the fundamental rule that makes modular arithmetic with huge numbers tractable.

The golden rule: $c \equiv a \cdot b \mod N \equiv (a \mod N \cdot b \mod N) \mod N$

This applies to both addition and multiplication:

• Addition: $(7 + 9) \mod 5 = (7 \mod 5 + 9 \mod 5) \mod 5 = (2 + 4) \mod 5 = 1$
• Multiplication: $(7 \cdot 9) \mod 5 = (7 \mod 5 \cdot 9 \mod 5) \mod 5 = (2 \cdot 4) \mod 5 = 3$

Why this matters for cryptography: RSA works with 300+ digit numbers. Without this rule, you'd need to compute $x^e$ first (astronomically large), then reduce mod N. With the rule, you reduce at every step, keeping numbers manageable.

Tip: This rule is the reason modular exponentiation (square-and-multiply) is efficient — you reduce mod N after every squaring and multiplication, never letting the numbers grow beyond $N^2$.

Go deeper:

• Modular arithmetic — properties (Wikipedia) — the reduce-anytime rule stated formally as a ring homomorphism.