Алгоритм Евклида
Ошибка.
Попробуйте повторить позже
Колесо длины 
в обод которого вбит гвоздь, достаточно долго едет по колесу длины 
На сколько частей поделят большее колесо
отметины от гвоздя?
Подсказка 1
Разделим колесо длиной 102 на 102 равных части (длиной 1 по окружности) и каждой точке деления поставим в соответствие число от 0 до 101. Можно полагать, что первая отметина гвоздя находится в точке 0. Также сразу ясно, что все отметины гвоздя могут попасть только в отмеченные точки. А как узнать, в какой точке появится отметина после x полных оборотов колеса длиной 19?
Подсказка 2
Верно! Можно заметить, что отметина появятся в точке, равной остатку от деления числа 19x на 102. Перепишем это утверждение по определению остатку 19x = 102y + r. Осталось узнать, какие r могут получиться! Как это сделать?
Подсказка 3
Точно! Давайте представим уравнение в виде 19x + 102y = r (переобозначим и вместо -y напишем y). Можно заметить, что 19 и 102 взаимно просты. Что можно сказать о решениях этого диофантового уравнения?
Подсказка 4
Конечно! По теореме о линейном представлении НОД найдутся такие числа a и b, что 19a + 102b = 1. А можно ли теперь узнать, какие r можно представить в виде 19x + 102y = 1?
Количество частей равно количеству отметин. Вычислим число отметин. Выберем первую точку на колесе длины 
на которой
появилась отметина, и обозначим ее 
От этой точки против часовой стрелки отметим последовательно точки 
так, чтобы
расстояние по окружности между соседними точками было равно 
Таким образом, мы разбили колесо длины 
на 
равные
части. Заметим, что отметины гвоздя могут появляться только в отмеченных точках, так как первая отметина появилась в
точке 
и длина у меньшего колеса целая. Каждая точка, в которой появится отметина гвоздя, может быть вычислена,
как остаток от деления 
на 
где 
— количество полных оборотов, совершенных от первого попадания в точку
колесом длины 
к данному моменту. Таким образом, из деления с остатком получаем 
где 
—
остаток.
Вопрос задачи сведен к вопросу о том, какие числа 
могут быть представлены в виде 
Очевидно, что 
и 
взаимно просты, поэтому имеется пара 
такая, что 
Умножим это равенство на 
и получим
Следовательно, все числа от 
до 
рано или поздно получатся, значит, отметины будут во всех отмеченных
точках, и количество частей, на которые разделится колесо, равно 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
