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 the case, case and/or numbers:

    To be President of the United States, sir, is to act as advocate for a blind, venomous, and ungrateful client; still, one must make the best of the case, for the purposes of Providence.
    John Updike (b. 1932)

    God ... created a number of possibilities in case some of his prototypes failed—that is the meaning of evolution.
    Graham Greene (1904–1991)

    All experience teaches that, whenever there is a great national establishment, employing large numbers of officials, the public must be reconciled to support many incompetent men; for such is the favoritism and nepotism always prevailing in the purlieus of these establishments, that some incompetent persons are always admitted, to the exclusion of many of the worthy.
    Herman Melville (1819–1891)