home

# Modular arithmetic

## Congruence

Two numbers $$a, b$$ are are congruent $$\bmod k$$ if they have the same remainder when divided by $$k$$. This is conventionally written $a \equiv b \pmod k$ which implies that $a = n \cdot k + r \quad \text{and} \quad b = m \cdot k + r$ and similarly $k\ |\ (a-b), \quad a = n \cdot k + b, n \in \mathbb{Z}$

## Residue

If $$x = a \pmod n$$ then $$a$$ is called the residue of $$x$$ modulo $$n$$. The complete set of all least residues is then $$\{0, 1, 2, \cdots, n\}$$. This may also be noted as $$\mathbb{Z}/n\mathbb{Z}$$ representing the finite set of $$\bmod n$$.

## Algebraic Properties

For all $$a,b,c,d \in \mathbb{Z}$$ and $$n \in \mathbb{Z}_{>1}$$, if $$a \equiv b \pmod n$$ and $$c \equiv d \pmod n$$ the following also hold $a \pm b \equiv c \pm d \pmod n$ $a \cdot b \equiv c \cdot d \pmod n$ $a^{m} \equiv b^{m} \pmod n, \quad \forall m \in \mathbb{N}$

## Multiplicative inverse

Give some integer $$a$$ its modular multiplicative inverse $$x$$ is an integer such that $$ax \equiv 1 \pmod k$$.

As an example under it can be seen that $$2 \cdot 5 \equiv 1 \pmod 9$$ which implies that $$2^{-1} \equiv 5 \pmod 9$$ and $$5^{-1} \equiv 2 \pmod 9$$. Note: $$a^{-1}$$ denotes the inverse, not reciprocal.

Not all numbers will have a modular multiplicative inverse. For example, $$3x \not \equiv 1 \pmod 9\ \forall x$$. In general it can shown that \begin{align*} a \in \mathbb Z \text{ is invertable} \bmod n \iff \gcd(a,n)=1 \end{align*} or simply:, numbers that are prime relative to the modulus are invertible, however factors are not.