Question

If $$a=107,b=13$$ using the Euclid division algorithm find the values of q and r such that $$a=bq+r$$.

Answer 1

Hint: We should know the definition of lemma and the concept of Euclid division lemma to solve this problem. A lemma is a proven statement used for proving another statement. So, according to Euclid's Division Lemma, if we have two positive integers a and b, then there would be whole numbers q and r that satisfy the equation $$a=bq+r$$ where 0 < r < b, a is the dividend and b is the divisor. Based on the definition of Euclid Division Lemma, we should find the different values of r for different values of q until 0 < r < b.

Complete step-by-step answer:
Before solving the problem, we should know the definition of a Lemma and the definition of Euclid’s Division Lemma. A lemma is a proven statement used for proving another statement. So, according to Euclid's Division Lemma, if we have two positive integers a and b, then there would be whole numbers q and r that satisfy the equation $$a=bq+r$$ where 0 r < b, a is the dividend and b is the divisor.
From the question, we were the $$a=107,b=13$$.
Now we have to find all the values of q and r such that $$a=bq+r$$ by using the Euclid Division algorithm.
Now let us substitute $$a=107,b=13$$ in $$a=bq+r$$.
$$\Rightarrow 107=13q+r....(1)$$
Let us substitute $$q=1$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 1+r\\ & \Rightarrow r=107-13\\ & \Rightarrow r=94\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(1,94)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 94 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=2$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 2+r\\ & \Rightarrow r=107-26\\ & \Rightarrow r=81\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(2,81)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 81 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=3$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 3+r\\ & \Rightarrow r=107-39\\ & \Rightarrow r=68\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(3,68)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 68 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=4$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 4+r\\ & \Rightarrow r=107-52\\ & \Rightarrow r=55\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(4,55)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 55 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=5$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 5+r\\ & \Rightarrow r=107-65\\ & \Rightarrow r=42\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(5,42)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 42 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=6$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 6+r\\ & \Rightarrow r=107-78\\ & \Rightarrow r=29\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(6,29)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 29 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=7$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 6+r\\ & \Rightarrow r=107-91\\ & \Rightarrow r=16\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(7,16)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 16 is greater than zero but not less than 13.
So, we can move further.
Let us substitute $$q=8$$ in equation (1), then we get
$$\begin{array}{rl}& \Rightarrow 107=13\times 8+r\\ & \Rightarrow r=107-104\\ & \Rightarrow r=3\end{array}$$
So, we can have an ordered pair of $$(q,r)$$ as $$(8,3)$$.
We know that the values of q and r will be obtained until \[0\le rNow we have to check whether the condition is satisfied or not. If the condition is satisfied then that will be the last $$(q,r)$$ ordered pair.
Here, 3 is greater than zero and less than 13.
So, we cannot move further.
Hence, the ordered pairs of $$(q,r)$$ are $$(1,94),(2,81),(3,68),(4,55),(5,42),(6,29),(7,16),(8,3)$$.

Note: Students may have a misconception that if 0 < r < b is not followed, then we cannot go further. If this misconception is followed, then we will get $$(1,94)$$ as the one and only ordered pair. But we know that the ordered pairs of $$(q,r)$$ are $$(1,94),(2,81),(3,68),(4,55),(5,42),(6,29),(7,16),(8,3)$$. So, this misconception should be avoided and students should have a clear view on the concept.