Question

for any two positive integers a and b,there exist unique integers q and r such that a=bq+r,then hcf(a,b)=?​

Answer 1

Step-by-step explanation:

Euclid’s division Lemma:

It tells us about the divisibility of integers. It states that any positive integer ‘a’ can be divided by any other positive integer ‘ b’ in such a way that it leaves a remainder ‘r’.

Euclid's division Lemma states that for any two positive integers ‘a’ and ‘b’ there exist two unique whole numbers ‘q’ and ‘r’ such that , a = bq + r, where 0≤r<b.

Here, a= Dividend, b= Divisor, q= quotient and r = Remainder.

Hence, the values 'r’ can take 0≤r<b.

hope help you

please follow me

mark has brainlist

Answer 2

The divisor at this stage $r_{n-1}$ is the highest common factor $(a,b)$ .

Step-by-step explanation:

Given:

There exist unique integers q and r for any two positive integers a and b is

$a=bq+r$.

To find:

To find the $hcf(a,b)$.

Solution:

Using Euclid's division lemma, obtain whole numbers $q_{1}$ and $r_{1}$ such $a=bq+r,0 < r_{1} < b$.

If $r_{1}=0,b$ is the HCF of $a$ and $b$.

If $r_{1}\neq 0$ apply Euclid’s division lemma to $b$ and $r_{1}$ obtain two whole numbers $q_{2}$ and $r_{2}$ such that $b=q_{2}r_{1}+r_{2}$.

If $r_{2} =0$ then $q_{2}$ is the HCF of $a$ and $b$.

If $r_{2} \neq 0$ then apply Euclid’s division lemma to $q_{2}$ and $r_{2}$ continue the above process till the remainder $r_{n}$ zero.

Hence, The divisor at this stage $r_{n-1}$ is the HCF of $a$ and $b$.

#SPJ2