Question

b) State and prove Euclidean theorem.​

Answer 1

Explanation:

Proof. The Euclidean Algorithm proceeds by finding a sequence of remainders, r1, r2, r3, and so on, until one of them is the gcd. We prove by induction that each ri is a linear combination of a and b. ... The repeated step in the Euclidean Algorithm defines rn+2 so that rn=qrn+1+rn+2, or rn+2=rn−qrn+1.