September 28, 2020

Division

For $a, b\in \Z, a \neq 0$, $a$ divides $b$ if there is some $c \in \Z$ such that

$$ ac=b. $$

Division Theorem: For $a \in \Z$ and $d \in \N$, $d > 0$, there exist unique $q, r\in \Z$ such that $a=qd + r$ and $0\leq r < |d|$.

Facts About Divisibility

  1. If $a \mid b$ and $b \mid c$, then $a\mid c$.
  2. If $a \mid b$ and $a \mid c$ then $a \mid sb+tc$ for all $s$ and $t$.
  3. For all $c\neq 0$, $a\mid b$ if and only if $ca\mid cb$.

Proof. Given that $a \mid b$, there is some $k_1 \in \Z$ such that $ak_1 = b$. Likewise, $ak_2 = c$. So,

$$ sb+tc=s(k_1a)+t(k_2a)=(sk_1+tk_2)a $$

Therefore, $a\mid sb+tc$ where the quotient is some value $sk_1 + tk_2$. This is called an integer linear combination of $b$ and $c$.

Primes

If $p \in \N$, $p>1$ is prime if its only positive factors are 1 and $p$.

$n \in \N$ is composite if $n > 1$ and $n$ is not prime.

How can we tell if $n \in \N$ is prime?

The naïve approach: check if $k \mid n$ for every $1 < k < n$.