Близкие дроби

33

В этой заметке рассказано о некоторых любопытных последовательностях добей и решена задача M298 из «Задачника «Кванта». Хотя в конце отчителя требуется знакомство с методом координат, векторами и принципиом математической индукции, но больше часть заметки будет понятна даже тем, кто лишь недавно познакомился с добями. Автор надеется, что старшеклассники и учитель найдет здесь удобный материал для занятий с учениками 5—6 классов. Упражнения включают существующее состояние.

1. Ряды Фарея. Наблюдения

Выпишем все правиланые доби, у которых знаменатель не больше 7:

$$\frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{3}{4}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}, \frac{1}{6},$$

$$\frac{5}{6}, \frac{1}{7}, \frac{2}{7}, \frac{3}{7}, \frac{4}{7}, \frac{5}{7}, \frac{6}{7}$$

(мы пропустили сократимые доби: $\frac{2}{4}, \frac{2}{6}, \frac{3}{6}$ и $\frac{4}{6}$ — из добей, представляющих одно и то же число, мы выбираем одн и у добь, а именно ту, у которой числитель и знаменатель наименьшие).

Теперь запишем те же доби в порядке возрастания:

$$\frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2},$$

$$\frac{4}{7}, \frac{3}{5}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}.$$

(1)

Проверьте, что в ряду (1) каждая добь действительное больше предыдущей

$$\frac{1}{6} - \frac{1}{7} = \frac{1}{6.7}, \frac{1}{5} - \frac{1}{6} = \frac{1}{5.6},$$

$$\frac{1}{4} - \frac{1}{5} = \frac{1}{4.5}, \frac{2}{7} - \frac{1}{4} = \frac{1}{4.7}, \dots$$

При этом соблюдается интересная закономерность: числомель разности двух соседних добей всегда получается равным единице, точнее,

A. Для любых двух соседних добей $\frac{a}{b}, \frac{c}{d}$ ($2\delta e \frac{a}{b} < \frac{c}{d}$) выполняется равенство

$$bc - ad = 1.$$

Какие еще закономерности присущи ряду добей (1)?

Нетрудно обнаружить, что сумма двух добей, симметрично стоящих в этом ряду, равна 1. Интересно, затемил ли читатель, что

B. Каждый добь получается из соседних с ней двух добей следующим образом: надо сложить их числели и разделить полученное число на сумму знаменателя.

В самом деле,

$$\frac{1}{6} = \frac{1 + 1}{7 + 5}, \frac{1}{5} = \frac{1 + 1}{6 + 4},$$

$$\frac{1}{4} = \frac{1 + 2}{5 + 7}, \frac{2}{7} = \frac{1 + 1}{4 + 3}, \frac{1}{3} = \frac{2 + 2}{7 + 5},$$

$$\frac{2}{5} = \frac{1 + 3}{3 + 7}, \frac{3}{7} = \frac{2 + 1}{5 + 2}, \frac{1}{2} = \frac{3 + 4}{7 + 7}$$

и так далее!

34

Таблица 1. Ряды Фарея.

Точно так же, как выписана строка (1) из правилных дробей со значенателем, не превосходящим 7, можно выписать в порядке возрастания дроби со значенателем, не превосходящим $n$. Расположим подряд также строки для $n=1, 2, \dots, 7$ в виде таблицы 1.

Первая строка и боковые стены из дробей $\frac{0}{1}$ и $\frac{1}{1}$ придают нашей таблице более законченный вид.

Упражнение 1. Проверьте, что закономерности А и Б, которые мы заметили в следующей строке таблицы, имеют место и во всех предыдущих строках.

Новые дроби в каждой строке мы выделили красным цветом.

Для новых дробей наблюдайте Б можно уточнить: у дроби, возникающее между двумя старыми, числитель равен сумме их числитель, значенатель — сумме значенателей. Таким образом, можно предложить простое правило, по которым получается новая $n$-я строка.

В. Нужно отметить в $(n-1)$-й строке все такие пары седних дробей $\frac{a}{b}, \frac{c}{d}$, у которых сумма значенателя равна $n$, и между ними встречаются дроби $\frac{a+c}{b+d}$ (они всегда получаются несократными).

