To simulate Euclid's algorithm for GCDpa, bq, you only need to show the remainder sequence of pa, bq defined as pa0, a1, a2, . . . , ah, ah1 0q, h 1 where pa0, a1q pa, bq and ai1 pai1 mod aiq for i 1. If a particlar step is not obvious, just do a side computation to justify it. The subscript h in this sequence is denoted by hpa, bq, representing the number of remainder steps needed to reach ah1 0. Call hpa, bq the length of the remainder sequence. To simulate the Extended Euclid's Algorithm, you produce the extended remainder sequence: this is the sequence of triples pa, s, tqi : pai , si , tiq, i 0, 1, . . . , h, h