Utvidet euklidisk algoritme - Extended Euclidean algorithm

I aritmetikk og dataprogrammering er den utvidede euklidiske algoritmen en utvidelse til den euklidiske algoritmen , og beregner, i tillegg til den største fellesdeleren (gcd) av heltall a og b , også koeffisientene til Bézouts identitet , som er heltall x og y slik at

${\ displaystyle ax+by = \ gcd (a, b).}$

Dette er en sertifiseringsalgoritme , fordi gcd er det eneste tallet som samtidig kan tilfredsstille denne ligningen og dele inngangene. Det lar en også beregne, med nesten ingen ekstra kostnad, kvotientene til a og b av deres største fellesdeler.

Utvidet euklidisk algoritme refererer også til en veldig lik algoritme for å beregne den polynomiske største fellesdeleren og koeffisientene for Bézouts identitet til to univariate polynomer .

Den utvidede euklidiske algoritmen er spesielt nyttig når a og b er coprime . Med denne bestemmelsen er x den modulære multiplikative inverse av en modulo b , og y er den modulære multiplikative inverse av b modulo a . På samme måte tillater den polynomiske utvidede euklidiske algoritmen en å beregne den multiplikative inverse i algebraiske feltutvidelser og spesielt i endelige felt av ikke -primær orden. Det følger at begge utvidede euklidiske algoritmer er mye brukt i kryptografi . Spesielt er beregningen av den modulære multiplikative inverse et vesentlig trinn i avledningen av nøkkelpar i RSA -krypteringsmetoden for offentlig nøkkel.

Beskrivelse

Den standard euklidiske algoritmen fortsetter med en rekke euklidiske divisjoner hvis kvoter ikke brukes. Bare resten beholdes. For den utvidede algoritmen brukes de påfølgende kvotientene. Nærmere bestemt består den standard euklidiske algoritmen med a og b som inngang i å beregne en sekvens av kvotienter og en sekvens av rester slik at ${\ displaystyle q_ {1}, \ ldots, q_ {k}}$${\ displaystyle r_ {0}, \ ldots, r_ {k+1}}$

${\ displaystyle {\ begynne {justert} r_ {0} & = a \\ r_ {1} & = b \\ & \, \, \, \ vdots \\ r_ {i+1} & = r_ {i- 1} -q_ {i} r_ {i} \ quad {\ text {og}} \ quad 0 \ leq r_ {i+1} <| r_ {i} | \ quad {\ text {(dette definerer}} q_ {i}) \\ & \, \, \, \ vdots \ end {align}}}$

Det er hovedegenskapen til den euklidiske inndelingen at ulikhetene til høyre definerer unikt og fra og${\ displaystyle q_ {i}}$${\ displaystyle r_ {i+1}}$${\ displaystyle r_ {i-1}}$${\ displaystyle r_ {i}.}$

Beregningen stopper når man når en rest som er null; den største fellesdeleren er da den siste ikke -null resten${\ displaystyle r_ {k+1}}$${\ displaystyle r_ {k}.}$

Den utvidede euklidiske algoritmen fortsetter på samme måte, men legger til to andre sekvenser, som følger

${\ displaystyle {\ begin {align} r_ {0} & = a & r_ {1} & = b \\ s_ {0} & = 1 & s_ {1} & = 0 \\ t_ {0} & = 0 & t_ {1} & = 1 \\ & \, \, \, \ vdots && \, \, \, \ vdots \\ r_ {i+1} & = r_ {i-1} -q_ {i} r_ {i} & {\ tekst {og}} 0 & \ leq r_ {i+1} <| r_ {i} | & {\ text {(dette definerer}} q_ {i} {\ tekst {)}} \\ s_ {i+1} & = s_ {i-1} -q_ {i} s_ {i} \\ t_ {i+1} & = t_ {i-1} -q_ {i} t_ {i} \\ & \, \, \ , \ vdots \ end {align}}}$

Beregningen stopper også når og gir ${\ displaystyle r_ {k+1} = 0}$