Проделаем эту операцию с следующим пары седним строкой. Отметим пары седним

них дробей, у которых сумма значенателем равна 8. Это такие пары

$\frac{0}{1}$ и $\frac{1}{7}$; $\frac{1}{3}$ и $\frac{2}{5}$; $\frac{3}{5}$ и $\frac{2}{3}$; $\frac{6}{7}$ и $\frac{1}{1}$.

Вставим между ними соответственно дроби $\frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}$ и получим восмную строчку

$$\frac{0}{1} \frac{1}{8} \frac{1}{7} \frac{1}{6} \frac{1}{5} \frac{1}{4} \frac{2}{7} \frac{1}{3} \frac{3}{8} \frac{2}{5} \frac{3}{7} \frac{1}{2}$$

$$\frac{4}{7} \frac{3}{5} \frac{5}{8} \frac{2}{3} \frac{5}{7} \frac{3}{4} \frac{4}{5} \frac{5}{6} \frac{6}{7} \frac{7}{8} \frac{1}{1}$$

Уражнение 2. Проделайте аналогичную операцию с восмой строчкой и проверьте, что таким образом получается строчка всех несократных дробей со значенателем не больше 9, иуших в порядке возрастания.

Уражнение 3. Проверьте, что в восмой и девятой строчках выполняются закономерности А и Б.

Строчка всех несократных дробей $\frac{p}{q}$, у которых $1 \leq p \leq q \leq n$ ($n$ — данные натуральное число), расположенных в возрастящем порядке, имеет в теории чисел специальное название — ряд Фарея, и обозначается иногда через $F_n$. Имя математика Фарея таким строчкам присвоил вликий французский математик Коши. Фарей интересы закономерности в этом ряду дробей, а Коши, обратив внимание на наблюдания Фарея, в 1816 году опубликовал их доказательство. Однако в полное воозможно, что эти закономерности были известны математикам и раньше.

Дадим два определения, связанные с нашими наблюдаениями.

Определение 1. Наозовем две дроби $\frac{a}{b}, \frac{c}{d}$ близкими, если $bc$-ад равно 1 или —1.

Уражнение 4. Выберите из дробей (1) все пары близких дробей.

35

Определение 2. Изовем медиантом двух дробей $\frac{a}{b}, \frac{c}{d}$ дробь $\frac{a+c}{b+d}$.

(Медианта несократимых дробей может оказаться сократимой дробью; приведите пример.)

2. Свойства близких дробей

Теперь наши гипотезы можно сформировать коротко так: в любом $n$-м ряду Фарея ($n$-й строке таблицы 1)

A. Соседние дроби близки дробу другую.

B. Каждая новая дробь $m/n$ является медиантом соседних с ней дробей.

В задаче М298 из «Задачника «Кванта» как раз и требовалось доказать свойство А: если $p/q < r/s$ — соседние дроби ряда $F_n$, то $qr - ps = 1$. Но оказывается, что значительное легко доказывать одновременно оба свойства — и А, и В. Мы наметим ниже целых три различных доказательства: одно — в пунктах 3—4, второе — в пункте 5, третье — в пункте 6. Укажем несколько простых свойств, характеризующих близкие дроби и медианты.

a) Для любых двух дробей $a/b$ и $c/d$ их разность по modulo не меньше 1/bd:

$$\left| \frac{a}{b} - \frac{c}{d} \right| \geq -\frac{1}{bd},$$

(2)

причем знак равенства в (2) получается в том и только в том случае, если дроби $a/b$ и $c/d$ близки. (Это объясняет выбор термин: близкие дроби.)

6. Медианта двух дробей всегда заключена между ними, m. e.

если $\frac{a}{b} < \frac{c}{d}$, то

$$\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}.$$

b) Если две дроби близки дроби к другу, то обе они несократимы.

r) Если две дроби близки дроби к другу, то их медианта близка к каждой из них.

d) Если две дроби близки дроби к другу, то их значения взаимно просты и их численные взаимно просты *).

