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:

    ““In my youth,” said his father, “I took to the law,
    And argued each case with my wife;
    And the muscular strength, which it gave to my jaw,
    Has lasted the rest of my life.””
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    “The forward Youth that would appear
    Must now forsake his Muses dear,
    Nor in the Shadows sing
    His Numbers languishing.”
    —Andrew Marvell (1621–1678)