• ${\ displaystyle r_ {k}}$er den største fellesdeleren for input og${\ displaystyle a = r_ {0}}$${\ displaystyle b = r_ {1}.}$
• Bézout -koeffisientene er og det er${\ displaystyle s_ {k}}$${\ displaystyle t_ {k},}$${\ displaystyle \ gcd (a, b) = r_ {k} = as_ {k}+bt_ {k}}$
• Kvotientene til a og b av deres største fellesdeler er gitt av og${\ displaystyle s_ {k+1} = \ pm {\ frac {b} {\ gcd (a, b)}}}$${\ displaystyle t_ {k+1} = \ pm {\ frac {a} {\ gcd (a, b)}}}$

Videre, hvis a og b er begge positive og , da ${\ displaystyle \ gcd (a, b) \ neq \ min (a, b)}$

${\ displaystyle | s_ {i} | \ leq \ left \ lfloor {\ frac {b} {2 \ gcd (a, b)}} \ right \ rfloor \ quad {\ text {og}} \ quad | t_ { i} | \ leq \ left \ lfloor {\ frac {a} {2 \ gcd (a, b)}} \ right \ rfloor}$

for hvor betegner den integrerte delen av x , det er det største heltallet ikke større enn x . ${\ displaystyle 0 \ leq i \ leq k,}$${\ displaystyle \ lfloor x \ rfloor}$

Dette innebærer at paret av Bézouts koeffisienter levert av den utvidede euklidiske algoritmen er det minimale paret av Bézout -koeffisienter, som det unike paret som tilfredsstiller begge ulikhetene ovenfor.

Det betyr også at algoritmen kan utføres uten et heltallsoverløp av et dataprogram ved hjelp av heltall med en fast størrelse som er større enn a og b .

Eksempel

Tabellen nedenfor viser hvordan den utvidede euklidiske algoritmen fortsetter med input 240 og 46 . Den største fellesdeleren er den siste ikke -null oppføringen, 2 i kolonnen "resten". Beregningen stopper på rad 6, fordi resten i den er 0 . Bézout-koeffisienter vises i de to siste oppføringene i den nest siste raden. Faktisk er det lett å bekrefte at −9 × 240 + 47 × 46 = 2 . Til slutt er de to siste oppføringene 23 og -120 i den siste raden, opp til tegnet, kvotientene til inndata 46 og 240 med den største fellesdeleren 2 .

Bevis

Siden sekvensen til er en synkende sekvens av ikke -negative heltall (fra i = 2 på). Dermed må den stoppe med noen Dette beviser at algoritmen stopper til slutt. ${\ displaystyle 0 \ leq r_ {i+1} <| r_ {i} |,}$${\ displaystyle r_ {i}}$${\ displaystyle r_ {k+1} = 0.}$

Som den største fellesdeleren er den samme for og Dette viser at den største fellesdeleren for inngangen er den samme som for Dette viser at det er den største fellesdeleren for a og b . (Inntil dette punktet er beviset det samme som for den klassiske euklidiske algoritmen.) ${\ displaystyle r_ {i+1} = r_ {i-1} -r_ {i} q_ {i},}$${\ displaystyle (r_ {i-1}, r_ {i})}}$${\ displaystyle (r_ {i}, r_ {i+1}).}$${\ displaystyle a = r_ {0}, b = r_ {1}}$${\ displaystyle r_ {k}, r_ {k+1} = 0.}$${\ displaystyle r_ {k}}$

Som og vi har for i = 0 og 1. Forholdet følger ved induksjon for alle : ${\ displaystyle a = r_ {0}}$${\ displaystyle b = r_ {1},}$${\ displaystyle as_ {i}+bt_ {i} = r_ {i}}$${\ displaystyle i> 1}$

${\ displaystyle r_ {i+1} = r_ {i-1} -r_ {i} q_ {i} = (as_ {i-1}+bt_ {i-1})-(as_ {i}+bt_ { i}) q_ {i} = (as_ {i-1} -as_ {i} q_ {i})+(bt_ {i-1} -bt_ {i} q_ {i}) = as_ {i+1} +bt_ {i+1}.}$

Således og er Bézout -koeffisienter. ${\ displaystyle s_ {k}}$${\ displaystyle t_ {k}}$

Vurder matrisen

${\ displaystyle A_ {i} = {\ begin {pmatrix} s_ {i-1} & s_ {i} \\ t_ {i-1} & t_ {i} \ end {pmatrix}}.}$

