Motivation§

Modular arithmetic will be used in topics like Diffie-Hellman and RSA.

Modular Arithmetic§

Modular Arithmetic

For an integer $p$, we can define $x \pmod{p} = z \pmod{p}$ to mean $p \vert (x - z)$. Often, for any number $x$ we represent it with the unique remainder $x’$ where $0 \leq x’ \lt p$. So,

$$x \pmod{p} \equiv x’.$$

We say that $x \equiv y \pmod{m}$ to say that the remainder of $x$ and $y$ after division by $m$ is the same, not that $x$ equals $y$.

I often use $a \equiv_n b$ interchangably with $a \equiv b \pmod{n}$.

Properties§

  • $x \pmod{p} + y \pmod{p} \equiv (x + y) \pmod{p}$.
  • $(x \pmod{p})(y \pmod{p}) \equiv xy \pmod{p}$.