---
tag: 0964YQFSA8
kind: concept
name: Extended Euclidean algorithm
msc: [11A05]
sources:
  - url: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    locator: Description
same_as:
  wikidata: Q1362750
  wikipedia: Extended Euclidean algorithm
---

## Summary

The extended Euclidean algorithm computes the [[greatest common divisor|02WF878BH1]] $d$ of two integers $a$ and $b$, and also integers $x$ and $y$ such that $a x + b y = d$.
It does the steps of the [[Euclidean algorithm|0TRNT4X7J0]].
At each step, it writes the new remainder as an integer combination of $a$ and $b$.

## Remarks

The coefficients $x$ and $y$ prove [[Bézout's identity|0DQVHMYAGA]] for $a$ and $b$.
When $\gcd(a, n) = 1$, the coefficient $x$ of $a$ is a [[modular multiplicative inverse|00GXTQMY8Z]] of $a$ modulo $n$.

## Explanations

### L1 human

For $a = 48$ and $b = 18$, the Euclidean algorithm gives $12 = 48 - 2 \cdot 18$ and $6 = 18 - 1 \cdot 12$.
Put the first equation into the second: $6 = 18 - (48 - 2 \cdot 18) = 3 \cdot 18 - 1 \cdot 48$.
So $x = -1$ and $y = 3$ give $48 x + 18 y = 6$.