Gjentagelsesforholdet kan skrives om i matriseform

${\ displaystyle A_ {i+1} = A_ {i} \ cdot {\ begin {pmatrix} 0 & 1 \\ 1 & -q_ {i} \ end {pmatrix}}.}$

Matrisen er identitetsmatrisen og dens determinant er en. Determinanten for matrisen til høyre i den foregående formelen er -1. Det følger at determinanten for er Spesielt, for vi har Ser på dette som en Bézouts identitet, dette viser det og er coprime . Forholdet som er bevist ovenfor og Euklids lemma viser at deler b og deler a . Ettersom de er coprime, er de, opp til deres tegn, kvotientene til b og a av deres største fellesdeler. ${\ displaystyle A_ {1}}$${\ displaystyle A_ {i}}$${\ displaystyle (-1)^{i-1}.}$${\ displaystyle i = k+1,}$${\ displaystyle s_ {k} t_ {k+1} -t_ {k} s_ {k+1} = (-1)^{k}.}$${\ displaystyle s_ {k+1}}$${\ displaystyle t_ {k+1}}$${\ displaystyle as_ {k+1}+bt_ {k+1} = 0}$${\ displaystyle s_ {k+1}}$${\ displaystyle t_ {k+1}}$

For å bevise den siste påstanden, antar du at a og b er både positive og . Deretter, og hvis , kan det sees at s- og t -sekvensene for ( a , b ) under EØS er opp til de første 0- og 1 -tallene, t- og s -sekvensene for ( b , a ). Definisjonene viser da at ( a , b ) saken reduseres til ( b , a ) saken. Så anta det uten tap av generalitet. ${\ displaystyle \ gcd (a, b) \ neq \ min (a, b)}$${\ displaystyle a \ neq b}$${\ displaystyle a <b}$${\ displaystyle a> b}$

Det kan sees at er 1 og (som eksisterer ved ) er et negativt heltall. Deretter er det alternative i tegn og streng økning i størrelse, som følger induktivt av definisjonene og det faktum at for , gjelder saken fordi . Det samme gjelder etter de første termene, av samme grunn. Videre er det lett å se det (når a og b er både positive og ). Og dermed, ${\ displaystyle s_ {2}}$${\ displaystyle s_ {3}}$${\ displaystyle \ gcd (a, b) \ neq \ min (a, b)}$${\ displaystyle s_ {i}}$${\ displaystyle q_ {i} \ geq 1}$${\ displaystyle 1 \ leq i \ leq k}$${\ displaystyle i = 1}$${\ displaystyle a> b}$${\ displaystyle t_ {i}}$${\ displaystyle q_ {k} \ geq 2}$${\ displaystyle \ gcd (a, b) \ neq \ min (a, b)}$

${\ displaystyle | s_ {k+1} | = \ left | {\ frac {b} {\ gcd (a, b)}} \ right | \ geq 2 | s_ {k} | \ qquad {\ text {og }} \ qquad | t_ {k+1} | = \ venstre | {\ frac {a} {\ gcd (a, b)}} \ høyre | \ geq 2 | t_ {k} |.}$

Dette, ledsaget av det faktum som er større enn eller lik i absolutt verdi enn noen tidligere eller henholdsvis fullførte bevis. ${\ displaystyle s_ {k}, t_ {k}}$${\ displaystyle s_ {i}}$${\ displaystyle t_ {i}}$

Polynom utvidet euklidisk algoritme

For univariate polynomer med koeffisienter i et felt fungerer alt på samme måte, euklidisk divisjon, Bézouts identitet og utvidet euklidisk algoritme. Den første forskjellen er at i den euklidiske divisjonen og algoritmen må ulikheten erstattes av en ulikhet i gradene. Ellers forblir alt som foregår i denne artikkelen det samme, ganske enkelt ved å erstatte heltall med polynom. ${\ displaystyle 0 \ leq r_ {i+1} <| r_ {i} |}$${\ displaystyle \ deg r_ {i+1} <\ deg r_ {i}.}$

En annen forskjell ligger i grensen for størrelsen på Bézout -koeffisientene levert av den utvidede euklidiske algoritmen, som er mer nøyaktig i polynomtilfellet, noe som fører til følgende teorem.

