Correct Answer - Option 2 : 11
Concept:
Euclid's division lemma: If a and b are two positive integers, then there exist unique positive integers q and r such that
\(a=bq+r\) where \(0\leq{r}\ <\ {b}\) .
If b ∣ a then r = 0 otherwise r must satisfy stronger inequality 0 < r < b.
Calculation:
According to Euclid division lemma, we know that for two positive integers a & b,
\(a=bq+r\) where \(0\leq{r}\ <\ {b}\) .
Repeated divisions give
⇒ 803 = 5 × 154 + 33
⇒ 154 = 4 × 33 + 22
⇒ 33 = 1 × 22 + 11
⇒ 22 = 2 × 11 + 0.
Hence, gcd(803, 154) = 11.
- Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.
- The HCF of two positive integers a and b is the largest positive integer d that divides both a and b.
