Let $a, ~b, ~q, ~r $ be integers such that $a = b \cdot q +r$, where $0< r < b$, then $gcd(a,b) = gcd(b,r)$.

 Lemma: Let $a, ~b, ~q, ~r $ be integers such that $a = b \cdot q +r$, where $0< r < b$, then $gcd(a,b) = gcd(b,r)$. 

Proof: Let $gcd(a,b) = d$. Firstly, we show that $d$ is a common divisor of both $b$ and $r$. Since $gcd(a,b) = d$, $d ~|~ a$ and $d ~|~ b$. Therefore by part $7.$ of Theorem, $d ~|~ (a~ -~ b \cdot q)$, i.e. $d ~|~ r$. Thus, $d$ is a common divisor of both $b$ and $r$. Now, we show that $d$ is greatest among all common divisors of both $b$ and $r$. Let $c$ be  an arbitrary common divisor of $b$ and $r$, then by part $7.$ of Theorem, $c ~|~ (b \cdot q + r)$, i.e. $c ~|~ a$. This implies that  $c$ is a common divisor of $a$ and $b$, so that $c \leq d$. This gives $d$ is greatest among all common divisors of both $b$ and $r$ and so  $gcd(b,r ) = d $.

Popular posts from this blog

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$. Theref...
Read more

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

Solve the system of linear congruences $x \equiv 2 ~(mod ~3)$ , $x \equiv 3 ~(mod ~5)$, $x \equiv 2 ~(mod ~7)$.

Example: Solve the system of linear congruences $x \equiv 2 ~(mod ~3)$, $x \equiv 3 ~(mod ~5)$, $x \equiv 2 ~(mod ~7)$. Answer:   Let $ n = 3 \cdot 5 \cdot 7 = 105, ~N_{1} = \dfrac{n}{3} = \dfrac{105}{3} = 35, ~ N_2 = \dfrac{n}{5} = \dfrac{105}{5} = 21, ~ N_3 = \dfrac{n}{7} = \dfrac{105}{7} = 15$. Now, we find solution of linear congruences $35 x_{1} \equiv 1 ~(mod ~3), ~ 2 1 x_2 \equiv 1 ~(mod ~5),  15x_3 \equiv 1 ~(mod ~7)$ We will find solution of linear congruences $35 x_{1} \equiv 1 ~(mod ~3), ~ 2 1 x_2 \equiv 1 ~(mod ~5),  15x_3 \equiv 1 ~(mod ~7)$ by trial and error method.  Firstly we find solution of linear congruence $35 x_{1} \equiv 1 ~(mod ~3)$. We will consider simple values of $x_{1}$ as $1, ~-1,~ 2,~ -2,~ \cdots $ and check which value satisfy given linear congruence $35 x_{1} \equiv 1 ~(mod ~3)$. When we take $x_{1} = 1, ~-1,~ 2,~ -2,~3, ~ -3$, we observe that $x_{1} =1, ~-1,$ are not a solution of $35 x_{1} \equiv 1 ...
Read more