e*) Из всех дробей, заключенных между двумя близкими дробями, называемый знаменатом имеет их медианта.

Упражнение 5. Докажите свойства a) — d).

Допустим теперь, что читатель не только проделал упражнение 2 — получил из воспользования 2 — но, продолжая действовать дальше по правилам В, получает десятию строку, одинаковую и так далее.

Из свойств 6), В), r) следует, что во всех новых строках сохраняется также закономерности:

1. дроби-mediанты, которые мы вставим, будут несократимы;
2. дроби идут в порядке возрастания;
3. любые две соседние дроби близки другую.

Оставшийся более трудный вопрос состоит в следующем. Попадут ли по правилам В в $n$-ю строку в се несократимые дроби со значением $n$ или может оказаться, что какие-то будут пропущены? Оказывается, что все такие дроби будут обязательно вставлены, т. е. мы действительно получим строку $F_n$ целиком. На этом месте мы советем читатель оставить и попробовать придумать доказательство самостояльно (один из путей — доказать свойство e, отмеченное звездочкой).

Мы же пока сделаем небольшое отсутствие и обсуждение вопрос:

сколько всего дробей в $n$-й строке нашей таблицы?

*) Цельные числа $a$ и $b$ называются взаимно простыми, если они не имеют общих делителей, бóльших 1.

36

3. Функция Эйлера.
   Число красных дробей

Пусть у нас имеется натуральное число $n$. Расмотрим все натуральные числа, не превосходящие $n$, и выберем из них те, которые взаимно просты с числом $n$. Количество этих чисел обозначим через $\varphi(n)$.

Например, для $n=8$ таких числа будут 1, 3, 5, 7, и тем самым $\varphi(8)=4$.

Итак, каждому натуральному числу $n$ сопоставлено число $\varphi(n)$. Это соответствие $\varphi$ называется функцией Эйлера.

Перечислим некоторые свойства функций Эйлера:

1. $\varphi(n) < n$.
2. Если $n = p$ — простое число, то $\varphi(p) = p-1$.
3. Для $n > 2$ число $\varphi(n)$ четно.
4. Если $n = p^d$ — степень простого числа $p$, то

$$\varphi(p^\alpha) = p^\alpha - p^{\alpha-1} = p^\alpha \left(1 - \frac{1}{p}\right).$$

5*) Если $m$ и $n$ взаимно просты, то $\varphi(mn) = \varphi(m) \cdot \varphi(n)$.
6) Общая формула для $\varphi(n)$ такова:

$$\varphi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_r}\right);$$

здеся $p_1, p_2, \dots, p_r$ — все простые числа, на которых делится $n$. (Эта формула доказана в статье «Малая теорема Ферма», «Квант», 1972, № 10.)

Доказать все эти свойства мы предлагаем читателю. Объясним только свойство 3). Все числа, меньше $n$ и взаимно простые с $n$, можно разить на пары: каждая пара состоит из таких чисел $q$, $s$, что $q+s=n$. Таким образом, число $\varphi(n)$ — четно.

Число красных дробей в $n$-й строке $F_n$, оченьindo, равно $\varphi(n)$, так как несократимых дробей $m/n$ ($0 \leqslant m/n \leqslant 1$) со значением $n$ столько же, сколько натуральных чисел $m$, меньше $n$, и взаимно простых с $n$.

Вопрос о том, сколько всего членов содержит $n$-й ряд Фарея $F_n$, обсуждает в своем письме читатель «Кванта». А. Китаев из Ленинграда. Ясно, что это число — обозначим его $\varphi(n)$ — равно

$$\varphi(n) = 1 + \varphi(1) + \varphi(2) + \varphi(3) + \dots + \varphi(n),$$

