Modular arithmetic - sum, product, power

Congruence behaves well with respect to operations: you can “reduce modulo $n$” at any moment of the computation, which makes even otherwise enormous powers feasible.

Property — Compatibility with operations

If $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$, then $a+b \equiv a'+b'\pmod n, \quad a\cdot b\equiv a'\cdot b'\pmod n, \quad a^k\equiv (a')^k\pmod n.$ Modular arithmetic “respects” the operations of sum, product and power. Not always division: $2x\equiv 4\pmod 6$ does not imply $x\equiv 2$ (also $x=5$ works). Modular division requires $\mathrm{mcd}(a,n)=1$.

Example — Fast computation of modular powers

$7^{100}\pmod{13}$. By Fermat $7^{12}\equiv 1\pmod{13}$. Then $7^{100} = 7^{96}\cdot 7^4 = (7^{12})^8\cdot 7^4\equiv 7^4 = 2401 = 13\cdot 184 + 9\equiv 9\pmod{13}.$

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Congruenza
Methods: Aritmetica modulare
Skills: Calcolare · Usare formule