DIVISION & DIVISIBILITY
Contents:
Given integers $a$ and $b$, there exist unique integers $q$ and $r$ such that:
$a = qb + r$, where $0 \leq r < \mid b \mid $
For integers $a$, $b$ and $c$, the following hold true:
Given positive integers $a$ and $b$, where at least one of them is non-zero, there exist integers $x$ and $y$ such that:
$\gcd(a, b) = ax + by$
Consider the set of all positive integers that can be expressed as $ax + by$, where $x,y \in \mathbb{Z}$ i.e. consider:
$T = \set{ax + by : ax + by > 0, x,y \in \mathbb{Z}}$
By well-ordering property, T must have a minimum element. Hence, denote d = min(T). The proof involves two parts:
To show the first part, we use the following…
By division algorithm:
Hence, obtain:
For $r_1$, expand $d = ax_0 + by_0$, and eventually obtain:
Hence, if $r_1 > 0$, we have that $ \mid r_1 - r_2 \mid \in \mathbb{Z}$.
But $r_1<d \implies r_1 = 0 \implies a = q_1d \implies d \mid a$
Similarly, show $d \mid b$.
To show the second part, take $c \mid a$ and $c \mid b$
$\implies c \mid ax + by, \forall \text{ } x,y \in \mathbb{Z}$
$\implies c \mid ax_0 + by_0$ i.e. $c \mid d$
$\implies c \leq d$
If a and b are given non-zero integers, then the set…
$T = \set{ax + by : x,y \in \mathbb{Z}}$ (set of all integer linear combinations of a and b)
… is precisely the set of all multiples of $\gcd(a, b)$.
Let $a$ and $b$ be two integers, at least one of which is non-zero. A positive integer d is the GCD of $a$ and $b$ iff the following conditions are met:
This is an iterative process to obtain the GCD of two integers. Given two integers a and b, by division algorithm repeatedly, we obtain the following:
In simple terms, previous divisor becomes next dividend, previous remainder becomes next divisor. The process will terminate when the remainder in the current step is zero. The last non-zero remainder i.e. the current divisor is the GCD of a and $b$.
For any integer $k \neq 0$, $\gcd(ka, kb) = \mid k \mid \gcd(a, b)$.
NOTE: Euclidean algorithm is used for the proof.
For $n > 0$, $\gcd(a, a+n) \mid n$
Let $d = \gcd(a, a+n)$
$d \mid a \implies a = pd$
$d \mid a+n \implies a + n = qd \implies a = qd - n$
Hence, we get:
$pd = qd - n$
$\gcd(qn+r, n) = \gcd(r,n)$
Let $d = \gcd(qn+r, n)$.
Hence, we must prove the following two statements
This will show that $d$ is also the GCD of $r$ and $n$.
Also called coprime integers
Let a and b be non-zero integers. Then, $a$ and $b$ are coprime iff there exist some integers $x,y \in \mathbb{Z}$ such that $ax + by = 1$.
Proof of sufficient part uses the facts that, given $d = \gcd(a, b)$, we have that $ax + by = 1$ for some integers $x$ and $y$, and that $d \mid a$ and $d \mid b \implies d \mid (ax + by)$.
If $d = \gcd(a,b)$, then $\frac{a}{d}$ and $\frac{b}{d}$ are coprime i.e. $\gcd(a/d, b/d) = 1$.
Let $d = \gcd(a, b)$. Then, by definition:
Then, $q_1$ and $q_2$ are relatively prime.
NOTE: This is because $q_1 = \frac{a}{d}$ and $q_2 = \frac{b}{d}$.
If $a \mid c$, $b \mid c$, and $\gcd(a, b) = 1$, then $ab \mid c$.
Proof uses the facts that:
The idea is to substitute $c$ with its expressions with respect to $a$ and $b$ such that $ab$ becomes a common factor among the terms whose sum equals $c$.
If $a \mid bc$ and $\gcd(a,b) = 1$, then $a \mid c$.
Assume $a$ does not divide $b$. Now, consider $a \mid bc$.
$\implies bc = qa$, for some $q \in \mathbb{Z}$
$\implies q = \frac{bc}{a} \in \mathbb{Z}$
But $a$ does not divide $b$, hence:
$\frac{b}{a} \not \in \mathbb{Z} \implies \frac{c}{a} \not \in \mathbb{Z} \implies a \mid c$
If $\gcd(a,c) = 1$ and $\gcd(b,c) = 1$, then $\gcd(ab,c) = 1$.
For positive integers $a$ and $b$, $gcd(a,b) lcd(a,b) = ab$.
Let $d = \gcd(a, b)$. Show that $m = \frac{ab}{d}$ is a common multiple of $a$ and $b$. Then, show that for any positive common multiple $c$ of $a$ and $b$, $m \leq c$. To show that $m \leq c$, show that $m \mid c$. To show that $m \mid c$, show that $\frac{c}{m} = \frac{c}{\frac{ab}{d}} = \frac{cd}{ab}$ is an integer. To do this, use the facts that:
By definition, if p is a prime number, we have the following:
If $p$ is a prime number and $p \mid ab$, then either:
NOTE: This is a special case of Euclid’s lemma.
If $p$ is a prime and $p \mid a_1a_2 … a_n$, then $p \mid a_i$ for some $i \in \set{1, 2… n}$.
If $p, q_1, q_2 … q_n$ are all prime, and $p \mid q_1q_2 … q_n$, then $p = q_i$ for some $i \in \set{1, 2… n}$
Every positive integer $n > 1$ is either a prime or can be uniquely expressed as a product of primes.
NOTE: Uniqueness implies that a positive integer n can be written only with particular amounts of particular primes i.e. n can be written only using one combination of primes.
Note that $p$ is positive.
If $n$ is prime, the proof is complete. Hence, assume $n$ is not prime, which means it has non-trivial factors. Consider the largest possible non-trivial factor of $n$, say $d_1$.
$\therefore n = p_1d$, where $p_1 \in \mathbb{Z}^+$
To show must $p_1$ be prime, suppose $p$ is not prime. Then, we can have $p_1 = a_1b_1$, where:
Hence, $n = a_1b_1d_1 = a_1(b_1d_1)$, where $b_1d_1 > d_1$. Note that $b_1d_1$ must be a non-trivial factor of $n$, since $b < p_1$ and $n = p_1d_1$ This violates the maximality of $d_1$. Hence, $p_1$ must be prime.
If $d$ is prime, the proof is complete. Hence, assume $d$ is not prime, which means it has non-trivial factors. Consider the largest possible non-trivial factor of $n$, say $d_2$.
$\therefore d_1 = p_1 d$, where $p_1 \in \mathbb{Z}^+$
To show must $p_2$ be prime, suppose $p$ is not prime. Then, we can have $p_1 = a_2b_2$, where:
Hence, $d_1 = a_2b_2d_2 = a_2(b_2d_2)$, where $b_2d_2 > d_2$. Note that $b_2d_2$ must be a non-trivial factor of $d_1$, since $b_2 < p_2$ and $d_1 = p_2d_2$. This violates the maximality of $d_2$. Hence, $p_2$ must be prime.
Hence, continue in this manner. Also note that this process must be finite, since $d_k$ will keep reducing for larger $k$ values, and $p_k$ cannot be $1$.
There are infinitely many primes.