Euclidean Algorithm - Number Theory #Euclidean #Algorithm #- #Number #Theory
Euclid Algorithm or Division Algorithm : Statement : Given integers a and b with b > 0 , there exists a unique pair of integers q and r such that a = bq + r , with 0 ≤ r < b. Moreover , r = 0 if, and only, if b/a. Proof : Suppose a and b are two integers with b > 0. Let S = { y / y= a - bx , x is an integer, y ≥ 0 } . Clearly S is a non - empty set of non - negative integers. ∴ By well- ordering Principle , S must have a smallest member , say a - bq for some integer q . Let r = a - bq. Hence r is the sm...