Условие
Натуральные числа p и q взаимно просты. Отрезок [0, 1] разбит на p + q одинаковых отрезков.
Докажите, что в каждом из этих отрезков, кроме двух крайних лежит ровно одно из p + q – 2 чисел 1/p, 2/p, ..., p–1/p, 1/q, 2/q, ..., q–1/q.
Решение
В силу взаимной простоты p и q указанные p + q – 2 числа попарно различны (кроме того, они отличаются и от чисел вида k/p+q). Поэтому они делят отрезок
[0, 1] на p + q – 1 отрезок. Достаточно доказать что внутри каждого из этих отрезков есть точка вида k/p+q.
На отрезке вида [m/p, m+1/p] такая точка, очевидно, есть, поскольку его длина больше 1/p+q. Расмотрим отрезок вида [m/p, n/q]. Он содержит точку m+n/p+q, поскольку неравенства m/p < m+n/p+q < n/q эквивалентны неравенству mq < np, то есть неравенству m/p < n/q. Аналогично рассматриваются отрезки вида [a/q, b/p].
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Алфутова Н.Б., Устинов А.В. |
|
Год издания |
2002 |
|
Название |
Алгебра и теория чисел |
|
Издательство |
МЦНМО |
|
Издание |
1 |
|
глава |
|
Номер |
3 |
|
Название |
Алгоритм Евклида и основная теорема арифметики |
|
Тема |
Алгебра и арифметика |
|
параграф |
|
Номер |
2 |
|
Название |
Алгоритм Евклида |
|
Тема |
Алгоритм Евклида |
|
задача |
|
Номер |
03.033 |
