Question

Describe the extended Euclidean algorithm using pseudocode.

Short answer

answer is not given in the file.

Step-by-step solution

Step: 1

Procedure extended Euclidean (a,b: positive integers)

$$\begin{gathered} x:=a \\ y:=b \\ oldolds:=1 \\ olds:=0 \\ oldoldt:=0 \\ oldt:=1 \end{gathered}$$

Step: 2

$$\begin{gathered} whiley\ne 0 \\ q:=xdivy \\ r:=xmody \\ x:=y \\ y:=r \\ s:=oldolds-qolds \\ t:=oldoldt-q.oldt \end{gathered}$$

Step: 3

$$\begin{gathered} oldolds:=olds \\ oldold:=oldt \\ olds:=s \\ old:=t \\ \{gcd(ab)\mathrm{is}x,and(oldolds)a+(oldoldt)b=x\} \end{gathered}$$