поскольку $\varphi(1) = 2$ и $\varphi(n) = \varphi(n-1) + \varphi(n)$ (см. таблицу 2). Простой формулы для $\varphi(n)$, видимо, не существует. Но интересно, что, несмотря на крайне нерегулярное поведение функции Эйлера $\varphi(n)$ (отно-

$$n \quad 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \quad 9 \quad 10 \quad 11 \quad 12 \quad 13 \quad 14 \quad 15 \quad 16 \dots$$

$$\varphi(n) \quad 1 \quad 1 \quad 2 \quad 2 \quad 2 \quad 6 \quad 4 \quad 6 \quad 4 \quad 10 \quad 4 \quad 12 \quad 6 \quad 8 \quad 8 \dots$$

$$\varphi(n) \quad 2 \quad 3 \quad 5 \quad 7 \quad 11 \quad 13 \quad 19 \quad 23 \quad 29 \quad 33 \quad 43 \quad 47 \quad 59 \quad 65 \quad 73 \quad 81 \dots$$

Таблица 2. Функция Эйлера и число дробей $F_n$.

шение $\frac{\varphi(n)}{n}$ былает сколь угодно близко к 0, и к 1), для $\varphi(n)$ можно доказать такое предельное соотношение:

$$\lim_{n \to \infty} \frac{\varphi(n)}{n^2} = \frac{3}{\pi^2} \approx 0,305 \dots,$$

т. е. $\varphi(x)$ при больших $x$ возрастает «приблизительно по параболе»: $\varphi(x) \approx \frac{3}{\pi^2} x^2$.

Это — одна из красивых теорем, полученных авторским математиком Ф. Мертенсом (1874 г.).

4. Соседние значенатели

Вернемся теперь к вопросу, поставленному в конце пункта 3, и обьясим, почему, действуюя по правилам В, мы получим все $\varphi(n)$ несократимых дробей со значенателем $n$. Сделаем еще одно наблюдение.

Обратим внимание на значенатели дробей в таблице 1. Составим для удобства из них новую таблицу 3. Правило В позволяет продолжать «таблицу значенателей» (не заботая о числительных) следующим образом.

В’. Нужно отметить в $(n-1)$-й строке все пары $q$, $s$ соседих чисел, сумма которых равна $n$, и между ними посмотрим $n$.

Как мы уже говорили, соседние значения $q$ и $s$ в таблице 3 — взаимно просты (см. свойство Д, пункт 2). Заметим теперь, что, вступая суммы $q+s=n$ в $n$-ю строку, мы встречаем какое из $\varphi(n)$ возможных представлений $n$ в виде суммы взаимно простых чисел (причемровно один). Например, в двоичной строке:

36

37

Таблица 3. Знаменатель рядов Фарея

$$9 = 1 + 8, \quad 9 = 5 + 4, \quad 9 = 7 + 2,$$
$$9 = 2 + 7, \quad 9 = 4 + 5, \quad 9 = 8 + 1.$$

Упражнение 6. Налишите еще три строчки таблицы 3 и проверьте, что все ф (n) представленный знаменатель n в виде суммы двух соседних знаменателей n = q + s встречаютсяровно по одному разу.

Наблюдение, сделанное в упражнении 6, формулируем так.
Г. В n-й строчке таблицы 3 каждое число, взаимно простое с n, былаем «соседом»ровно дважды: один раз — следа и один раз — справа.

Упражнение 7. Докажите, что если свойство Г выполняется во всех предыдущих строчках таблицы 3, то оно должно выполнять и в n-й строчке, полученной по правилау B'.

Из упражнения 7 вытекает (согласно принципу математической индукции), что если новые строчки таблицы 3 получать по правилау B’, то во всех строчках свойство Г будет выполняться, а следовательно, в n-й строчке будетровно ф (n) новых членов!

Упражнение 8. Пусть мы, начав со строчки $\left(\frac{0}{1}, \frac{1}{1}\right)$, несколько раз проделиваем такую операцию: между двумя уже написными дробями вставляем их медианту. Докажите, что для любой строчки, которое можно таким образом получить, выполняются свойства A и B.

Из результатата этой задачи, в частности, следует, что свойства A и B выполняются для каждой строчки таблицы 4, где между к а ж-dы ми и двумя дробями в следующее строчке вставляется медиант.

