So . In general, to find :

with | ||||

with | ||||

with | ||||

with | ||||

with | ||||

This process must terminate as . Using Lemma (2.21), . So is the last non-zero remainder in this process. We now wish to find and with . We can do this by backsubstitution.

This works in general but can be confusing and wasteful. These numbers can be calculated at the same time as if we know we shall need them. We introduce and . We put and . We iteratively define

Now consider .

, using the definition of and . |

- and ,
- if and then .