# Divisibility and Modular Arithmetic

Of all other primitive mathematical operations (addition subtraction and multiplication), division is the only operation that is able to produce non-integers out of integers.
$$
u \in \mathbb{Z} \land v \in \mathbb{Z} \to (u+v \in \mathbb{Z}) \land (u-v \in \mathbb{Z}) \land (uv \in \mathbb{Z})\\
\text{but} \\
\frac{4}{3}\notin \,\mathbb{Z}
$$

### Divisibility

> If $a$ and $b$ are integers, we say that $a$ **divides** b if there exists an integer $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** of $b$ or **divisor** of $b$. The notation $a|b$ denotes the proposition $a$ divides $b$. We write $a \nmid b$ when $a$ does not divide $b$. The proposition $a|b$ has the same meaning as $\exists c \in \mathbb{Z}(ac=b)$

#### Properties of divisibility

---

$$
[(a|b) \land (a|c)] \to a|(b+c)
$$

##### Proof

$$
b = au \land c= av \tag{for some $u,v\in \mathbb{Z}$ }\\
b+c = au +av \\
b+c = a(u+v)\\
\text{since $u+v \in \mathbb{Z}$},\\
a|(b+c)
$$

---

$$
a|b \to \forall c\in \Z (a|bc)
$$

##### Proof

$$
b = au \tag{for some $u\in \mathbb{Z}$ }\\
bc = auc \\
bc = a(uc)\\
\text{since $uc \in \mathbb{Z}$},\\
a|(bc)
$$

---

$$
[(a|b) \land (b|c)] \to a|c
$$

##### Proof

$$
b = au \\
c = bv \tag{for some $u,v\in \mathbb{Z}$ }\\
c = auv\\
c = a(uv)\\
\text{since $uv \in \mathbb{Z}$},\\
a|c
$$

---

### Division Algorithm

Let $a,d \in \Z^+$ then there are unique integers $q$ and $r$ with $0 \leq r < d$ such that $a=dq+r$.

- $d$ is called the divisor
- $a$ is the dividend
- $q$ is the quotient ($q= a \text{ div } d$ or $\lfloor \frac{a}{d} \rfloor$)
- $r$ is the remainder ($r = a\mod d$ or $a-d\lfloor \frac{a}{d} \rfloor$)

$$
101 = 11 (9) +2 \\
101 \mod 11 = 2 \\
$$

$$
-11 = 3(-4) +1\\
-11 \mod 3 =1
$$

### Congruency Classes

If $a$ and $b$ are integers and $m$ is a positive integer, then $a$ is congruent to $b$ modulo $m$. We use the notation $a \equiv b\pmod m$ to indicate that $a$ is congruent to $b$ modulo $m$. We say that $a \equiv b\pmod m$ is a congruence and that $m$ is the modulus. If $a$ and $b$ are not congruent in mod $m$ we write $a \not\equiv b\pmod m$.

Let $a,b \in \Z$ then $a \equiv b \pmod m$ if and only if, $a \mod m = b \mod m$ ($a$ and $b$ have the same reminder when divided by $m$)
$$
a \equiv b \pmod m \leftrightarrow m | (a-b)
$$

$$
\begin{align*}
a &= um +r \\
b &= vm +r \tag{for some $u,v\in \mathbb{Z}$ }\\
a-um &= b-vm \\
a-b &= um - vm\\
a-b &= m(u-v)\\
&\text{since $uv \in \mathbb{Z}$},\\
&m | (a-b)
\end{align*}
$$

> The integers $a$ and $b$ are congruent in modulo $m$ if and only if there is an integer $k$ such that $a=b+km$.

Let $m \in \Z^+$. If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then
$$
a+c \equiv b+d \pmod m\\
ac \equiv bd \pmod m
$$
Corollary:
$$
(a+b) \mod m = ((a \mod m)+ b \mod m)) \mod m\\
ab \mod m = ((a \mod m)(b \mod m)) \mod m
$$

#### Arithmetic Modulo

$$
a +_m b = (a+b) \mod m \\
a \cdot_m b = ab \mod m
$$

#### Modular Exponentiation

Finding the remainders of large powers is relatively slow since the values involved will generally cause problems. For example solving:
$$
3^{200} \mod 10
$$
will require the computer to solve for $3^{200}$ which is an extremely big number for your computer to represent. But there is a known trick to solve for problems like this without actually calculating the exact value of $3^{200}$. This technique is considerably fast compared to evaluating $3^{200}$.

To do this we must make use of this theorem:
$$
a \equiv b \pmod {m} \to a^k \equiv b^k \pmod {m}
$$
As an example, lets solve $7^{77} \mod 13$.

