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{align}
  & \Rightarrow 107=13\times 1+r \\
 & \Rightarrow r=107-13 \\
 & \Rightarrow r=94 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 1,94 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 2+r \\
 & \Rightarrow r=107-26 \\
 & \Rightarrow r=81 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 2,81 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 3+r \\
 & \Rightarrow r=107-39 \\
 & \Rightarrow r=68 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 3,68 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 4+r \\
 & \Rightarrow r=107-52 \\
 & \Rightarrow r=55 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 4,55 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 5+r \\
 & \Rightarrow r=107-65 \\
 & \Rightarrow r=42 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 5,42 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 6+r \\
 & \Rightarrow r=107-78 \\
 & \Rightarrow r=29 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 6,29 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 6+r \\
 & \Rightarrow r=107-91 \\
 & \Rightarrow r=16 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 7,16 \right)\].
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 \[\left( q,r \right)\] 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{align}
  & \Rightarrow 107=13\times 8+r \\
 & \Rightarrow r=107-104 \\
 & \Rightarrow r=3 \\
\end{align}\]
So, we can have an ordered pair of \[\left( q,r \right)\] as \[\left( 8,3 \right)\].
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 \[\left( q,r \right)\] ordered pair.
Here, 3 is greater than zero and less than 13.
So, we cannot move further.
Hence, the ordered pairs of \[\left( q,r \right)\] are \[\left( 1,94 \right),\left( 2,81 \right),\left( 3,68 \right),\left( 4,55 \right),\left( 5,42 \right),\left( 6,29 \right),\left( 7,16 \right),\left( 8,3 \right)\].

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 \[\left( 1,94 \right)\] as the one and only ordered pair. But we know that the ordered pairs of \[\left( q,r \right)\] are \[\left( 1,94 \right),\left( 2,81 \right),\left( 3,68 \right),\left( 4,55 \right),\left( 5,42 \right),\left( 6,29 \right),\left( 7,16 \right),\left( 8,3 \right)\]. So, this misconception should be avoided and students should have a clear view on the concept.