Het uitgebreide algoritme van Euclides is een uitbreiding van het algoritme van Euclides, dat niet alleen de grootste gemene deler ggd van twee natuurlijke getallen
en
bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele
en
:

De uitbreiding bestaat daarin dat behalve de berekening van de
van de getallen
en
met het algoritme van Euclides, ook de
wordt uitgedrukt als gehele lineaire combinatie van
en
. Het bewijs van de stelling van Bachet-Bézout steunt op de constructie door het algoritme.
Een veelgebruikte toepassing is het RSA-algoritme, meestal afgekort tot RSA, in de encryptie. Het is daarin op een gegeven moment nodig de geheime sleutel
te berekenen als modulaire inverse van de publieke sleutel
, dat wil zeggen dat
door
,
wordt gegeven voor zeker natuurlijk getal
. Deze geheime sleutel kan met het algoritme van Euclides worden berekend. Om dit te laten zien aan de hand van het voorbeeld van een ontbinding van Bézout, merken we op dat in RSA
en
geen gemeenschappelijke delers hebben. Het is een voorwaarde voor het bestaan van een geheime sleutel, dat
en
onderling ondeelbaar zijn.
Neem het voorbeeld met de getallen 1140 en 900. Bepaal eerst
met behulp van het algoritme van Euclides. Schrijf de deling van
als
en de rest als
, bijvoorbeeld
en
. Dan:

Dus
. Schrijf nu de
als lineaire combinatie van 1140 en 900. Bereken daartoe de
in omgekeerde volgorde:

Daarmee is
geschreven als gehele lineaire combinatie van 1140 en 900. Deze tweede stap wordt de ontbinding van Bézout genoemd.
Als de getallen in de
door 60 worden gedeeld resulteert dit in:

Neem nu het voorbeeld dat de publieke sleutel
= 15 en
= 19, deze getallen hebben inderdaad geen gemeenschappelijke deler. De geheime sleutel
wordt bepaald door
.
Reduceer
de termen in de bovenstaande ontbinding van
en gebruik
dus
.
Hieruit volgt dat
de inverse van 15 is
. Als er een geheime sleutel tussen 1 en 19 wordt gezocht, kan het worden gebruikt dat
.