Пусть заданы два числа $%a < b$%. Дан алгоритм:

1) Прибавляем к 1 число $%a$% до тех пор, пока "находимся" в сегменте $%[1;a+b]$%;

2) Отнимаем число $%b$% до тех пор, пока "находимся" в сегменте $%[1;a+b]$%;

Продолжаем до тех пор, пока получаем новые числа.

Пример:

$%a = 5; b = 7$%

Последовательность чисел по алгоритму следующая:

1 6 11 4 9 2 7 12 5 10 3 8

Требуется доказать, что получим $%1, 1+НОД(a,b), 1+2 \cdot НОД(a,b), \dots$%

задан 18 Май '17 18:12

10|600 символов нужно символов осталось
1

Для удобства вычтем по единице из каждого числа, то есть будем считать, что мы начинаем с нуля, а числа могут принимать значения от 0 до a+b-1 включительно. Также разделим оба числа на их НОД, сводя задачу к случаю двух взаимно простых чисел. Требуется показать, что все a+b значений появятся в ходе описанного процесса.

Ввиду конечности числа значений, среди них возникают повторения. Рассмотрим первый момент, когда некоторое значение первый раз повторилось. За это время мы k раз прибавили a и m раз вычли b. Получается ka=mb, так как мы вернулись назад. Ввиду взаимной простоты, k делится на b, и m делится на a. В частности, k+m>=a+b. Мы делали ровно k+m переходов, и различных чисел у нас k+m. Больше, чем a+b, их быть не может. Значит, их ровно a+b, и все значения присутствуют.

ссылка

отвечен 18 Май '17 18:40

А как мы перейдём обратно к исходным числам и получим все числа 1, 1+НОД(a,b) ...

(18 Май '17 19:16) PaCman

@PaCman: если все a+b чисел встретились, то их расположим по возрастанию. Здесь сама мысль в том, что встретятся все числа, и ничего не будет пропущено. Для случая взаимно простых, если начать с нуля, встретятся 0,1,2,...,a+b-1 в каком-то порядке, что и было доказано. После домножения на d=НОД(a,b) получатся 0,d,2d, ... , а потом прибавляется 1.

(18 Май '17 19:21) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879

задан
18 Май '17 18:12

показан
346 раз

обновлен
18 Май '17 19:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru