从第二行开始到最后一行，我们可以用各个等式逐个消去中间余数。在这个例子中，先利用倒数第二个等式，然后是它上面的那个，我们得到：
18=162-2×72=162-2×(396-2×162)
=5×162-2×396。
最后我们再用第一个等式，把第一个中间余数162也消去：
5×162-2×396=5×(558-396)-2×396
=5×558-7×396=18。
无论是对于实践还是理论，可以倒过来执行这一程序都是很重要的。特别是在解密里，为了找出爱丽丝的解密数d，我们想要d满足de除以φ(n)余1的条件。为了简洁，我们用一个单独的符号k来代表φ(n)。 现在就可以看出我们坚持要e和k互素的原因了。因为如果它们的最大公因数是1，当我们对e和k执行欧几里得算法时，最终出现的余数自然是1。倒过来执行这一算法，我们就能最终把1表示成e和k的组合。特别地，我们会找到整数c和d，它们满足ck＋de=1，或者换句话说de=1-ck。因此de除以k会余1。
