Пример

Решим тождество

$65537·x ≡ 1 \pmod {9477888}$

$i$	$r_{i-2}$	$r_{i-1}$	$r_i$	$k_i$	$s_i$	$t_i$
0	—	—	65537	—	1	0
1	—	65537	9477888	—	0	1
2	65537	9477888	65537	2	1	0
3	9477888	65537	40560	144	-144	1
4	65537	40560	24977	1	145	-1
5	40560	24977	15583	1	-289	2
6	24977	15583	9394	1	434	-3
7	15583	9394	6189	1	-723	5
8	9394	6189	3205	1	1157	-8
9	6189	3205	2984	1	-1880	13
10	3205	2984	221	1	3037	-21
11	2984	221	111	13	-41361	286
12	221	111	110	1	44398	-307
13	111	110	1	1	-85759	593

$s = -85759$ , или

$s = -85759 + 9477888 = 9392129$

Проверяем:

$65537·9392129 = 615531958273$

$615531958273 ≡ 1 \pmod {9477888}$