>First we need to solve for the remainders:
>$$
>7 \mod 13 = 7 \\
>7^2 \mod 13 =49 \mod 13= 10 \\
>$$
>Which is very straightforward and easy. After this, we need to solve for the next to solve for:
>$$
>7^4 \mod 13=2401 \mod 13
>$$
>To solve this we don't actually need to divide 2401 by 13, in fact we don't need the value 2401 at all. Instead, we can make use of the exponent theorem of modulo to replace $2401$ or $7^4$ with something congruent to $7^4$ in mod $7$.
>$$
>10 \equiv 7^2 \pmod {13}\\
>\text{therefore,}\\
>{10^2} \equiv (7^2)^2 \pmod{13}
>$$
>Therefore we can use $10^2$ or $100$ as a replacement for $7^4$, which will be easier to solve since $100$ is a relatively small number.
>$$
>7^4 \mod 13 = 10^2 \mod 13=9
>$$
>We can do this again and again for the bigger powers until we can almost reach our goal.
>$$
>7^4 \mod 13 = 10^2 \mod 13=9 \\
>7^8 \mod 13 = 9^2 \mod 13=3 \\
>7^{16} \mod 13 = 3^2 \mod 13=9 \\
>7^{32} \mod 13 = 9^2 \mod 13=3 \\
>7^{64} \mod 13 = 3^2 \mod 13=9 \\
>$$
>Solving for $7^{128}$ would be meaningless since that number is greater than $7^{77}$.
>
>After this we need to make use of the fact that $77$ in binary is $1001101$ which means that:
>$$
>77=64+8+4+1
>$$
>which allows us to write $7^{77}$ as :
>$$
>7^{77}=(7^{64})(7^8)(7^4)(7)
>$$
>Which will we can apply on the product rule of modulo:
>$$
>\begin{align*}
>7^{77} \mod 13&=((7^{64}\mod 13) (7^8 \mod 13)(7^4 \mod 13)(7\mod 13) \mod 13) \\
>7^{77} \mod 13&=((9)(3)(9)(7)) \mod 13
>7^{77} \mod 13&=1701 \mod 13\\
>7^{77} \mod 13&=11
>\end{align*}
>$$

### Primes

Every integer greater than one is divisible by at least two, integers, one and itself.
$$
a|a\\
1|a
$$
One of the most interesting kinds of integers are those that have **exactly** two divisors, we call those integers primes. We call integers which have more than two divisors, **composite**.

#### Fundamental theorem of arithmetic

> Every integer greater than 1 can be written uniquely as prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size.

$$
100=2\cdot2\cdot5\cdot5 = 2^2\cdot5^2
$$

#### Checking for primality

> If $n$ is a composite number then $n$ has a prime divisor less than or equal to $\sqrt{n}$.

This theorem is the reason why the brute force algorithm called **trial division** works. The easiest way to check the primality of a given integer is by checking for the divisibility of said number against divisors from $2$ to $\sqrt{n}$.

##### Sieve of Eratosthenes

Sometimes instead of checking whether a specific number is prime or not, you will be asked to look for all the prime numbers up to a specific number. To do thi9s you can use the technique known as Sieve of Eratosthenes.

##### GCD's and LCM's

> Let $a,b \in \mathbb{Z}$, the largest integer $d$ such that $d |a$ and $d|b$ is called the **greatest common divisor** of $a$ and $b$. This is denoted as $\gcd(a,b)$.

The gcd for any two nonzero integers always exists because the set of common divisors is both non-empty and finite.

Example:
$$
\gcd(18,42)=6
$$
The number 18 written as a product of primes is $2(3)(3)$ and 42 as a product of primes is 2(3)(7). The product 2(3) is common for both of them which means their gcd is 2(3) or 6.
$$
\gcd(12,35)=1
$$

$$
12=2(2)(3)\\
35=5(7)
$$

The integers 12 and 35 have no common divisors except, 1 which means their gcd is 1. There's a special name for these kinds of integer pairs. We call 12 and 35 them **relatively prime**. We call a set of integers $\{a_1,a_2,a_3,\cdots\}$, **pairwise relatively prime** if each pair of integer in the set is relatively prime.

> Let $a,b \in \mathbb{Z^+}$. The **least common multiple of $a$ and $b$** denoted by $\text{lcm}(a,b)$, is the smallest positive integer $m$ such that $a|m$ and $b|m$

The prime factorization of integers can also be used to find their lcm.
$$
\text{lcm}(18,42)=2(3)(3)(7)=172\\
18=2(3)(3)\\
42=2(3)(7)
$$
The lcm of 12 and 42 can be found by finding the "union" of their prime factors. Another interesting thing to be noted is that for any two positive integers:
$$
ab=\gcd(a,b)\cdot\text{lcm}(a,b)
$$

