Алгоритм Евклида

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

Вопрос задачи сведен к вопросу о том, какие числа могут быть представлены в виде Очевидно, что и взаимно просты, поэтому имеется пара такая, что Умножим это равенство на и получим Следовательно, все числа от до рано или поздно получатся, значит, отметины будут во всех отмеченных точках, и количество частей, на которые разделится колесо, равно