Алгоритм решения уравнения ax+by = 1

1.Определим матрицу E:

E =	( 1 0 ) ( 0 1 )

2. Вычислим r - остаток от деления числа a на b, a=bq+r, 0 <= r < b.

3. Если r=0, то второй столбец матрицы E даёт вектор ( x, y ) решений уравнения.

4. Если r =/= 0, то заменим матрицу E матрицей

E *	( 0  1 ) ( 1 -q )

5. Заменим пару чисел (a,b) на (b,r) и перейдем к шагу 2.