##### Euclidean Algorithm

One of the interesting things Euclid discovered was a way to find the gcd of two integers in a relatively fast and deterministic way. Lets demonstrate with an example:
$$
\gcd(287,91)
$$
The first step is to use the division algorithm to divide the larger number by ther smaller number:
$$
287=91(3)+14
$$
next we replace the dividend by the divisor and the divisor by the remainder and divide again:
$$
91=14(6) + 7
$$
and the same process again:
$$
14=7(2)
$$
The gcd of the first two numbers is equal to the divisor when the remainder is 0. In this case, $\gcd(287,91)=7$.

The reason why this algorithm works is because of the theorem:
$$
\gcd(a,b)=\gcd(b,r)
$$
where $a,b\in \mathbb{Z}$ and $r= a \mod b $.

To prove that the Euclidean algorithm works, we need to prove this theorem:

First, let $z$ be any common divisor of $a$ and $b$. Or that:
$$
z|a \land z|b\\
a=zu \land b=zv \tag{for some integers u,v}
$$
Notice that $r$ can be written in terms of $a$ and $b$ like this:
$$
a=bq+r\\
r=a-bq\\
$$
Which means we can substitute $zu$ and $zv$ to $a$ and $b$ respectively
$$
r=zu-zvq\\
r=z(u-vq)\\
z|r
$$
which means that any $z$ which is a divisor of $a$ and $b$ is also a divisor of $r$. But wait there's more, the converse is also provable using a similar manner:

Let $w$ be any common divisor of $b$ and $r$:
$$
w|b \land w|r\\
b=wu \land r=wv \tag{for some integers u,v}
$$
Writing down $a$ in terms of $b$ and $r$, and substituting:
$$
a=bq+r\\
a=wuq+wv\\
a=w(uq+v)\\
w|a
$$
Which means that any $w$ which is a divisor of $b$ and $r$ is also a divisor of $a$. Therefore the pair of integers $a$ and $b$ and the pair of inetgers $b$ and $r$, have same set of divisors, which means that their gcd's are the same as well.

This theorem can be used to prove that the Euclidian algorithm works:
$$
\begin{align*}
a&=bu+r &\gcd(a,b)&=\gcd(b,r)\\
b&=ru_1+r_1 &\gcd(b,r)&=\gcd(r,r_1)\\
r&=r_1u_2+r_2 &\gcd(r,r_1)&=\gcd(r_1,r_2)\\
r_1&=r_2u_3+r_3 &\gcd(r_1,r_2)&=\gcd(r_2,r_3)\\
&~~\vdots &&~~\vdots\\
r_{k-2}&=r_{k-1}u_k+r_k &\gcd(r_{k-2},r_{k-1})&=\gcd(r_{k-1},r_k)\\
r_{k-1} &= r_ku_{k+1}+0 &\gcd(r_{k-1},r_{k})&=\gcd(r_k,0)=r_k
\end{align*}
$$

###### Bézout's Theorem

For all pairs of positive integers, $a$ and $b$, there exists integers $s$ and $t$ such that:
$$
\gcd(a,b)=sa+tb
$$
Proving this identity is quite long and kind of complicated so instead of that we will demonstrate how to find the integers $s$ and $t$ using the **extended euclidean algorithm**. As an example we can try to find $\gcd(252,198)$.
$$
\begin{align*}
252&=198(1)+54\\
198&=54(3)+36\\
54&=36(1)+18\\
36&=18(2)+0
\end{align*}
$$
This shows us that $\gcd(252,189)=18$

First we need to change the divisions above by writing them in terms the remainder:
$$
\begin{align*}
54&=252-198\\
36&=198-54(3)\\
18&=54-36\\
0&=36-18(2)
\end{align*}
$$
Starting from the gcd which is 18, we work our way through substitution to express this in terms of 252 and 198:
$$
18=54-36
$$
We substitute 36 using the values above:
$$
\begin{align*}
18&=54-(198-54(3))\\
&=54-198+54(3)\\
&=54(4)-198
\end{align*}
$$
We then substitute using the divisions above:
$$
\begin{align*}
18&=54(4)-198\\
&=(252-198)(4)-198\\
&=252(3)-198(4)-198\\
&=252(4)-198(5)
\end{align*}
$$

##### Solving Linear Congruences

