Divisibility

Divisibility 

We say that a nonzero $b$ divides $a$ if $a=qb$ for some $m$, where $a$,$b$ and $q$ are integers.That is $b$, divides $a$ if there is no remainder on division.The notation $b \mid a$ is commonly used to mean$b$ divides $a$.Also, if  $b|a$, we say that $b$ is a divisor of $a$. If $b$ does not divide $a$ we denote it by $b \nmid a$.

For example, $6 \mid 36$  but $7 \nmid 36$. Note that $b \mid 0$ for any non-zero integer $b$ and $1\mid a$ for any integer $a$. When we write $b \mid a$, it is tacitly assumed that $b$ is a non-zero integer.

We can easily deduce the following properties form the definition of divisibility itself

Let $a, b, c ,d$ be any non-zero integers.

1.if $a|1$ , then $a = \pm 1$

2. If $a | b$ and $b|c $  then  $a |c$.

Proof: (1) Suppose $b = na$ and $c = mb$, where $n; m \in Z$. Then $c = m(na) = (mn)a$ and so $a | c$.

3. If $a | b$ and $c| d$ then $ac | bd.$

Proof: (2) Suppose $b = na$ and $d = mc$ where $n; m \in Z.$ Then $bd = (na)(mc) = (mn)(ac)$, i.e.,

$ac | bd.$

4.If $a|x$ and $a|y$ then $a|cx + dy$ for any integers $c; d$.

Proof: $x = an; y = am$

$\Rightarrow  cx + dy = c(an) + d(am)$

$\Rightarrow a(cn + dm) \Rightarrow a|cx+dy$

Example: $7|14$ and $7|63$, Then  $7|(2*14+3*63)$

$7|7(2*7+3*9)$

5.If $d | a$ and $a \ne 0$ then $|d| \le |a|$

6.if $a |b$ and $b |a$ if and only if $a = \pm b$.

$a | b \Rightarrow  |a| \le |b|$

$b | a \Rightarrow |b| \le |a|$

$\Rightarrow  |a| = |b|$

$\Rightarrow a = \pm b$

Quotient and Remainder 

If $a$ and $n$ are integers with $n>0$ , then there is unique pair of integers $q$ and $r$ such that

$$a=qn+r\quad 0 \le r \lt n$$

Example:

If $a=9$ and $n=4$, then we have $9=2*4 + 1$ with $0 \le 1 \lt 4$, so $q=2$ and $r=1$.If $a=-9$ and $n=4$ then $q=-3$ and $r=3$

We call $q$ the quotient and $r$ the remainder.By dividing by $n$, so that

$$\frac{a}{n}=q+\frac{r}{n} \quad  and  \quad 0 \le \frac{r}{n} \lt 1$$

We see that $q$ is the integer part  $\left \lfloor a/n \right \rfloor$ of $a/n$, the greatest integer $i \le a/n$. This makes it easy to calculate $q$, and then to find $r=a-qn$.The remainder is often referred to as a residue.