Hvis a og b er to ikke -null polynomer, produserer den utvidede euklidiske algoritmen det unike paret med polynomer ( s , t ) slik at

${\ displaystyle as+bt = \ gcd (a, b)}$

og

${\ displaystyle \ deg s <\ deg b- \ deg (\ gcd (a, b)), \ quad \ deg t <\ deg a- \ deg (\ gcd (a, b)).}$

En tredje forskjell er at i polynom -tilfellet er den største fellesdeleren definert bare opp til multiplikasjonen med en ikke -null konstant. Det er flere måter å definere utvetydig en største fellesdeler.

I matematikk er det vanlig å kreve at den største fellesdeleren er et monisk polynom . For å få dette, er det tilstrekkelig å dele hvert element i utgangen med den ledende koeffisienten til Dette tillater at hvis a og b er coprime, får man 1 på høyre side av Bézouts ulikhet. Ellers kan man få en hvilken som helst ikke-null konstant. I datamaskinalgebra har polynomene vanligvis heltallskoeffisienter, og denne måten å normalisere den største fellesdeleren innfører for mange fraksjoner for å være praktisk. ${\ displaystyle r_ {k}.}$

Den andre måten å normalisere den største fellesdeleren når det gjelder polynomer med heltallskoeffisienter, er å dele hver utgang med innholdet i for å få en primitiv største felles divisor. Hvis inngangspolynomene er coprime, gir denne normaliseringen også en største felles divisor lik 1. Ulempen med denne tilnærmingen er at mange fraksjoner skal beregnes og forenkles under beregningen. ${\ displaystyle r_ {k},}$

En tredje tilnærming består i å utvide algoritmen til subresultante pseudo-rest-sekvenser på en måte som ligner utvidelsen av den euklidiske algoritmen til den utvidede euklidiske algoritmen. Dette gjør at når du starter med polynom med heltallskoeffisienter, har alle polynomene som er beregnet heltallskoeffisienter. Videre er hver beregnet rest et subresultant polynom . Spesielt hvis inngangspolynomene er coprime, blir Bézouts identitet ${\ displaystyle r_ {i}}$

${\ displaystyle as+bt = \ operatorname {Res} (a, b),}$

hvor betegner resultatet av a og b . I denne formen for Bézouts identitet er det ingen nevner i formelen. Hvis man deler alt med den resulterende får man den klassiske Bézouts identitet, med en eksplisitt fellesnevner for de rasjonelle tallene som vises i den. ${\ displaystyle \ operatorname {Res} (a, b)}$

Pseudokode

For å implementere algoritmen som er beskrevet ovenfor, bør man først bemerke at bare de to siste verdiene til de indekserte variablene er nødvendig i hvert trinn. For å lagre minne må hver indekserte variabel derfor erstattes av bare to variabler.

For enkelhets skyld bruker følgende algoritme (og de andre algoritmene i denne artikkelen) parallelle oppgaver . I et programmeringsspråk som ikke har denne funksjonen, må parallelle oppgaver simuleres med en hjelpevariabel. For eksempel den første,

(old_r, r) := (r, old_r - quotient * r)

tilsvarer

prov := r;
r := old_r - quotient × prov;
old_r := prov;

og tilsvarende for de andre parallelle oppgavene. Dette fører til følgende kode:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

Kvotientene til a og b av deres største fellesdeler, som sendes ut, kan ha et feil tegn. Dette er lett å korrigere på slutten av beregningen, men har ikke blitt gjort her for å forenkle koden. På samme måte, hvis enten a eller b er null og den andre er negativ, er den største fellesdeleren som er utgang negativ, og alle tegnene på utgangen må endres.

Legg til slutt merke til at i Bézouts identitet, kan man løse for gitt . Således er en optimalisering til algoritmen ovenfor å bare beregne sekvensen (som gir Bézout -koeffisienten ), og deretter beregne på slutten: ${\ displaystyle ax+av = \ gcd (a, b)}$${\ displaystyle y}$${\ displaystyle a, b, x, \ gcd (a, b)}$${\ displaystyle s_ {k}}$${\ displaystyle x}$${\ displaystyle y}$

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

