Fundamental theory of divisibility

Quotient and Remainder Problem of Integers

The sum, difference and product of two integers are obviously integers but the quotient of two integers may or may not be an integer. For this reason, We say that – An integer $b$ is divisible by an integer $a$ $(a \neq 0)$ , if there is an integer $c$ such that $b=ac$ .

We denote this by $a \mid b$ and read as $a$ divides $b$ . If no such integer can be found we write $a \nmid b$ read as $a$ does not divide $b$ . Again $a \mid b$ then $a$ is called a divisor of $b$ and $b$ is called a multiple of $a$ .

On the other hand, if $a \mid b$ and $0 < a < b$ then $a$ is called a proper divisor or factor of $b$ .

Again $b = ac = (-a)(-c)$ . This shows that if $a\mid b$ then $-a \mid b$ . For practical purposes we can limit our attention to positive divisors of integers.

Remember that $1$ is a divisor of any integer and $0$ is a multiple of any integer. Any non zero integer is a divisor or a multiple of itself. A number which is a multiple of $2$ is called an even number, otherwise it is called an odd number.

THEOREM 1: For any integers $a,b,c$ the following hold

$a \mid b \Rightarrow a \mid bc$ .
$a \mid b$ and $b \mid c \Rightarrow a \mid c$ .
$a \mid b$ and $b \mid a \Rightarrow a = \pm b$ .
$a \mid 1 \Rightarrow a = \pm 1$ .
$a \mid b$ and $a \mid c \Rightarrow a \mid (bx+cy)$ for any integers $x$ and $y$ .

Proof:

Given that, $a \mid b \Rightarrow b= am$ where m is any integer. Now $bc=amc=a(mc) \Rightarrow a \mid bc$ .
If $a \mid b$ and $b \mid c$ then there exist two integers $m$ and $n$ such that $b=am$ and $c=bn$ . Now $c=bn \Rightarrow c=amn \Rightarrow c=a(mn) \Rightarrow a \mid c$ .
Given that $a \mid b \Rightarrow b=am$ and $b \mid a \Rightarrow a=bn$ . From above those equations, we can write that $b=bnm \Rightarrow mn=1$ . Since $mn=1$ then both $m$ and $n$ are $+1$ or $-1$ . Therefore $a=bn \Rightarrow a=\pm b$ .
Given that, $a \mid 1 \Rightarrow 1=am$ . Since $am=1$ then both $a$ and $m$ are $+1$ or $-1$ . Therefore $am=1 \Rightarrow a = \pm 1$ .
Given that, $a \mid b \Rightarrow b=am$ and $a \mid c \Rightarrow c=an$ . Now $bx+cy=amx+any=a(mx+ny) \Rightarrow a \mid (bx+cy)$ .

Now we discuss below about the theory of divisibility

THEOREM 2 (Fundamental theory of divisibility) : For any random pair of integers $a,b(\neq 0)$ we always get another unique pair of integers $q,r$ such that $a=bq+r$ where $0 \le r<b$ .

Proof: Consider the infinite sequence of multiples of $b$ such that $\dots \dots \dots \dots \dots,-3b, -2b, -b, 0, b, 2b, 3b\dots \dots qb, (q+1)b, \dots \dots \dots \dots$ . Obviously $a$ must be equal one of the multiples of $b$ say $bq$ in the sequence or must be between two consecutive multiples say $bq$ and $b(q+1)$ , for any arbitrary $q$ . In either case, we have $bq \le a < b(q+1) \Rightarrow 0 \le a-bq <b$ . Let $a-bq=r \Rightarrow a=bq+r$ . Since $a,b,q$ are integers then $a-bq$ also an integer that is $r$ is an integer. Therefore $0 \le r <b$ . Hence the existence of $q$ and $r$ are proved.

Now we have to show that $q$ and $r$ are unique integers for $a$ and $b$ . Let $q$ and $r$ aren’t unique integers for $a$ and $b$ . Then there exist $q_1,q_2,r_1,r_2$ integers such that $a=q_1b+r_1, 0 \le r_1 <b$ and $a=q_2b+r_2, 0 \le r_2 <b$ .

Therefore $q_1b+r_1=q_2b+r_2 \Rightarrow (q_1-q_2)b=r_2-r_1 \Rightarrow b \mid r_2-r_1$ . But this is impossible. Since both $r_1$ and $r_2$ are positive integers and less than $b$ . Therefore $q$ and $r$ are unique.

Quotient and Remainder Problem of Integers

Now we discuss below about the theory of divisibility

Leave a comment Cancel reply