L'algorisme d'Euclides ampliat o algorisme d'Euclides estès és una millora de l'algorisme d'Euclides de càlcul del màxim comú divisor de dos nombres enters, que dona, a més del màxim comú divisor dels dos nombres, els coeficients de cadascun d'aquests dos nombres a la identitat de Bézout.
Siguin
i
dos nombres enters. L'algorisme d'Euclides consisteix a construir la recurrència finita
en la qual
no és més que el residu de la divisió entera de
i
amb quocient
. La successió és estrictament decreixent i la condició
obliga a que sigui finita. L'últim terme, posem
arriba quan hi ha
que fa
. La successió té, doncs,
termes i
.
Però si ara considerem aquestes altres dues recurrències finites:
amb els valors
de la successió de l'algorisme d'Euclides, resulta que, per
amb
, es té
com es comprova fàcilment per inducció.
Per tant, si
, resulta
i
i
, amb els signes adequats, són els coeficients de
i
a la identitat de Bézout.
Hom sol disposar els càlculs en una graella com aquesta
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle x_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/766d09a498699be10e276ad49145c921f8cbe335) |
![{\displaystyle x_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb828766e82e496666b179ff70d8e2fd24a79e5f) |
![{\displaystyle x_{5}\ldots \ldots x_{i-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8672c14ecde492cfa3b89f1683312b85b90496b) |
![{\displaystyle x_{i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db345bb67bd140474742faf5d2fff314daa04e33) |
![{\displaystyle x_{i}\ldots \ldots x_{k-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6d38c75a7bc5077e9985100b98204224d4cb7d0) |
![{\displaystyle x_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c60c4443107198983b1ced988c34b238bcd9119) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle y_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e73a90104a9b6484a6bc2df35edf469d6307b2c) |
![{\displaystyle y_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6859e9003d906e626edc77215dd6a9a896fa3b1e) |
![{\displaystyle y_{5}\ldots \ldots y_{i-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/129b278798a523daa74c923cd6ced3c1a72224e1) |
![{\displaystyle y_{i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30560d7871c030b94039f0af89bd27355d04133d) |
![{\displaystyle y_{i}\ldots \ldots y_{k-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f892425af1dd57e66de71546e027c51cc13da8e) |
![{\displaystyle y_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84cdc83a28249794a7c4152186059b6ba953455d) |
|
|
![{\displaystyle q_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c188711ffce607c8dd7504a6dcb52196e8b670b8) |
![{\displaystyle q_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4f2342d73d7213eb9c47db62f7ec31172d5cc43) |
![{\displaystyle q_{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25471063d32952bd8270997edc0d0f8acb6302fd) |
![{\displaystyle q_{6}\ldots \ldots q_{i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/483fda6af584dfb61baec69ab77f5535e2472162) |
![{\displaystyle q_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2752dcbff884354069fe332b8e51eb0a70a531b6) |
![{\displaystyle q_{i+1}\ldots \ldots q_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b771c9febb17c9f95be5b0193a30144c66956b8) |
![{\displaystyle q_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f27215e46abcad60f100434d2c8003310580af95) |
|
![{\displaystyle |a|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b61d5baa05004815f3abc52f517ce62b609b9b6) |
![{\displaystyle |b|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/881f49e94388a46a05d329251551ce20baf4f05d) |
![{\displaystyle d_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f051bd12b5413014eeb4944816cb5672edfcff4) |
![{\displaystyle d_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d43e86e828c6871d10a70e4c86a6cea2415991f0) |
![{\displaystyle d_{5}\ldots \ldots d_{i-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a84b810558bd7b5f4927271c1d73396d340b12f6) |
![{\displaystyle d_{i-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/424e21ab0f8c7faca2ba795eb3ad7c4f2247a98d) |
![{\displaystyle d_{i}\ldots \ldots d_{k-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b021b46768150587235e5a42553a417ab1ffca3) |
![{\displaystyle d_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74e726983141293b94078583acbb7440815a4c8b) |
![{\displaystyle d_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b78f5b2abc48e63b987b6d7527caa5aa9b1bb512) |
|
Hom comença obtenint
com a quocient de la divisió entera de
entre
, és a dir,
entre
i
a partir de
. Els termes
i
resulten de
i
. Els termes següents,
,
,
i
s'obtenen de la mateixa manera i en el mateix ordre:
i el procés acaba quan trobem
. Aleshores,
Il·lustrem aquest procés amb un exemple: es tracta de calcular
:
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle -2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46e5b5b462e546b1d3d7e5f9a23efece405b2e78) |
![{\displaystyle 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/991e33c6e207b12546f15bdfee8b5726eafbbb2f) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle -4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/addc8519724f81b43a6883c5eb2c996f9fc2996f) |
![{\displaystyle 9}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32d3d1e1f9dfe0254c628379e69a69711fe4eabd) |
![{\displaystyle -13}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4535a0d4479ed2ed4228d61fa0633637c525aa98) |
|
|
![{\displaystyle 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42) |
![{\displaystyle 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/991e33c6e207b12546f15bdfee8b5726eafbbb2f) |
![{\displaystyle 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f) |
|
![{\displaystyle 763}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cad4e3be79853e06aeba4a84b2ce2b2dd12b4b18) |
![{\displaystyle 175}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7406be7cecdb8fcffff521808ed2707bebda98e) |
![{\displaystyle 63}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5e687091bb4983ba6ce8cdf908d778baeffbcba) |
![{\displaystyle 49}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e854adb3d39762b45aea9e0b4df5188127c7a74) |
![{\displaystyle 14}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0599c6d5e184865910f777d74957032713eed57e) |
![{\displaystyle 7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee716ec61382a6b795092c0edd859d12e64cbba8) |
|
que prové de
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1=1-4\cdot 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d5395bf67e94fef965f4c8803f99d993d0250bc) |
![{\displaystyle -2=0-2\cdot 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfec994fe43dffe5f0ba0e811375ad170b163f0b) |
![{\displaystyle 3=1-1\cdot (-2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e660645503fbd1b5267140587488b20ddc6d483f) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle -4=0-4\cdot 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b02e4faaff1227f07bdd491bcd8c4062a4cf6e57) |
![{\displaystyle 9=1-2\cdot (-4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/beb116359a7230c5cc47762d92a8e705de4823c4) |
![{\displaystyle -13=-4-1\cdot 9}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4de7e35c2a241722e62314bc1737ebcab3fdcd4) |
|
|
![{\displaystyle 4=763\div 175}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6603f9e58133da0ce19212ade0043712c95f5ae7) |
![{\displaystyle 2=175\div 63}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d894d92f7066ea3b6b4405cdffc771d4ad1409e7) |
![{\displaystyle 1=63\div 49}](https://wikimedia.org/api/rest_v1/media/math/render/svg/061ece6c318f63168f58e7367c6d9102a10b16aa) |
![{\displaystyle 3=49\div 14}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5673b238468dd90330b6f405fc432f1c9edc65c6) |
![{\displaystyle 2=14\div 7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efa78e658d9b9553f0326617e9496dfec6bc570d) |
|
![{\displaystyle 763}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cad4e3be79853e06aeba4a84b2ce2b2dd12b4b18) |
![{\displaystyle 175}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7406be7cecdb8fcffff521808ed2707bebda98e) |
![{\displaystyle 63=763-175\cdot 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d880ffb133c5ded96c2c6af653d920ea398cdd36) |
![{\displaystyle 49=175-63\cdot 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c193d021d683d1d89574bce0716270c462592d2) |
![{\displaystyle 14=63-1\cdot 49}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d56a978855a033d8a7646565fdbf91133651aadf) |
![{\displaystyle 7=49-3\cdot 14}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04e92a813a422912a9334a3f6e583587b1b70a4e) |
|
(Les divisions
se sobreentenen enteres) Aleshores,
.