Imidlertid er dette i mange tilfeller egentlig ikke en optimalisering: mens den tidligere algoritmen ikke er utsatt for overløp når den brukes med maskintall (det vil si heltall med en fast øvre grense for sifre), multiplisering av old_s * a ved beregning av bezout_t kan flyte over, og begrense denne optimaliseringen til innganger som kan representeres på mindre enn halvparten av den maksimale størrelsen. Når du bruker heltall med ubegrenset størrelse, vokser tiden som trengs for multiplikasjon og divisjon kvadratisk med størrelsen på heltallene. Dette innebærer at "optimaliseringen" erstatter en sekvens av multiplikasjoner/divisjoner av små heltall med en enkelt multiplikasjon/divisjon, noe som krever mer beregningstid enn operasjonene den erstatter, samlet.

Forenkling av brøk

En brøkdel en/ber i kanonisk forenklet form hvis a og b er coprime og b er positiv. Denne kanoniske forenklede formen kan oppnås ved å erstatte de tre utgangslinjene i den foregående pseudokoden med

if s = 0 then output "Division by zero"
if s < 0 then s := −s;  t := −t   (for avoiding negative denominators)
if s = 1 then output -t        (for avoiding denominators equal to 1)
output -t/s

Beviset for denne algoritmen er avhengig av det faktum at s og t er to koprime -heltall, slik som + bt = 0 , og dermed . For å få den kanoniske forenklede formen er det nok å flytte minustegnet for å ha en positiv nevner. ${\ displaystyle {\ frac {a} {b}} =-{\ frac {t} {s}}}$

Hvis b deler a jevnt, utfører algoritmen bare en iterasjon, og vi har s = 1 på slutten av algoritmen. Det er det eneste tilfellet der utgangen er et heltall.

Beregning av multiplikative inverser i modulære strukturer

Den utvidede euklidiske algoritmen er det essensielle verktøyet for å beregne multiplikative inverser i modulære strukturer, vanligvis de modulære heltallene og de algebraiske feltutvidelsene . Et bemerkelsesverdig eksempel på sistnevnte tilfelle er de endelige feltene i ikke-primær orden.

Modulære heltall

Hvis n er et positivt heltall, kan ringen Z / n Z identifiseres med settet {0, 1, ..., n -1} av resten av den euklidiske divisjonen med n , addisjonen og multiplikasjonen består i å ta resten med n av resultatet av tillegg og multiplikasjon av heltall. Et element a av Z / n Z har en multiplikativ invers (det vil si at det er en enhet ) hvis det er kopi til n . Særlig hvis n er primtall , en har en multiplikativ invers hvis den ikke er null (modulo n ). Dermed er Z / n Z et felt hvis og bare hvis n er primtall.

Bézouts identitet hevder at a og n er coprime hvis og bare hvis det finnes heltall s og t slik at

${\ displaystyle ns+at = 1}$

Å redusere denne identiteten modulo n gir

${\ displaystyle at \ equiv 1 \ mod n.}$

Således er t , eller, mer nøyaktig, resten av divisjonen av t med n , multiplikativ invers av en modulo n .

For å tilpasse den utvidede euklidiske algoritmen til dette problemet, bør man bemerke at Bézout -koeffisienten til n ikke er nødvendig, og derfor ikke trenger å beregnes. For å få et resultat som er positivt og lavere enn n , kan man også bruke det faktum at heltallet t gitt av algoritmen tilfredsstiller | t | < n . Det vil si at hvis t <0 , må man legge n til det på slutten. Dette resulterer i pseudokoden, der inngangen n er et heltall større enn 1.

 function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Enkle algebraiske feltutvidelser

Den utvidede euklidiske algoritmen er også hovedverktøyet for å beregne multiplikative inverser i enkle algebraiske feltutvidelser . Et viktig tilfelle, mye brukt i kryptografi og kodingsteori , er det for endelige felt av ikke-primær orden. Faktisk, hvis p er et primtall, og q = p ^d , er rekkefølge q en enkel algebraisk forlengelse av primfeltet til p -elementer, generert av en rot av et ureduserbart polynom med grad d .

