Posts

Showing posts from December, 2023

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...

Well-Ordering Principle

Image
 Let  $ \mathbb{Z}$ denotes set of all integers, that is, $\mathbb{Z} = \{\dots,~ -4,~-3,~-2,~-1,~0,~1,~2,~3,~4,~ \cdots\}$ and $\mathbb{Z}^{+}$ denotes set of all nonnegative integers, that is, $\mathbb{Z}^{+} = \{0,~1,~2,~3,~4,~ \cdots\}$.    Well-Ordering Principle : Every nonempty set $S$ of a nonnegative integers contains a least element; that is, there exists integer $a \in S$ such that $a \leq b$ for all $b \in S$. If we take set $S = \{8,~ 5, ~90, ~3, ~29, ~57\}$. One can observe that $S$ is nonempty and $S \subseteq \mathbb{Z}^{+}$ and $3 \in S$ such that $3$ is less than or equal to all other elements of $S$. So that $3$ is the least element of $S$.