Modular arithmetic

Modular arithmetic concerns the algebraic properties of natural numbers that have been “cut off” at a certain point.

Modular congruence

The starting point of modular arithmetic are the modular congruence relations $\equiv 𝑛$ , where for two natural numbers $𝑥, 𝑦 \in ℕ$

𝑥 \equiv 𝑛 𝑦 ⟺ 𝑛 ∣ (𝑦 - 𝑥)

that is $𝑥, 𝑦$ have the same remainder after euclidean division by $𝑛$ .

Quotients

The congruence relations create new algebraic structures called the Algebraic quotient, denoted $ℤ / \equiv 𝑛$ or equivalently $ℤ 𝑛$ , The properties of $ℤ 𝑛$ as a Congruence relation allow us to define

[𝑥] + [𝑦] = [𝑥 + 𝑦] [𝑥] \times [𝑦] = [𝑥 \times 𝑦]

Hence, $(ℤ 𝑛, +, \times)$ constitutes a Ring.

Quotient ring $ℤ 𝑛$

In the case that $𝑛$ is prime, $ℤ 𝑛$ constitutes an field, which follows from A finite integral domain is a field.

Addition and multiplication are commutative (i.e. $+$ forms an Abelian group, $\times$ forms an abelian monoid/group) $𝑥 + 𝑦 \equiv 𝑦 + 𝑥 𝑥 \times 𝑦 \equiv 𝑦 \times 𝑥$
There is an additive identity $0$
Additive inverse exists
There is a multiplicative inverse $1$
Some elements (called units) may have a multiplicative inverse

Properties of modular arithmetic

#state/tidy | #lang/en | #SemBr

Modular arithmetic

Modular congruence

Quotients

Quotient ring ℤ𝑛

Properties of modular arithmetic

Quotient ring $ℤ 𝑛$