One of the main uses of Bezout's coefficients are to solve for $x$in a linear congruence in the form:
$$
ax \equiv b \pmod m
$$
This congruence can be solved in the similar manner an equality of the same form is solved:
$$
ax=b
$$
To solve for the above equality we simply multiply both sides by the multiplicative inverse of $a$, since $a\frac{1}{a}=1$:
$$
a\frac{1}{a}x=b\frac{1}{a}\\
x=\frac{b}{a}
$$
We cannot use the same multiplicative inverse to solve congruences beacuse $\frac{1}{a}$ cannot be an integer and therefore is meaningless in the universe of modulo. Instead congruences are solved by multiplying both sides with the **modulo inverse** of $a$, often denoted as $\overline{a}$. This value is any integer, such that when it is multiplied to $a$ it will be congruent to $1$ in modulo $m$.
$$
a\overline{a}\equiv1\pmod m
$$
We can multiply both sides of a congruence with this value and find $x$ for any linear congruence:
$$
a\overline{a}x\equiv b\overline{a} \pmod m\\
x\equiv b\overline{a} \pmod m
$$
The modulo inverse of an integer is guaranteed to exist if $a$ and $m$ are relatively prime. This is because relatively prime integers have a gcd of 1 which means the Bezout's identity:
$$
\gcd(a,m)=1=sa+tm
$$
Since, this is guaranteed by Bezout's theorem, this congruence holds (because they are the left and right are same number altogether)
$$
sa+tm\equiv 1 \pmod m
$$
Since $tm$ is a multiple of $m$ it is safe to conclude that:
$$
tm\equiv0 \pmod m
$$
Which means:
$$
sa\equiv 1 \pmod m
$$
This means that the Bezout's coefficient for $a$ is also the modulo inverse of $a$ in modulo $m$ (if $a$ and $m$ are relatively prime).

Using the example, a while ago we have found that the Bezouts coefficient for
$$
\gcd(4620,1601)=(-35)4620+(101)1601
$$
which means that the modulo inverse for 4620 in modulo 101 is -35:
$$
4620(-35)\equiv 1 \pmod {101}
$$
ultimately any integer congruent to -35 in modulo 101 is also a modulo inverse for 4620:
$$
4620(66)\equiv 1 \pmod {101}\\
4620(167)\equiv 1 \pmod {101}\\
\vdots
$$

##### Chinese remainder theorem

>Let $m_1,m_2,m_3,\cdots,m_n$ be pairwise relatively prime positive integers greater than one, and let $a_1, a_2,a_3,\cdots,a_n$ be arbitrary integers. Then the system of congruences:
>$$
>\begin{align*}
>x&\equiv a_1 \pmod {m_1} \\
>x&\equiv a_2 \pmod {m_2} \\
>x&\equiv a_3 \pmod {m_3} \\
>&~~\vdots\\
>x&\equiv a_n \pmod {m_n}
>\end{align*}
>$$
>has a unique solution modulo $m=m_1m_2m_3\cdots m_n$. This means that there is a solution $x$ such that $0\leq x < m$, and all othjer solutions are congruent in modulo $m$ to $x$.

###### Proof

The prove this theorem let $M_k=m_k$ for all $k$ in $1,2,3,\cdots,n$. This number is basically the product of all moduli in the system except $m_k$. The integer $M_k$ is guaranteed to be relatively prime with $m_k$ since $m_k$ is relatively prime to all other moduli in the system. This means each $M_k$ has a corresponding modulo inverse in modulo $m_k$. Lets call this number $w_k$.
$$
M_kw_k\equiv1\pmod{m_k}
$$
This means that we can construct a solution:
$$
x=a_1M_1w_1+a_2M_2w_2+a_3M_3w_3+\cdots+a_nM_1w_n
$$
First, note that $M_j \equiv 0 \pmod {m_k}$ for any pair of $j\neq k$. This is because $m_k$ is guaranteed to divide $M_j$ ($m_j$ is the only moduli not in the product $M_j$). This means that for any modulo $m_k$ in the system only $a_kM_kw_k$ contributes to the sum. We know that this value is congruent to $a_k$ because we have established that $M_kw_k\equiv 1 \pmod{m_k}$. This means that this sum $x$ is indeed a solution for the system.

To demonstrate this we can use the example system:
$$
\begin{align*}
x&\equiv 2 \pmod {3} \tag{1}\\
x&\equiv 3 \pmod {5} \tag{2}\\
x&\equiv 2 \pmod {7} \tag{3}
\end{align*}
$$
First we calculate $M_k$ values for each congruence:
$$
M_1=35 \\
M_2=21 \\
M_3=15
$$
And then we find each inverse for $M_k$ in modulo $m_k$:
$$
35(-1) \equiv 1 \pmod{3} \\
21(1) \equiv 1 \pmod{5} \\
15(1) \equiv 1 \pmod{7}
$$
Therefore the solution:
$$
x=2(35)(-1)+3(21)(1)+2(15)(1)\\
x=23
$$
where other solutions are:
$$
x\equiv23\pmod {105}
$$