Кстати, можно делить не только с недостатком, но и с избытком.
Как в непрерывных дробях - можно брать не остатки, а абсолютно наименьшие вычеты. Это несколько ускоряет процесс, но по сути ничего не меняет.
Единица получится потому, что на каждом шаге минимальный коэффициент строго уменьшается.
То есть продолжаем процесс до единицы и получаем полную систему

уравнений с

неизвестными. Тогда всё понятно кроме одного: почему определитель системы

должен быть

, и не придется ли в противном случае решать сравнение по

чтобы получить целые решения? Вопрос не праздный. Можно ведь и сразу заняться сравнением (как в примере выше), не решая никаких систем.
p.s. Я к тому, что последняя переменная (с единицей) может оказаться уже не из

-ов. Но даже если из

-ов, получим полную систему

уравнений.
(Оффтоп)
Надо же, влез не в свою тему....