En enkel algebraisk forlengelse L av et felt K , generert av roten til et ureduserbart polynom p av grad d, kan identifiseres til kvoteringsringen , og dens elementer er i bijektiv korrespondanse med polynomene av grad mindre enn d . Tilsetningen i L er tillegg av polynom. Multiplikasjonen i L er resten av den euklidiske divisjonen med p av produktet av polynomer. For å fullføre aritmetikken i L gjenstår det bare å definere hvordan du skal beregne multiplikative inverser. Dette gjøres av den utvidede euklidiske algoritmen. ${\ displaystyle K [X]/\ langle p \ rangle,}$

Algoritmen er veldig lik den som er gitt ovenfor for å beregne den modulære multiplikative inverse. Det er to hovedforskjeller: for det første er den siste, men en linje ikke nødvendig, fordi Bézout -koeffisienten som gis alltid har en grad mindre enn d . For det andre kan den største fellesdeleren som er gitt, når inngangspolynomene er koprime, være alle ikke -nullelementer av K ; dette Bézout koeffisient (a polynom generelt positiv grad) må således multipliseres med den inverse av dette element av K . I pseudokoden som følger, er p et polynom med en grad større enn ett, og a er et polynom.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Eksempel

For eksempel, hvis polynomet som brukes til å definere det endelige feltet GF (2 ⁸ ) er p = x ⁸  +  x ⁴  +  x ³  +  x  + 1, og a = x ⁶  +  x ⁴  +  x  + 1 er elementet hvis inverse er ønsket, og deretter utfører algoritmeresultatene i beregningen beskrevet i tabellen nedenfor. La oss huske at i felt av rekkefølge 2 ⁿ har en - z = z og z + z = 0 for hvert element z i feltet). Siden 1 er det eneste nullelementet i GF (2), er det ikke nødvendig med justering i den siste linjen i pseudokoden.

Dermed er det inverse x ⁷  +  x ⁶  +  x ³  +  x , som kan bekreftes ved å multiplisere de to elementene sammen , og ta resten med p av resultatet.

Saken om mer enn to tall

Man kan håndtere saken med mer enn to tall iterativt. Først viser vi det . For å bevise dette la . Per definisjon av gcd er en deler av og . Slik for noen . Tilsvarende er en deler av det for noen . La . Ved vår konstruksjon av , men siden er den største deleren er en enhet . Og siden resultatet er bevist. ${\ displaystyle \ gcd (a, b, c) = \ gcd (\ gcd (a, b), c)}$${\ displaystyle d = \ gcd (a, b, c)}$${\ displaystyle d}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ gcd (a, b) = kd}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle c}$${\ displaystyle c = jd}$${\ displaystyle j}$${\ displaystyle u = \ gcd (k, j)}$${\ displaystyle u}$${\ displaystyle ud | a, b, c}$${\ displaystyle d}$${\ displaystyle u}$${\ displaystyle ud = \ gcd (\ gcd (a, b), c)}$

Så hvis så er det og slik at så den endelige ligningen vil være ${\ displaystyle na+mb = \ gcd (a, b)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x \ gcd (a, b)+yc = \ gcd (a, b, c)}$

${\ displaystyle x (na+mb)+yc = (xn) a+(xm) b+yc = \ gcd (a, b, c). \,}$

Så for å søke på n tall bruker vi induksjon

${\ displaystyle \ gcd (a_ {1}, a_ {2}, \ dots, a_ {n}) = \ gcd (a_ {1}, \, \ gcd (a_ {2}, \, \ gcd (a_ { 3}, \ dots, \ gcd (a_ {n-1} \ ,, a_ {n}))), \ dots),}$

med ligningene som følger direkte.

Se også

• Euklidisk domene
• Lineær kongruenssetning
• Kuṭṭaka

Referanser

• Knuth, Donald . The Computer of Computer Programming . Addison-Wesley. Bind 2, kapittel 4.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein . Introduksjon til algoritmer , andre utgave. MIT Press og McGraw-Hill, 2001. ISBN  0-262-03293-7 . Side 859–861 i seksjon 31.2: Største fellesdeler.

Eksterne linker

• Kilde for algoritmens form som brukes til å bestemme multiplikativ invers i GF (2^8)