Question

write Euclid algorithm

Answer 1

Let a=bq+r, then find a number u which divides both a and b (so that a=su and b=tu), then u also divides r since

r=a-bq=su-qtu=(s-qt)u.
(1)
Similarly, find a number v which divides b and r (so that b=s^'v and r=t^'v), then v divides a since

a=bq+r=s^'vq+t^'v=(s^'q+t^')v.
(2)
Therefore, every common divisor of a and b is a common divisor of b and r, so the procedure can be iterated as follows:

q_1=|_a/b_| a=bq_1+r_1 r_1=a-bq_1 ; q_2=|_b/(r_1)_| b=q_2r_1+r_2 r_2=b-q_2r_1 ; q_3=|_(r_1)/(r_2)_| r_1=q_3r_2+r_3 r_3=r_1-q_3r_2 ; q_4=|_(r_2)/(r_3)_| r_2=q_4r_3+r_4 r_4=r_2-q_4r_3 ; q_n=|_(r_(n-2))/(r_(n-1))_| r_(n-2)=q_nr_(n-1)+r_n r_n=r_(n-2) ; -q_nr_(n-1); q_(n+1)=|_(r_(n-1))/(r_n)_| r_(n-1)=q_(n+1)r_n+0 r_n=r_(n-1)/q_(n+1)

Answer 2

Euclid division algorithm is also known as lemma and states that dividend is equal to divisor into questiont plus remainder