Extended Euclidean Algorithm

Input: integers , with
Initialize: a table with 6 columns so that

• The columns are labeled , , (which we will call , EA, ,
• The first row of the table is (1, 0, a, -, - (technically 0), - (technically ))
• The second row is (0, 1, b, , , )

Repeat: For :

• , and
• (Although this should be done through the EA cell)

Stop: When
Output: Set and , and are a certificate of correctness

Note that this is better illustrated with examples

Find , , , and such that and

Conclusion
We determine that . The certificate of correctness is and . We can then check:

For , we simply chose and , and we check:

For row 2, observe: we plug in and , so
For row 2, observe: ,
For row 3, observe:
For row 3, observe: , so and

Input: Integers , wth
initialize: A table with four columns so that

• The columns are labelled , , , and
• The first row in the table is (, , , )
• The second row in the table is (, , , )

Repeat: For

Stop: when
Output: Set . Then , and , and are a certificate of correctness

Let

1. Apply EEA to compute and give a certificate of correctness for
2. Determine and give a certificate of correctness for

1.

From the table constructed above, we determine that , and . The certificate of correctness is and , and indeed we check that

2.
We have . Our certificate of correctness is and