# Extended Euclidean algorithm (Python)

Other implementations: C++ | Python

This article describes a Python implementation of Extended Euclidean algorithm.

## Algorithm

For u and v, this algorithm finds (u1,u2,u3) such that uu1 + vu2 = u3 = gcd(u,v). We use auxiliary vectors (v1,v2,v3) and (t1,t2,t3) in the algorithm. The following equations always hold throughout the algorithm.

ut1 + vt2 = t3
uu1 + uu2 = u3
uv1 + uv2 = v3
1. (Initialization): ,
2. If v3 = 0, stop.
3. Otherwise, do the following.
• (t1,t2,t3) = (u1,u2,u3) − (v1,v2,v3) * q
• and

## Source

The algorithm is quite straightforward and it is not difficult to translate the algorithm into a Python source code.

```<<eea>>=
def eea(u, v):
u1 = 1
u2 = 0
u3 = u
v1 = 0
v2 = 1
v3 = v
while v3 != 0:
q = u3 / v3
t1 = u1 - q * v1
t2 = u2 - q * v2
t3 = u3 - q * v3
u1 = v1
u2 = v2
u3 = v3
v1 = t1
v2 = t2
v3 = t3
return u1, u2, u3
```

The test driver is also given.

```<<eea.py>>=
eea
if __name__ == "__main__":
a, b, d = eea(352, 168)
print a, b, d
a, b, d = eea(168, 352)
print a, b, d
a, b, d = eea(3458, 4864)
print a, b, d
```

## Execution result

```crypto@crypto ~/python
\$ python eea.py
-10 21 8
21 -10 8
-45 32 38
```
• The first test case shows that -10 *352 + 21 * 168 = 8 and 8 is gcd(352, 168).
• The second result means that the order of input numbers has no significant meaning.
• The last result shows that -45 * 3458 + 32 * 4864 = 38 and 38 is gcd(3458, 4864).