Question

According to Euclid's division algorithm, which of the following is true for a=37 b=5
37=5×7+2
37=5×6+6
37=5×8-3
All the above​

Answer 1

Answer:

According to Euclid's division lemma,

 

For each pair of positive integers a and b, we can find unique integers q and r satisfying the relation  

a=bq+r,0≤r≤b

If r=0 then q will be HCF of a and b

The basis of the Euclidean division algorithm is Euclid’s division lemma.  

To calculate the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm.  

HCF is the largest number which exactly divides two or more positive integers.  

By exactly we mean that on dividing both the integers a and b the remainder is zero.