Definition of divisibility and Theorem on divisibility

  Definition: An integer $b$ is said to be divisible by an integer $a \not = 0$, if there exists some integer $c$ such that $ b = a \cdot c$. An integer $b$ is  divisible by an integer $a \not = 0$, is denoted by $a ~|~ b$.  We write $a \nmid b$ to indicate that $b$ is not divisible by $a$.


Theorem: For integers $a, ~b, ~c$ the following hold:

$1.$ $a ~|~ 0, ~ 1 ~|~ a, ~ a ~|~ a $.

$2.$ $ a ~|~ 1 $ if and only if $a =  1$ or $a = -1$.

$3.$ If $a ~|~ b$ and $c ~|~ d$, then $a \cdot c ~|~ b \cdot d$.

$4.$  If $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$.

$5.$ If $a ~|~ b$ and $b ~|~ a$ if and only if $a = b$ or $a = -b$.

$6.$ If $a ~|~ b$ and $b \not = 0$, then $|a| \leq |b|$.

$7.$ If $a ~|~ b$ and $a ~|~ c$, then $a~ |~ (b \cdot x + c \cdot y)$ for arbitrary integers $x$ and $y$.


Proof: $1.$ For any integer $a$, we can write $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = a \cdot 1$. Therefore proof follows from definition of divisibility. 

 $2.$ Suppose $a ~|~ 1$, therefore there exists integer $c$ such that $1 = a \cdot c$. Since $a, ~c$ are integers and their product is $1$, we get either $a =c=1$ or $a =c= - 1$. Conversely if $a = 1$ or $a = - 1$, then clearly $a ~|~ 1$. 

 $3.$ Suppose $a ~|~ b$ and $c ~|~ d$. Therefore by definition of divisibility there exist integers $e, ~f$ such that $b = a \cdot e$ and $d = c \cdot f$. Taking product of $b = a \cdot e$ and $d = c \cdot f$, we get $b \cdot d = a \cdot c ~(e \cdot f)$. Since $e \cdot f$ is an integer, we get $a \cdot c ~|~ b \cdot d$. 

 $4.$ Suppose $a ~|~ b$ and $b ~|~ c$. Therefore by definition of divisibility there exist integers $e, ~f$ such that $b = a \cdot e$ and $c = b \cdot f$. We put $b = a \cdot e$ in $c = b \cdot f$, we get $c = a \cdot e \cdot f= a ~(e \cdot f)$. Since $e \cdot f$ is an integer, we get $a ~|~ c$. 

 $5.$ Suppose $a ~|~ b$ and $b ~|~ a$. Therefore by definition of divisibility there exist integers $e, ~f$ such that $b = a \cdot e$ and $a = b \cdot f$. We put $b = a \cdot e$ in $a = b \cdot f$, we get $a = a~ (e \cdot f)$. Hence $e \cdot f = 1$. Since $e, ~f$ are integers and their product is $1$, we get either $e =f=1$ or $e =f= - 1$. If $e =f=1$, then $a = b$. If $e =f= -1$, then $a = -b$. In either case $a = b$ or $a = -b$. Conversely, suppose that $a = b$ or $a = -b$. If $a = b$, then we can write $b = a \cdot 1$ and $a = b \cdot 1$, that is, $a ~|~ b$ and $b ~|~ a$. If $a = -b$, then we can write $b = a ~(- 1)$ and $a = b~ (-1)$,  that is, $a ~|~ b$ and $b ~|~ a$. 

 $6.$ Suppose that $a ~|~ b$ and $b \not = 0$. Since $a ~|~ b$, then there exists an integer $c$ such that $b = a \cdot c$. We have $b \not = 0$, this implies that $c \not = 0$. By taking absolute values, we get $|b| = |a \cdot c| = |a| \cdot |c|$. Since $c \not = 0$, we have $|c| \geq 1$. Therefore $|b| \geq |a|$, that is $|a| \leq |b|$. 

 $7.$ Suppose that $a ~|~ b$ and $a ~|~ c$. Therefore there exist integers $e, ~f$ such that $b = a \cdot e$ and $c = a \cdot f$. For any arbitrary integers $x$ and $y$, we have $b \cdot x+c \cdot y = a \cdot e \cdot x + a \cdot f \cdot y = a ~(e \cdot x + f \cdot y)$. Since $(e \cdot x + f \cdot y)$ is an integer, we get $a ~|~ (b \cdot x+c \cdot y)$.

Popular posts from this blog

The Division Algorithm / Prove that given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$.

Image
State and prove Division Algorithm theorem.  Theorem:  Given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$. Proof : Firstly, we will show that the set $S = \{a - x \cdot b \;|\; x \in \mathbb{Z}$ and $  a -x \cdot b \geq 0\}$ is nonempty.  For this purpose, we have to find value of $x$ such that $a -x \cdot b \geq 0$. Given that integer $b > 0$, i.e. $b \geq 1$. Multiply $b \geq 1$ by $|a|$, we get $|a|\cdot b \geq |a|$ and so $a - ( - |a|) \cdot b = a + |a| \cdot b \geq a + |a| \geq 0$. If we take $x = |a|$, then, $a -x \cdot b \in S$. This show that $S$ is nonempty subset of nonnegative integers. By the Well-Ordering Principle (for more details see  Well-Ordering Principle  ) , set $S$ contains a least integer; say it $r$. Since $r \in S$, there exists an i...
Read more

Define Greatest Common Divisor and Prove that if $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$.

Image
Definition: Let $a$ and $b$ be any integers, with at least one of them is not zero. The greatest common divisor of $a$ and $b$, denoted by $gcd(a, b)$, is the positive integer $d$ satisfying the following: $1.$  $d ~|~ a$ and $d ~|~ b$. $2.$ If $c ~|~ a$ and $c ~|~ b$, then $c \leq d$. Theorem:  If $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$. Proof:   Let  $a$ and $b$ be any integers, not both of them are zero. Consider the set $S = \{a \cdot u + b \cdot  v \;|\; a \cdot  u + b \cdot  v > 0$ and $ u, v \in \mathbb{Z}\}$, that is  $S$ is the set of all positive linear combinations of $a$ and $b$. Firstly, we will show  that $S$ is nonempty set. We have taken integers $a$ and $b$ such that not both of them are zero. Without loss of generality, suppose that $a \not = 0$. Then the integer $|a| = a \cdot u + b \cdot 0 \in S$ for the v...
Read more