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:

    “Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
    —Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    “All ye poets of the age,
    All ye witlings of the stage,
    Learn your jingles to reform,
    Crop your numbers to conform.
    Let your little verses flow
    Gently, sweetly, row by row;
    Let the verse the subject fit,
    Little subject, little wit.
    Namby-Pamby is your guide,
    Albion’s joy, Hibernia’s pride.”
    —Henry Carey (1693?–1743)