Назовём беспосадочный перелёт из одного города в другой коротким маршрутом, а перелёт из одного города в другой с одной пересадкой в пути длинным маршрутом. Перенумеруем города и обозначим через число рейсов, выходящих из -го города.

Будем учитывать короткие маршруты в их конечных пунктах, а длинные — в пунктах пересадки. Тогда, если из города выходит авиалиний, то в нём будет учтено коротких маршрутов и длинных (так как из каждого смежного города через данный проходит длинных маршрутов), а всего — маршрутов. Таким образом, общее число маршрутов равно

Поскольку в любой степени при делении на дает остаток то остаток от деления на у общего числа маршрутов такой же, как у числа то есть а у числа этот остаток равен