[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/modular_arithmetic.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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>0\) and \(0 \leq r <b\). More specifically, we denote: \begin{equation} a \equiv a’\ \text{mod}\ b \end{equation} if \(b|(a-a’)\). additional information basic modular arithmetic operations \begin{align} (a+b)\ \text{mod}\ c &= ((a\ \text{mod}\ c) + (b\ \text{mod}\ c))\ \text{mod}\ c \\ (ab) \ \text{mod}\ c &= ((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’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’s so many numbers! Instead, let’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.