> See also: > - [[Number Theory]] > - [[Integers]] # Divisibility and Modular Arithmetic ## Division Division of an integer by a positive integer produces a quotient (q) and a remainder (r) > [!abstract] **Definition of Division Operation** > If $a$ and $b$ are integers with $a \ne 0$, we say that $a$ *divides* $b$ if there is an integers $c$ such that $b=ac$, or equivalently, if $\frac{b}{a}$ is an integer. > > When $a$ *divides* $b$ we say that $a$ is a *factor* (or *divisor*) of $b$, and that $b$ is a *multiple* of $a$. > > The notation $a \mid b$ denotes that $a$ divides $b$. We write $a \nmid b$ when $a$ does not divide $b$. The *divides* operator can also be defined using logical quantifiers ### The Division Algorithm > [!summary] **The Division Algorithm** > Let $a$ be an integer and $d$ a positive integer. > > Then there are unique integers $q$ and $r$, with $0 \le r < d$, such that $a=dq+r$. > > --- > a This definition is the basis for **quotients** ($q$) and **remainders** ($r$) ### Divisibility ## Modular Arithmetic There are many situations where we are only interested in the remainder when > [!NOTE] Congruence Relations > a > $a \equiv b \pmod m$ The results of modular computations must remain within $Z_n = \{0,1,2,...,n-1\}$ > [!important] Modulo in Mathematics vs Programming > Many programming languages have some sort of implementation of modular arithmetic. > > However, they can often deviate from the general definition used within discrete mathematics/number theory. >a ### Modulo Reduction When working with larger values, **modulo reduction** can be used to simplify modular computations: **Addition Property:** $(a+b)\mod{n} = ((a \mod{n}) + (b \mod{n})) \mod{n}$ **Multiplication Property:** $(a*b)\mod{n} = ((a \mod{n}) * (b \mod{n})) \mod{n}$