Упражнение 9. Докажите, что в таблице 4 в каждой строчке, начиная с n-й, встречаются все несократимые дроби со знаменателем n, причем каждая — один раз.

Таблица 4. 《Ускореенный》 ряд Фарея.

Таблица 4 тесто связывана с таблицей целых чисел, которая рассматривается в задаче М233 Г. А. Гальперина из «Задачника «Кванта». Эта таблица 5 появляется не только в знаменательх дробей таблицы 4, но и в их числительных (во второй «половине» таблицы 4, — начняя со второй строчки, во второй «четверти», — начняя с третий строчки и так далее!)!

5. Второе доказательство

Приведем короткое доказательство свойств А и В рядом Фарея $F_n$, опирающееся на свойство a) близких дробей (такое доказательство приведено в книге [2]).

Доказательство тоже проводится по индукции. Предположим, что для всех строчек $F_1, F_2, \dots, F_{n-1}$, предшествующих $F_n$, свойства A и B доказаны. Пусть некоторая дробь $m/n$ (so знаменателем n) заключена между соседними дробями $p/q$ и $r/s$ из $F_{n-1}, p/q < r/s$ (значит, $qr - ps = 1$).

Тогда

$$\frac{m}{n} - \frac{p}{q} \geq \frac{1}{qn}$$

и

$$\frac{r}{s} - \frac{m}{n} \geq \frac{1}{sn}.$$

Сложив эти неравенства, получим

$$\frac{r}{s} - \frac{p}{q} \geq \frac{q + s}{nqs};$$

38

$$\frac{q+s}{n} \leq qr - ps = 1;$$
$$q+s \leq n.$$

Сторое неравенство $q+s < n$ выполняется не может: в этом случае дробь $(p+r)/(q+s)$ встречается бы между $p/q$ и $r/s$ уже в $F_{n-1}$ (далее в $F_{q+s}$).

Следовательно,
$$n = q+s,$$
(4)
а поэтому неравенства (3) также должны быть равенствами, откуда
$$mq-np = 1, nr-ms = 1.$$ (5)
Из (4) и (5) следует, что $m = p+r$.

Итак, мы доказали, что $m/n$ — медианта дробей $p/q$ и $r/s$ и близка к каждой из них. (По существу, мы здесь доказали свойство e) близких дробей.) Значит, свойства A и B верны и для $F_n$.

У пряженние 10. Докажите, что:
a) если дроби $m/n$ и $p/q$, где $q < n$ — близки, то они — соседние дроби в $F_n$;
b) любая дробь, близкая к $m/n$, равна одной из дробей $(m+kr)/(n+ks)$, либо $(m+kp)/(n+kq)$, где $k = 0, 1, 2, \dots$, а $p/q$ и $r/s$ — соседи $m/n$ в $F_n$.

У пряженние 11. Пусть в последовательности дробей $\frac{1}{1} \leq \xi_1 \leq \dots \leq \xi_N \leq \frac{1}{1}$ каждые две соседние дроби близки друг к другу. Докажите, что эти последовательность можно получить проедурой, описанной в упражнения 8.

Геометрическая интерпретация, к которой мы переходим, значитно прояснить простые принципы закономерностей A и B, а заодно подсказket идею еще одного доказательства.

6. Решетки и параллелограммы

Возьем лист клетчатой бумаги и введем на нем систему координат. Две перpendикулярные линии сетки примем за оси координат, а сторону клетки — за единицу масштаба.

Поставим в соответствии каждой дроби $m/n$ ($0 \leq m/n \leq 1, n > 0$) точку с координатами $(n, m)$. (На рисунке 1 — это черные точки.) Вместо «точка» мы иногда будем говорить «дробь».

Несократимые дроби на рисунке 1 обведены голубыми кружками, а те из них, знаменители которых не больше 4, соединены голубыми отрезками с началом координат O.

Сформилируем несколько свойств дробей на геометрическом языке. Пусть $p/q$ и $r/s$ — две дроби, $A(q, p)$ и $B(s, r)$ — соответствующие им точки.

a) $p/q = r/s$ в том и только том случае, если точки A и B лежат на одном луче с началом O. Ближайший к O узел на этом луче соответствует несократимой дроби.

