---
title: "modular arithmetic"
type: concept
related: [Subgroup, Group, Parallel Linear Algebra, Modular Arithmetic]
source: https://www.jemoka.com/posts/kbhmodular_arithmetic/
confidence: high
status: active
---

Clock math.
We say that \(a\ \text{mod}\ b = r\) if \(a=bq+r\), such that \(b&gt;0\) and \(0 \leq r &lt;b\). More specifically, we denote:
\begin{equation} a \equiv a&rsquo;\ \text{mod}\ b \end{equation}
if \(b|(a-a&rsquo;)\).
additional information basic modular arithmetic operations \begin{align} (a+b)\ \text{mod}\ c &amp;= ((a\ \text{mod}\ c) + (b\ \text{mod}\ c))\ \text{mod}\ c \\ (ab) \ \text{mod}\ c &amp;= ((a\ \text{mod}\ c) (b \ \text{mod}\ c)) \ \text{mod}\ c \end{align}
examples of modular arithmetic If \(a\ \text{mod}\ b = r\), \((-a)\ \text{mod}\ b = -r = b-r\)
\(2^{2}\equiv 4 \equiv -1 \ \text{mod}\ 5\), \(2^{4}\equiv 1\ \text{mod}\ 5\)
USPS&rsquo;s check digit is \(a\ \text{mod}\ 9\) because you can just add all the digits up Let \(a \in \mathbb{Z}\). Let \(s\) be the sum of all the digits in \(a\). \(a \ \text{mod}\ 9 = s \ \text{mod}\ 9\). Why? Not a very satisfying answer, but because \(9\) is \(10-1\), so for each \(n \times 10^{k}\ \text{mod}\ 9\) is always \(-n\) smaller. like how \(10 = 9+1\), \(20 = 2 \times 9+2\), etc.
subgroups Recall the real numbers: \(\dots, -2, -1, 0, 1, 2, 3, \dots\)
That&rsquo;s so many numbers! Instead, let&rsquo;s create a circle of these values. For instance, what if you only want \(5\):
\begin{equation} \mathbb{Z}_{5} = \{0,1,2,3,4\} \end{equation}
This is a group under addition.
humph: similarity between this and affine subsets \(u/U = v/U\) if \(u-v \in U\) \(u \equiv v\ \text{mod}\ b\) if \(b|u-v\) Chinese Remainder Theorem Suppose \(a,b \in \mathbb{Z}\), and \(m,n \in \mathbb{N}\), such that \(\gcd (m,n) = 1\) (that is, suppose \(m,n\) is coprime). There is some \(x \in \mathbb{Z}\) such that:
\begin{equation} x \equiv a \ \text{mod}\ m, x \equiv b\ \text{mod}\ n \end{equation}
Furthermore, and importantly, \(x\ \text{mod}\ (mn)\) is unique.
