# Modular Arithmetic ## Metadata **Status**:: #x **Zettel**:: #zettel/literature **Created**:: [[2024-03-30]] **Topic**:: [[♯ Math]] ## Synopsis Integers modulus p form a [[Ring]] under the binary operator modular addition and modular multiplication. When and only when p is a prime, the ring of integers modulus p is a [[Field]]. ![[Wikipedia Authors - Modular arithmetic (Highlights)#^699857992]] ## Annotations The integers modulus p is a set $\{0, \ldots, p -1\}$. We denote the remainder of an integer _m_ when divided by _p_ as $\overline{m}_p$. Apparently, $\overline{m}_p$ is a member of the integers modulus p. ## Modular Addition Integers modulus p under addition is an [[Abelian Group]]. $ \overline{a}_p + \overline{b}_p = \overline{(a + b)}_p $ The identity under addition is $\overline{0}_p$. The additive inverse of $\overline{a}_p$ is denoted as $-\overline{a}_p$ such that $\overline{a}_p + (-\overline{a}_p) = \overline{0}_p$. The additive inverse is defined for every member: $ -\overline{a}_p = \overline{(kp-a)}_p \text{~for~} \forall{k} \in \mathbb{Z} $ Subtraction is defined as adding the inverse of the right hand operand. $ \overline{a}_p - \overline{b}_p = \overline{a}_p + (-\overline{b}_p) $ ## Modular Multiplication Integers modulus p under division is an [[Monoid (Math)|Monoid]]. $ \overline{a}_p \times \overline{b}_p = \overline{(a \times b)}_p $ The identity under addition is $\overline{1}_p$. The multiplicative inverse of $\overline{a}_p$ is denoted as $\frac{1}{\displaystyle\overline{a}_p}$ such that $\overline{a}_p \times {\displaystyle\frac{1}{\overline{a}_p}} = \overline{1}_p$. The multiplicative inverse is only defined for $\overline{a}_p$ when _a_ is relative prime with p. So when p is a prime, the multiplicative inverse is defined for every member and integers modulus p under division becomes an [[Abelian Group]]. See [[Modular Multiplicative Inverse]] on how to compute the multiplicative inverse. Division is defined as multiplying the inverse of the right hand operand. $ \overline{a}_p \div \overline{b}_p = \overline{a}_p \times {\frac{1}{\overline{b}_p}} $ ## References - [[Wikipedia Authors - Modular arithmetic (Highlights)]]