Дальше мы считаем, что $p/q \neq r/s$.

6. $p/q > r/s$, если луч OA составляет больший угол с горизонтальной осью координат, чем луч OB.

39

В) Дробь $(p+r)/(q+s)$ соответствует четырой вершине $C(p+r, q+s)$ параллелограмма $OACB$ (рис. 2). Для тех, кто знаком с векторами, запишем это так: $\overrightarrow{OC} = \overrightarrow{OA} + \overrightarrow{OB}$. (Мы видим, что созвучность терминов «medianta» и «mediана» не случайна: отрезок $OC$ идет как раз по медиане треугольника $OAB$.)

г) $|qr-ps|$ равно удвоенной площади $\Delta AOB$, то есть площади параллелограмма $OACB$.

д*) Внутри и на сторонах этого параллелограмма $OACB$ в том и только в том случае нет узлов (за исключением вершин), когда $|qr-ps|=1$.

е*) В этом случае точка $C$ — ближайший к $O$ узел сетки, лежащей внутри угла $AOB$.

У праванние 12. Докажите свойства a)—r).

Ключ к обьясению закономерности ряда Фарея — свойства d) и e*).

Постотрим визимательно на рисунки 2 и 3. На них внутренность угла $AOB$ разрезана прямыми на параллелограммы, конгруэнтные параллелограмму $OACB$. Все их вершины лежат в узлах клетчатой бумаги. Но на рисунке 2 (где площадь $OACB$ больше 1) многое узлы внутренни угла $AOB$ не являются вершинами этих параллелограммов. А на рисунке 3 (здесь площадь $OACB$ равна 1) любои узел внутренни угла $AOB$ — вершина такого параллелограмма, т. е. для любого такого узла $M(n, m)$ найдуться натуральные числа $x$ и $y$, для которых

$$\overrightarrow{OM} = x \cdot \overrightarrow{OA} + y \cdot \overrightarrow{OB}.$$

(6)

Векторное равенство (6) эквивалентно системе уравнений

$$\begin{cases} px + ry = m, \\ qx + sy = n. \end{cases}$$

*). Их можно доказать, опираясь на свойства решеток на плоскости (см. статьи А. А. Егорова и Н. Б. Васильева, «Квант», 1974, № 12.

У праванние 13. a) Докажите, что если $|qr-ps|=1$, где $p, q, r, s$ целые числа, то система (7) при любых целых $m$ и $n$ имеет решение в целых числах $x$ и $y$.

б*) Сформируйте и докажите обратную теорему.

b) Выведите из a), что для двух близких дробей $p/q < r/s$ любую дробь $m/n$, где $p/q < m/n < r/s$, можно представить в виде $\frac{px+ry}{qx+sy}$, где $x$ и $y$ — натуральные числа.

г) Докажите свойства e* из пунктов 2 и 5 и выведите отicioда закономерности А и В рядом Фарея.

Заключение

Мы наметили несколько путьей построения небольший, но красивой теории рядов Фарея.

Эту теорию можно строить в самом начале изучения целых чисел, не опираясь на основную теорему арифметики (о единственности разложения на простые множители). Сама эта теорема может быть выведена из свойств рядов Фарея. Из этих свойств легко получить также решения в целых числах уравнения $ax-by=1$, где $a$ и $b$ взимено просты: достаточно рассмотреть дробь $\frac{a}{b}$ и взять любую из соседних с ней дробей в ряду Фарея.

Ряды Фарея, а также изображение дробей на решетке полезны и в более тонких вопросах приближения вещественных чисел дробями с небольшими значениями.

Литература

1. Н. Б. Васильев. Решение задачи М233. «Квант», 1974, № 7, с. 39.
2. И. М. Виноградов. Основы теории чисел. М., «Наука», 1965.
3. К. Чандраекхаран. Введение в анализические теории чисел. М., «Мир», 1974.
4. Д. Б. Фукс, М. Б. Фукс. «О наилучших приближениях». «Квант», 1971, №№ 6 и 11.