Question

prove that , G.C.D(a,b)=ax+by​

Answer 1

Step-by-step explanation:

Theorem: Let a, b be integers, not both zero, and let d be the smallest positive element of S = {ax + by : x, y ∈ IN}

. Then, gcd(a, b) = d.

Proof: S contains a positive integer because |a| ∈ S. By definition, there exist x, y such that d = ax + by.