====== - #1 Divisibility ======
In the following, $\mathbb Z$ will denote the set of all integers, i.e. $\mathbb Z = \{\dots, -3, -2, -1, 0, 1, 2, 3, 4, \dots\}$, and $\mathbb N$ will denote the set of all natural numbers (aka positive integers), $\mathbb N = \{1, 2, 3, 4, 5, \dots\}$.
===== - Division with remainder =====
Let $b$ be an integer and $a$ be a natural number. Then there exists a unique pair of integers
$(q, r)$, such that $b = qa + r$ and $0 \leq r < a$.
Here $q$ is called the **quotient** and $r$ the **remainder** of dividing $b$ by $a$.
The remainder $r$ is also denoted by $b \operatorname{mod} a$.
{{ :modular:quotient_remainder.png?350 }}
Find the quotient $q$ and the remainder $r$ for the following
divisions $b/a$. Pay attention to the condition $0 ≤ r < a$.
* $6/3$; ++Answer| The quotient is $2$ and the remainder is $0$.++
* $7/3$; ++Answer| The quotient is $2$ and the remainder is $1$.++
* $(−6)/3$; ++Answer| The quotient is $-2$ and the remainder is $0$.++
* $(−7)/3$. ++Answer| The quotient is $-3$ and the remainder is $2$.++
Write a Python script for finding quotients and remainders given an integer $b$ and a natural number $a$.
===== - Divisibility =====
An integer $a$ **divides** an integer $b$ if there is an integer $c$ such that $b = ac$. This is denoted by $a \mid b$.
{{ :modular:divides.png?150 }}
For example, consider the number 6. It divides, e.g., 6, 12, -18, 24, 0 and is divided by 6, -6, 3, -2, 1.
By using the notation from above write down that $6$ is divided by $-2$.
++Answer| $-2 \mid 6$++
Since $0=0\cdot1$, we can write $0 \mid 0$, i.e. zero divides itself. However, **we can not write** $0 \mid b$ where $b\neq 0$ since there is no such integer $c$ that could provide the equality $b=0\cdot c$.
Among the following numbers, which numbers divide which: $0,\ 1,\ -1,\ 2,\ 4,\ -5,\ 10,\ -10$.
++Answer| $1 \mid -1$; $1 \mid 2$; $1 \mid 4$; $1 \mid -5$; $1 \mid 10$; $1 \mid -10$; $1 \mid 0$, $1 \mid 1$;\\ $-1 \mid 2$; $-1 \mid 4$; $-1 \mid -5$; $-1 \mid 10$; $-1 \mid -10$; $-1 \mid 0$; $-1 \mid 1$; $-1 \mid -1$;\\ $2 \mid 4$; $2 \mid 10$; $2 \mid -10$; $2 \mid 0$; $2 \mid 2$;\\ $4 \mid 0$; $4 \mid 4$;\\ $-5 \mid 10$; $-5 \mid -10$; $-5 \mid 0$; $-5 \mid -5$;\\ $10 \mid -10$; $10 \mid 0$; $10 \mid 10$;\\ $-10 \mid 0$; $-10 \mid 10$; $-10 \mid -10$++
If $a$ is a natural number, then $a$ divides $b$ if and only if $b \operatorname{mod} a = 0$.
This is standard criterion for checking divisibility.
Does
* $1$ divides $5$; ++Answer| Since $5 \operatorname{mod} 1=0$, indeed $1 \mid 5$.++
* $4$ divides $10$; ++Answer| Since $10 \operatorname{mod} 4=2$, $4$ does not divide $10$. It is also denoted $4\not\mid 10$.++
* $3$ divides $\pi$; ++Answer| Even though $\pi$ is not an integer, we can extend the definitions to irrational numbers also. Since $\pi \operatorname{mod} 3=0.14\dots$, $3\not\mid \pi$.++
* $e$ divides $\pi$? ++Answer| Since $\pi \operatorname{mod} e=e$, $e\not\mid \pi$.++
===== - Lattice of divisibility =====
In the following let us restrict ourselves to natural numbers.
We can represent all the distinct divisors of a number in a directed graph where there is an arc (aka arrow) from $a$ to $b$ if $a$ divides $b$ and there is no number $c$ (distinct from $a$ and $b$) such that $a$ divides $c$ and $c$ divides $b$.
{{ :modular:lattice?divisibility.png?280 }}
For instance, consider a graph formed by all the divisors of $12$.
{{ :modular:divisibility-lattice.svg?150 }}
Such a graph is called a **lattice of divisibility**.
Apriori it may not be clear that a lattice of divisibility exists for any given number. One might imagine a divisor $a$ such that for any other divisor $b$ there exists $c$ sitting inbetween $a$ and $b$, i.e., satisfying $a\mid c$ and $c\mid b$.
So, why there is no such divisor?
If such a divisor $a$ existed, then taking $c$ in place of $b$ we would find $d$ sitting between $a$
and $c$, then $e$ between $a$ and $d$ and so on. We could go on infinitely. But in practice we cannot go on infinitely.
For instance, if we start with a pair $1\mid 12$ we can quickly discover $1\mid 6$ and $6 \mid 12$ and then discover $1\mid 3$ and $3\mid 6$. Then there is nothing to be put between $1$ and $3$, so there must be an arc from $1$ to $3$.
To understand why this process is finite it is enough to **observe that $a$ can divide $b$ only if $a\leq b$** and for any number $b$ there are only finitely many numbers less than $b$ and greater than $1$, so there are only finitely many divisors of $b$.
Thus, indeed any given number has a lattice of divisibility.
Construct a lattice of divisibility for $24$ by dragging and dropping the given numbers onto
their correct locations in the diagram.
{{url>http://mathwiki.cs.ut.ee/illustrations/diag.html 210px, 360px noborder}}
A number $a$ divides $b$ if and only if there is a path from $a$ to $b$ in the lattice of divisibility.
This follows from the **transitivity** of divisibility. Namely, if $a$ divides $b$ and $b$ divides $c$ then $a$ also divides $c$.
{{ :modular:transitivity.png?380 }}
Transitivity guarantees that there are no directed cycles in the graph. Indeed, let us observe a cycle with an arc from $a$ to $b$ ($a \neq b$):
digraph {
rankdir=BT;
node [shape = circle];
"?"->a->b->"??"->"?"
}
Since it is a cycle, there is path from $b$ to $a$, i.e. $b \mid a$. And there is arc from $a$ to $b$ meaning $a \mid b$. Recall that from $a \mid b$ follows that **$a \leq b$**. We have also $b \mid a$ meaning **$a \geq b$**. Thus $a=b$ which is contradiction.
Let us sum up the properties of divisibility we found:
* $a | b$ only if $a \leq b$,
* $a | b$ and $b | a$ if and only if $a = b$ (antisymmetry),
* $a | b$ and $b |c$ imply $a | c$ (transitivity).
The divisibility relation is a **partial order**. See [[Ordered sets]] for more details on this type of structures.
[[modular:02_primes]]\\