# Extended Euclidean algorithm (Python)

### From LiteratePrograms

**Other implementations**: C++ |**Python**

This article describes a Python implementation of Extended Euclidean algorithm.

## Algorithm

For *u* and *v*, this algorithm finds (*u*_{1},*u*_{2},*u*_{3}) such that *u**u*_{1} + *v**u*_{2} = *u*_{3} = gcd(*u*,*v*). We use auxiliary vectors (*v*_{1},*v*_{2},*v*_{3}) and (*t*_{1},*t*_{2},*t*_{3}) in the algorithm. The following equations always hold throughout the algorithm.

*u**t*_{1}+*v**t*_{2}=*t*_{3}*u**u*_{1}+*u**u*_{2}=*u*_{3}*u**v*_{1}+*u**v*_{2}=*v*_{3}

- (Initialization): ,
- If
*v*_{3}= 0, stop. - Otherwise, do the following.
- (
*t*_{1},*t*_{2},*t*_{3}) = (*u*_{1},*u*_{2},*u*_{3}) − (*v*_{1},*v*_{2},*v*_{3}) **q* - and
- return to 2.

## Source

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

<<eea>>=defeea(u, v): u1 = 1 u2 = 0 u3 = u v1 = 0 v2 = 1 v3 = vwhilev3 != 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 = t3returnu1, u2, u3

The test driver is also given.

<<eea.py>>=eeaif__name__ == "__main__": a, b, d = eea(352, 168)

## 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).

Download code |