Extended Euclidean Algorithm - The Case of More Than Two Numbers

The Case of More Than Two Numbers

One can handle the case of more than two numbers iteratively. First we show that . To prove this let . By definition of gcd is a divisor of and . Thus for some . Similarly is a divisor of so for some . Let . By our construction of, but since is the greatest divisor is a unit. And since the result is proven.

So if then there are and such that so the final equation will be

So then to apply to n numbers we use induction

with the equations following directly.

Read more about this topic:  Extended Euclidean Algorithm

Famous quotes containing the words case and/or numbers:

    “My case is thrown exclusively upon the independent voters of this county, and if elected they will have conferred a favor upon me, for which I shall be unremitting in my labors to compensate.”
    —Abraham Lincoln (1809–1865)

    “Think of the earth as a living organism that is being attacked by billions of bacteria whose numbers double every forty years. Either the host dies, or the virus dies, or both die.”
    —Gore Vidal (b. 1925)