Покажем, что никакие 2 числа из не могут давать одинаковые остатки от деления на n.
Пусть не так, и .
Но тогда их разность делится на n. Отсюда следует, с учетом взаимной простоты n и d, что делится на n. Но, нетрудно заметить, - противоречие.
Значит, числа дают различные остатки при делении на n. Но этих чисел ровно n - значит, среди них обязательно найдется число, дающее остаток 0 при делении на n. Противоречие с тем, что числа взаимно простые с n.
Это и означает, что числа n и d не взаимно простые.
45 работников надо нанять
Пошаговое объяснение:
Проработав 2 дня, 15 работников выполнили 2/10 работы.
Осталось выполнить 8/10 работы.
Запишем изменяемых 3 параметра для наглядности:
8/10 работы -> 15 работников -> 8 дней
Следовательно, при удвоении работников дело пойдёт в 2 раза быстрее:
8/10 работы -> 30 работников -> 4 дня
Удвоим их снова, пусть работают:
8/10 работы -> 60 работников -> 2 дня
Значит, надо 60 работников. 15 уже есть, осталось пригласить
60 - 15 = 45 работников.
Пусть не так, и и числа n и d взаимно простые.
Покажем, что никакие 2 числа из
не могут давать одинаковые остатки от деления на n.
Пусть не так, и
.
Но тогда их разность
делится на n. Отсюда следует, с учетом взаимной простоты n и d, что 
делится на n. Но, нетрудно заметить, 
- противоречие.
Значит, числа
дают различные остатки при делении на n. Но этих чисел ровно n - значит, среди них обязательно найдется число, дающее остаток 0 при делении на n. Противоречие с тем, что числа 
взаимно простые с n.
Это и означает, что числа n и d не взаимно простые.
Ч.т.д.