Часть I · Числа Глава 5 из 60
Дроби
Как честно разделить семь пирогов на троих, почему при делении дробь переворачивают и откуда в записи одной седьмой бесконечная карусель цифр 142857.
Опирается на: 4 · Делимость и алгоритм Евклида
Вы научитесь
- складывать, вычитать, умножать и делить дроби и объяснять, почему правила именно такие
- переводить обыкновенную дробь в десятичную, а периодическую — обратно в обыкновенную
- доказывать, что десятичная запись любой дроби конечна или периодична
Семь пирогов, трое гостей. Деление с остатком из прошлой главы отвечает честно, но неполно: $7 = 3 \cdot 2 + 1$, каждому по два пирога, и один остаётся на столе. Натуральные числа на этом заканчиваются. Разрезать оставшийся пирог на три части может любой, у кого есть нож, а вот записать, сколько получил каждый, без нового числа нельзя.
Каждому досталось два пирога и ещё треть. Эта «треть» — первая дробь, с которой люди столкнулись задолго до всякой арифметики: при дележе зерна, земли, наследства. В этой главе мы сначала поработаем руками — порежем ленты, пироги и египетские хлебы, — а потом займёмся загадкой, которая прячется в самой простой дроби. Почему $\frac17 = 0{,}142857142857\dots$ крутит одни и те же шесть цифр бесконечно и почему $142857 \cdot 3 = 428571$ — те же цифры, только сдвинутые?
Доля и деление
Разрежем пирог на $3$ равные части. Одна часть — это $\frac13$ пирога, две части — $\frac23$. Нижнее число говорит, на сколько долей режем целое, верхнее — сколько долей берём.
Обыкновенная дробь $\frac{a}{b}$ — это $a$ долей по $\frac1b$ целого. Число $b$ под чертой называют знаменателем (он «называет» размер доли), число $a$ над чертой — числителем (он «считает», сколько таких долей).
У этой записи есть второй смысл, не менее важный. Вернёмся к пирогам. Можно не отдавать сначала целые пироги, а разрезать каждый из семи на три части и раздать по кусочку от каждого. Тогда у каждого гостя окажется $7$ кусочков по $\frac13$, то есть $\frac73$ пирога. Значит, $7 : 3 = \frac73$: дробь — это результат деления, записанный до того, как его выполнили. Черта дроби и знак деления означают одно и то же.
Первый способ дележа дал «два и ещё треть», второй — «семь третей». Это одно и то же количество пирога, записанное по-разному: $\frac73 = 2\tfrac13$. Запись $2\tfrac13$ называют смешанным числом: целая часть и дробь стоят рядом, а подразумевается их сумма $2 + \frac13$. Дробь, у которой числитель меньше знаменателя, называют правильной, остальные — неправильными. «Неправильная» здесь не упрёк: $\frac73$ ничем не хуже $2\tfrac13$, а в вычислениях даже удобнее.
Раз дробь — это частное, у неё может быть и знак: $\frac{-7}{3} = -\frac73$ — долг в семь третей пирога. А вот знаменатель нулём быть не может, по той же причине, по какой нельзя делить на ноль (глава 2): разрезать пирог «на ноль частей» не получится.
Одна доля — много имён
Половина пирога остаётся половиной, как её ни режь: $\frac12 = \frac24 = \frac36 = \frac{50}{100}$.
Если числитель и знаменатель дроби умножить или разделить на одно и то же натуральное число, дробь не изменится: $\frac ab = \frac{ak}{bk}$.
Идея: разрезать каждую долю ещё мельче — количество пирога от этого не меняется.
Дробь $\frac ab$ — это $a$ долей, каждая размером в $\frac1b$ целого. Разрежем каждую из $b$ долей целого на $k$ равных кусочков. Тогда целое окажется разрезанным на $bk$ равных кусочков, то есть каждый кусочек — это $\frac1{bk}$. В каждой старой доле $\frac1b$ ровно $k$ новых кусочков, значит, в $a$ старых долях — $ak$ кусочков по $\frac1{bk}$. Это и есть $\frac{ak}{bk}$, а количество пирога мы не меняли. Прочитанное справа налево, то же равенство говорит, что делить числитель и знаменатель на их общий делитель $k$ тоже можно.
Деление обоих чисел на общий делитель называют сокращением. Чтобы сократить дробь сразу до конца, делят на наибольший общий делитель. Так мы и поступили с дробью $\frac{391}{527}$ в прошлой главе: алгоритм Евклида за четыре деления нашёл $\text{НОД}(391, 527) = 17$, и дробь превратилась в $\frac{23}{31}$. Дальше сокращать некуда: у $23$ и $31$ нет общих делителей, кроме единицы.
Несократимая дробь — дробь, у которой числитель и знаменатель взаимно просты.
У каждой дроби $\frac ab$ (с натуральным $b$) есть ровно одна несократимая запись с натуральным знаменателем.
Идея: получить несократимую запись делением на НОД, а единственность вывести из того, что разложение на простые множители единственно.
Существует. Пусть $g = \text{НОД}(a, b)$. По основному свойству $\frac ab = \frac{a/g}{b/g}$. У чисел $\frac ag$ и $\frac bg$ нет общего делителя $e > 1$: иначе $a$ и $b$ делились бы на $ge$, большее, чем их наибольший общий делитель $g$.
Единственна. Пусть $\frac ab = \frac cd$, обе дроби несократимы, $b, d > 0$. Приведя к общему знаменателю $bd$, получаем $ad = bc$. Значит, $b$ делит произведение $ad$. Каждый простой множитель $b$ (с учётом повторений) должен найтись в разложении $ad$ (основная теорема арифметики), но в $a$ его нет — у $a$ и $b$ нет общих простых множителей. Значит, все они сидят в $d$, и $b$ делит $d$. Точно так же $d$ делит $b$. Натуральные числа, делящие друг друга, равны: $b = d$, а тогда из $ad = bc$ и $a = c$.
Выходит, что $\frac12$, $\frac24$ и $\frac{50}{100}$ — разные записи одного и того же числа. Такие числа и называют рациональными.
Рациональное число — число, которое можно записать дробью $\frac{p}{q}$ с целым $p$ и натуральным $q$. Все рациональные числа вместе обозначают $\mathbb Q$ — от слова «частное» (quotient). Целые числа тоже рациональны: $5 = \frac51$, $-2 = \frac{-2}{1}$.
Название происходит от латинского ratio — «отношение», а не от «разумности». Хотя и разумности в них хватает: в $\mathbb Q$ можно складывать, вычитать, умножать и делить (кроме деления на ноль), и результат никогда не выйдет за его пределы.
Общая мерка
Что больше: $\frac23$ или $\frac34$? А сколько будет, если их сложить? Положим рядом две ленты одинаковой длины: одна разрезана на трети, другая на четверти. Какая из закрашенных частей длиннее, видно сразу. А вот «на сколько» и «сколько вместе» сразу не скажешь: трети и четверти — кусочки разного размера, и считать их вместе — всё равно что складывать метры с футами.
Нужна общая мерка — такая маленькая доля, которая укладывается целое число раз и в треть, и в четверть. Подойдёт двенадцатая: $\frac13 = \frac4{12}$, $\frac14 = \frac3{12}$. Тогда $\frac23 = \frac8{12}$, $\frac34 = \frac9{12}$, и всё становится счётом: $8$ кусочков против $9$, вместе $17$.
Мерка $\frac1{12}$ взялась не с потолка: $12$ — наименьшее число, которое делится и на $3$, и на $4$, то есть $\text{НОК}(3, 4)$. Годится и любое общее кратное знаменателей, например их произведение — оно общее всегда.
При натуральных $b$ и $d$: $\frac ab + \frac cd = \frac{ad + cb}{bd}$ и $\frac ab - \frac cd = \frac{ad - cb}{bd}$.
Идея: перейти к общей мерке $\frac1{bd}$ — после этого складываются просто количества одинаковых кусочков.
По основному свойству дроби $\frac ab = \frac{ad}{bd}$ (числитель и знаменатель умножили на $d$) и $\frac cd = \frac{cb}{bd}$ (умножили на $b$). Теперь обе дроби — это количества кусочков одного размера $\frac1{bd}$: в первой их $ad$, во второй $cb$. Вместе $ad + cb$ таких кусочков, то есть $\frac{ad + cb}{bd}$. Если вторую часть отнять, останется $ad - cb$ кусочков.
Вот что означает каждая часть формулы:
Сравнивать дроби можно так же: приводим к общему знаменателю и сравниваем числители.
При натуральных $b$ и $d$: $\frac ab < \frac cd$ тогда и только тогда, когда $ad < bc$.
Идея: после приведения к общей мерке сравнивать приходится просто количества одинаковых кусочков.
По основному свойству $\frac ab = \frac{ad}{bd}$ и $\frac cd = \frac{bc}{bd}$. Обе дроби теперь состоят из кусочков одного размера $\frac1{bd}$: в первой их $ad$, во второй $bc$. Из двух количеств одинаковых кусочков больше то, где кусочков больше, поэтому $\frac ab < \frac cd$ ровно тогда, когда $ad < bc$. Например, $\frac23 < \frac34$, потому что $2 \cdot 4 = 8 < 9 = 3 \cdot 3$.
Чему равно $\frac12 + \frac13$?
Общая мерка — шестая: $\frac12 = \frac36$, $\frac13 = \frac26$, вместе $\frac56$. Ответ $\frac25$ заведомо неверен: сумма не может быть меньше слагаемого $\frac12$.
Сложите $\frac7{12} + \frac5{18}$. Ответ — несократимая дробь.
$\text{НОК}(12, 18) = 36$, потому что $12 = 2^2 \cdot 3$, $18 = 2 \cdot 3^2$. Тогда $\frac7{12} = \frac{21}{36}$, $\frac5{18} = \frac{10}{36}$, сумма $\frac{31}{36}$. С произведением знаменателей вышло бы $\frac{7 \cdot 18 + 5 \cdot 12}{216} = \frac{186}{216}$, и пришлось бы сокращать на $6$.
Умножить и разделить
Умножение на дробь звучит странно: как можно взять число «две третьих раза»? Слово «раз» здесь мешает. Умножить на $\frac23$ — значит взять $\frac23$ от числа. Две трети от трёх четвертей пирога: делим $\frac34$ на три равные части — в каждой по $\frac14$, берём две — $\frac24 = \frac12$.
$\frac ab \cdot \frac cd = \frac{ac}{bd}$: взять $\frac ab$ от $\frac cd$ — значит перемножить числители и знаменатели.
Идея: разрезать $\frac cd$ на $b$ равных частей и взять $a$ из них, а для этого измельчить мерку в $b$ раз.
По основному свойству $\frac cd = \frac{cb}{db}$: это $cb$ кусочков размера $\frac1{bd}$. Разделим их на $b$ равных частей — в каждой окажется $c$ кусочков, то есть одна $b$-я часть от $\frac cd$ равна $\frac{c}{bd}$. Взять $a$ таких частей — значит взять $ac$ кусочков по $\frac1{bd}$: получается $\frac{ac}{bd}$. На картинке это прямоугольник: единичный квадрат режем по ширине на $b$ полос и берём $a$ из них, по высоте — на $d$ полос и берём $c$; квадрат разрезан на $bd$ клеток, а в пересечении оказалось $ac$ клеток. Тот же счёт показывают ленты в режиме «$\times$».
Числитель на числитель, знаменатель на знаменатель — общий знаменатель здесь не нужен, в отличие от сложения. Заметьте, что умножение на правильную дробь уменьшает: две трети от чего угодно меньше целого. Если в голове сидит «умножение увеличивает», то это привычка из натуральных чисел, и ей пора на пенсию.
С делением интереснее. Школьное правило звучит как заклинание: «чтобы разделить на дробь, умножь на перевёрнутую». Откуда оно?
Деление отвечает на вопрос «сколько раз одно помещается в другом». Сколько раз отрезок в $\frac34$ метра помещается в $2$ метрах? Перейдём к общей мерке — четвертям: в двух метрах $8$ четвертей, в отрезке $\frac34$ — три. Сколько раз $3$ помещается в $8$? Два полных раза и ещё две трети, то есть $\frac83$ раза. Значит, $2 : \frac34 = \frac83$. А $2 \cdot \frac43$ — тоже $\frac83$.
Так выходит всегда. После приведения к общей мерке делимое и делитель становятся просто числами одинаковых кусочков, и делить остаётся одно число на другое: $\frac ab : \frac cd = \frac{ad}{bd} : \frac{bc}{bd} = \frac{ad}{bc}$. А это и есть $\frac ab \cdot \frac dc$.
Обратное число к $x \ne 0$ — такое число $\frac1x$, что $x \cdot \frac1x = 1$. Для дроби $\frac ab$ с $a \ne 0$ обратная — перевёрнутая дробь $\frac ba$: $\frac ab \cdot \frac ba = \frac{ab}{ab} = 1$.
При $c \ne 0$: $\frac ab : \frac cd = \frac ab \cdot \frac dc = \frac{ad}{bc}$.
Идея: деление — это умножение наоборот. Разделить $x$ на $y$ — значит найти такое число $z$, что $z \cdot y = x$.
Число $\frac{ad}{bc}$ подходит. Умножим его на делитель: $\frac{ad}{bc} \cdot \frac cd = \frac{adc}{bcd}$ (правило умножения). Числитель и знаменатель делятся на $cd \ne 0$, и по основному свойству получаем $\frac ab$ — делимое.
Других нет. Пусть $z \cdot \frac cd = \frac ab$. Умножим обе части на обратное к делителю число $\frac dc$: слева $z \cdot \frac cd \cdot \frac dc = z \cdot 1 = z$, справа $\frac ab \cdot \frac dc = \frac{ad}{bc}$. Значит, $z = \frac{ad}{bc}$.
Вот что означает каждая часть этой формулы:
Отсюда и эффект, который удивляет каждого шестиклассника: деление на правильную дробь увеличивает. Разделить на $\frac12$ — значит спросить, сколько в числе половинок, а их вдвое больше, чем единиц.
Сколько стаканов по $\frac38$ литра можно наполнить из двух литров сока? Ответ может быть дробным: неполный стакан тоже считается своей долей.
$2 : \frac38 = 2 \cdot \frac83 = \frac{16}3 = 5\tfrac13$. В восьмых долях литра: в двух литрах их $16$, в стакане $3$, и $16 : 3 = 5\tfrac13$ — пять полных стаканов и треть шестого.
Правила собраны — пора набить руку. Тренажёр даёт задачи трёх уровней, от сокращения до смешанных чисел со знаками, и разбирает каждую по шагам.
Хлебы писца Ахмеса
Египетские писцы решали задачу о пирогах иначе, и их способ до сих пор задаёт математикам загадки. В Египте записывали доли вида $\frac1n$ — «одна часть из $n$»; особые знаки были ещё для $\frac12$ и $\frac23$. Любую другую дробь писец выражал суммой разных долей: вместо $\frac34$ — $\frac12 + \frac14$.
Египетская дробь — запись числа суммой различных долей вида $\frac1n$.
Зачем такие сложности? У способа есть практический смысл. Если девять хлебов надо поделить на десятерых, запись $\frac9{10}$ подсказывает резать каждый хлеб на десять частей — это девяносто кусков. Египетская запись говорит, как резать крупно: сначала каждому по половине, потом по трети и так далее. Каждый получает по одному куску каждого размера, и все видят, что доли одинаковы.
Как найти такое разложение? Самый прямой способ описал Фибоначчи в «Книге абака» (1202): на каждом шаге давать каждому самый большой кусок $\frac1m$, который ещё помещается в остаток. Для $\frac9{10}$: половина помещается ($\frac12 \le \frac9{10}$), остаётся $\frac9{10} - \frac12 = \frac25$; в $\frac25$ помещается $\frac13$, остаётся $\frac25 - \frac13 = \frac1{15}$ — и это уже доля. Выходит $\frac9{10} = \frac12 + \frac13 + \frac1{15}$: не так, как у Ахмеса, но тоже верно.
Но заканчивается ли жадный способ всегда? Может быть, для какой-нибудь дроби куски будут мельчать бесконечно?
Для любой дроби $0 < \frac ab < 1$ жадный алгоритм заканчивается не больше чем за $a$ шагов и даёт сумму различных долей.
Идея: следить за числителем остатка — он на каждом шаге уменьшается.
Пусть на очередном шаге остаток равен $\frac ab$ (с $0 < \frac ab < 1$), и $\frac1m$ — самая большая доля, которая в него помещается, то есть $\frac1m \le \frac ab$, но $\frac1{m-1} > \frac ab$. Так как $\frac ab < 1$, здесь $m \ge 2$. Новый остаток равен
$$\frac ab - \frac1m = \frac{am - b}{bm}.$$Его числитель $am - b$ не отрицателен (ведь $\frac1m \le \frac ab$ означает $b \le am$). А меньше $a$ он потому, что $\frac1{m-1} > \frac ab$ означает $b > a(m - 1) = am - a$, то есть $am - b < a$. После сокращения числитель может стать только меньше.
Итак, числитель остатка — натуральное число, которое с каждым шагом уменьшается хотя бы на единицу, пока остаток не станет нулём. Начав с $a$, он дойдёт до нуля не больше чем за $a$ шагов. Доли не повторяются: новый остаток меньше, чем $\frac1{m-1} - \frac1m = \frac1{m(m-1)} \le \frac1m$, поэтому следующая доля строго меньше $\frac1m$.
Честный способ не всегда экономен. Для $\frac5{121}$ жадный алгоритм выдаёт пять долей, последняя из которых — единица, делённая на двадцатипятизначное число, хотя хватило бы трёх: $\frac5{121} = \frac1{33} + \frac1{121} + \frac1{363}$. Самое короткое разложение можно найти перебором, но быстрого способа для него не знают, и многие вопросы о египетских дробях до сих пор открыты. Например, гипотеза Эрдёша — Штрауса (1948) утверждает, что любую дробь $\frac4n$ при $n \ge 2$ можно записать суммой трёх долей $\frac1x + \frac1y + \frac1z$. Её проверили на компьютерах для огромного количества $n$, но не доказали.
Десятая Стевина
Египетские доли, вавилонские шестидесятые, римские двенадцатые — у каждой культуры были свои дроби, и считать с ними было мучением. Выход подсказала позиционная запись из главы 1: если целые числа пишут разрядами по степеням десяти, почему бы не продолжить разряды вправо — десятые, сотые, тысячные?
Десятичная дробь — дробь со знаменателем $10$, $100$, $1000$, …, записанная разрядами после запятой: $2{,}375 = 2 + \frac3{10} + \frac7{100} + \frac5{1000} = \frac{2375}{1000}$.
Какую дробь можно записать конечной десятичной? Ту, которую можно привести к знаменателю $10^n = 2^n \cdot 5^n$: $\frac38 = \frac{375}{1000} = 0{,}375$, $\frac7{20} = \frac{35}{100} = 0{,}35$. А вот $\frac13$ никак не хочет: деление $1 : 3$ уголком не заканчивается, $0{,}3333\dots$
Несократимая дробь $\frac pq$ записывается конечной десятичной дробью тогда и только тогда, когда в разложении $q$ на простые множители нет ничего, кроме двоек и пятёрок.
Идея: конечная десятичная дробь — это дробь со знаменателем $10^n = 2^n 5^n$, а в такой знаменатель могут «влезть» только двойки и пятёрки.
Если в $q$ только двойки и пятёрки, $q = 2^\alpha 5^\beta$. Возьмём $n$ — большее из чисел $\alpha$ и $\beta$ — и умножим числитель и знаменатель на $2^{n - \alpha} 5^{n - \beta}$ (основное свойство дроби). Знаменатель станет $2^n 5^n = 10^n$, и дробь запишется $n$ знаками после запятой: $\frac3{8} = \frac{3 \cdot 5^3}{2^3 \cdot 5^3} = \frac{375}{1000}$.
Обратно, пусть $\frac pq = \frac N{10^n}$. Тогда $p \cdot 10^n = N q$, то есть $q$ делит $p \cdot 10^n$. Каждый простой множитель $q$ должен найтись в разложении $p \cdot 10^n$ (основная теорема арифметики), но в $p$ его нет — дробь несократима. Значит, он входит в $10^n = 2^n 5^n$, то есть это $2$ или $5$.
Для $\frac13$ знаменатель $3$ — не двойка и не пятёрка, поэтому конечной записи у неё нет, и деление уголком обязано идти бесконечно.
Почему цифры повторяются
Разделим уголком $1$ на $7$. Будем следить не только за цифрами, но и за остатками.
| Делим | $10$ | $30$ | $20$ | $60$ | $40$ | $50$ | $10$ |
|---|---|---|---|---|---|---|---|
| Цифра | 1 | 4 | 2 | 8 | 5 | 7 | 1 |
| Остаток | 3 | 2 | 6 | 4 | 5 | 1 | 3 |
На седьмом шаге мы снова делим $10$ на $7$ — ровно то же, что на первом. Всё, что будет дальше, уже было: следующая цифра и следующий остаток зависят только от текущего остатка. Цифры $142857$ пойдут по кругу бесконечно: $\frac17 = 0{,}142857142857\dots$
Периодическая дробь — бесконечная десятичная дробь, в которой с некоторого места один и тот же блок цифр повторяется бесконечно. Этот блок называют периодом и пишут в скобках: $\frac17 = 0{,}(142857)$. Цифры между запятой и периодом называют предпериодом: $\frac16 = 0{,}1(6)$, $\frac7{12} = 0{,}58(3)$.
Остаток от деления на $7$ может быть только $0, 1, \dots, 6$. Если он хоть раз станет нулём, деление закончится и дробь окажется конечной. Если нет, ненулевых остатков всего шесть, а шагов — сколько угодно. Значит, не позже седьмого шага какой-то остаток повторится.
Это частный случай простого и удивительно сильного соображения. В русской традиции его рассказывают про кроликов в клетках, а подробно он разобран в главе о комбинаторике.
Если $n + 1$ предметов разложить по $n$ ящикам, то хотя бы в одном ящике окажется не меньше двух предметов.
Если бы в каждом ящике лежало не больше одного предмета, всего предметов было бы не больше $n$. А их $n + 1$.
При делении на $q$ ящики — это ненулевые остатки $1, 2, \dots, q - 1$, а предметы — шаги деления.
Десятичная запись любой дроби $\frac pq$ либо конечна, либо периодична, причём период не длиннее $q - 1$ цифр.
Идея: всё, что происходит при делении уголком, определяется текущим остатком, а разных остатков конечное число.
Будем делить $p$ на $q$ уголком. Сначала выделим целую часть: $p = q \cdot n + r_0$, где $0 \le r_0 < q$ (деление с остатком из главы 4). Дальше каждый шаг устроен одинаково: к текущему остатку $r$ приписываем ноль, то есть берём $10r$, и снова делим с остатком: $10r = q \cdot c + r'$. Число $c$ — очередная цифра после запятой, $r'$ — новый остаток, $0 \le r' < q$. Важно, что цифра $c$ и новый остаток $r'$ зависят только от $r$ — больше ни от чего.
Если какой-то остаток оказался нулём, все следующие цифры — нули, и десятичная запись конечна.
Если нулей нет, все остатки лежат среди $q - 1$ чисел $1, 2, \dots, q - 1$. Посмотрим на остатки после первых $q$ шагов: их $q$, а возможных значений $q - 1$, поэтому по принципу Дирихле два из них совпадают — скажем, после шага $i$ и после шага $j$, $i < j \le q$. Раз всё дальнейшее зависит только от остатка, начиная с шага $j$ деление повторяет то, что делалось начиная с шага $i$: те же цифры, те же остатки — и так снова и снова. Значит, цифры с $(i + 1)$-й по $j$-ю повторяются бесконечно. Это период, и в нём $j - i \le q - 1$ цифр.
Нарисуем остатки точками на окружности и будем соединять каждый остаток со следующим. Для семёрки получится замкнутый путь через все шесть ненулевых остатков.
Картинка объясняет фокус из начала главы. Остатки при делении на $7$ ходят по кругу $1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1$. Дробь $\frac37$ начинает деление с остатка $3$ — это та же карусель, только мы сели на неё на другой остановке. Поэтому $\frac37 = 0{,}(428571)$: те же цифры со сдвигом. Умножить $142857$ на $3$ — всё равно что вычислить период дроби $\frac37$, и потому
$$142857 \cdot 2 = 285714, \quad \cdot 3 = 428571, \quad \cdot 4 = 571428, \quad \cdot 5 = 714285, \quad \cdot 6 = 857142.$$А при умножении на $7$ получается $999999$: ведь $7 \cdot \frac17 = 1 = 0{,}(999999)$. Кстати, приближение Архимеда $\pi \approx \frac{22}7 = 3{,}(142857)$ катается на той же карусели.
С тринадцатью картина другая: $\frac1{13} = 0{,}(076923)$, $\frac2{13} = 0{,}(153846)$. Двенадцать ненулевых остатков распались на два круга по шесть, и каждая дробь $\frac k{13}$ попадает на один из них. У $\frac1{17}$ снова один большой круг — период из $16$ цифр.
Почему длина периода $\frac1p$ делит $p - 1$
Если $p$ — простое число, отличное от $2$ и $5$, то длина периода дроби $\frac1p$ делит $p - 1$.
Идея: ненулевые остатки от деления на $p$ распадаются на непересекающиеся круги, и все круги одинаковой длины — той самой, что у периода.
Стрелки. Шаг деления переводит остаток $r$ в остаток числа $10r$ при делении на $p$ — нарисуем стрелку $r \to r'$. Ненулевой остаток переходит в ненулевой: $p$ простое и не делит ни $10$, ни $r$, а значит, и $10r$. Разные остатки переходят в разные: если $10r$ и $10s$ дают одинаковый остаток, то $p$ делит $10(r - s)$, а раз $p$ не делит $10$, то делит $r - s$, и $r = s$.
Круги. Выйдем из любого ненулевого остатка $r$ и пойдём по стрелкам. Остатков конечное число, поэтому какой-то из них встретится повторно. Первым повторится именно $r$: если бы первым повторился другой остаток $s$, в $s$ вели бы стрелки из двух разных остатков — а разные остатки переходят в разные. Значит, каждый ненулевой остаток лежит на замкнутом круге, и два круга либо совпадают, либо не пересекаются.
Одинаковая длина. Круг через остаток $1$ — это остатки чисел $1, 10, 100, \dots$ при делении на $p$; пусть в нём $L$ остатков. Деление $1 : p$ начинается с остатка $1$ и сразу идёт по этому кругу, поэтому период $\frac1p$ состоит ровно из $L$ цифр. Круг через остаток $k$ — это остатки чисел $k, 10k, 100k, \dots$, то есть круг через $1$, умноженный на $k$. Умножение на $k$ (которое $p$ не делит) тоже переводит разные остатки в разные, поэтому и в этом круге ровно $L$ остатков. Все $p - 1$ ненулевых остатков разбились на круги по $L$ штук — значит, $L$ делит $p - 1$. Для $7$ — один круг длины $6$; для $13$ — два круга длины $6$; для $41$ — восемь кругов длины $5$, потому что $\frac1{41} = 0{,}(02439)$.
Какая цифра стоит на сотом месте после запятой в десятичной записи $\frac17$?
Период $142857$ имеет длину $6$. Так как $100 = 6 \cdot 16 + 4$, на сотом месте стоит та же цифра, что на четвёртом, — это $8$.
Из периода — обратно в дробь
Теорема работает и в обратную сторону: любая периодическая дробь — рациональное число. Пусть $x = 0{,}(27) = 0{,}272727\dots$ Умножим на $100$ — запятая сдвинется на длину периода: $100x = 27{,}2727\dots$ Хвосты после запятой у $100x$ и у $x$ одинаковые, и при вычитании они уничтожаются:
$$100x - x = 27, \qquad 99x = 27, \qquad x = \frac{27}{99} = \frac3{11}.$$С любым периодом рассуждение то же.
Любая периодическая десятичная дробь равна некоторой обыкновенной дроби, то есть рациональна.
Идея: сдвинуть запятую ровно на длину периода — хвосты совпадут и при вычитании исчезнут.
Чисто периодическая дробь. Пусть $x = 0{,}(a_1 a_2 \dots a_k)$, и $A = \overline{a_1 a_2 \dots a_k}$ — период, прочитанный как натуральное число. Умножение на $10^k$ сдвигает запятую на $k$ знаков вправо: $10^k x = a_1 a_2 \dots a_k{,}(a_1 a_2 \dots a_k) = A + x$ — после запятой стоит в точности тот же бесконечный хвост, что и у $x$. Вычитаем $x$: $(10^k - 1)x = A$, и $x = \frac{A}{10^k - 1}$ — дробь. (Что такое бесконечная десятичная запись и почему с ней можно так обращаться, строго объясняет глава о рядах; здесь мы пользуемся только тем, что умножение на $10$ сдвигает запятую.)
Дробь с предпериодом. Пусть у $x$ целая часть $N$, предпериод из $m$ цифр $b_1 \dots b_m$ и чисто периодический хвост. Тогда $10^m x = \overline{N b_1 \dots b_m} + y$, где $y$ — чисто периодическая дробь. Число $y$ рационально по первой части доказательства, целое $\overline{N b_1 \dots b_m}$ тоже, а сумма дробей и её деление на $10^m$ снова дают дробь.
Первая часть доказательства — это готовая формула.
Если перед периодом есть предпериод, сначала сдвинем запятую так, чтобы он ушёл в целую часть. Например, $x = 0{,}1(6)$: тогда $10x = 1{,}(6) = 1 + \frac69 = \frac53$ и $x = \frac5{30} = \frac16$.
Две теоремы вместе дают полную картину.
Рациональные числа — это в точности те, у которых десятичная запись конечна или периодична. Дробь даёт период, потому что остатков конечное число; период даёт дробь, потому что сдвиг на длину периода уничтожает хвост.
При $k = 1$ и периоде $9$ формула с девятками даёт то, во что поначалу трудно поверить: $0{,}(9) = \frac99 = 1$.
Как соотносятся числа $0{,}999\dots$ (девятки без конца) и $1$?
Проще всего так: $\frac13 = 0{,}333\dots$, умножаем на $3$ — получаем $1 = 0{,}999\dots$ Или по формуле: $0{,}(9) = \frac99$. У числа $1$ просто две десятичные записи, как у половины — много записей дробью. Строго о бесконечных суммах — в главе о рядах.
Запишите $0{,}(36)$ несократимой дробью.
Период из двух цифр: $0{,}(36) = \frac{36}{99}$. Сокращаем на $9$: $\frac4{11}$. Проверка делением: $4 : 11 = 0{,}3636\dots$
Теперь потренируйтесь в обе стороны: из обыкновенной дроби в периодическую и обратно.
А если в десятичной записи никакой блок не повторяется бесконечно — например, $0{,}1010010001\dots$, где между единицами становится всё больше нулей? Такое число не может быть дробью. Придумать подобные записи легко. Вопрос в другом: встречаются ли в жизни числа, которые не дроби? Об этом — в следующей главе.
Дерево всех дробей
Вернёмся к неверному ответу $\frac12 + \frac13 = \frac25$. В арифметике он неверен, а в спортивной статистике верен. Баскетболист в первой игре попал $1$ раз из $2$ бросков, во второй — $1$ из $3$. За две игры: $2$ попадания из $5$ бросков. Когда складывают «сколько из скольких», складывают и числители, и знаменатели.
Медианта дробей $\frac ab$ и $\frac cd$ — дробь $\frac{a + c}{b + d}$.
Точность за две игры не может быть лучше лучшей и хуже худшей. Отсюда догадка: медианта всегда лежит между исходными дробями, как $\frac13 < \frac25 < \frac12$.
Если $\frac ab < \frac cd$ и знаменатели $b$, $d$ положительны, то $\frac ab < \frac{a + c}{b + d} < \frac cd$.
Идея: вычесть и посмотреть на знак разности.
По признаку сравнения дробей условие $\frac ab < \frac cd$ означает, что $bc - ad > 0$. Приведём к общему знаменателю: $\frac{a + c}{b + d} - \frac ab = \frac{(a + c)b - a(b + d)}{(b + d)b} = \frac{bc - ad}{(b + d)b}$. Числитель положителен, знаменатель тоже, значит, медианта больше $\frac ab$. Так же $\frac cd - \frac{a + c}{b + d} = \frac{c(b + d) - d(a + c)}{d(b + d)} = \frac{bc - ad}{d(b + d)} > 0$, и медианта меньше $\frac cd$. В этом рассуждении нигде не нужно, чтобы числа были целыми, — лишь бы знаменатели были положительны.
Это свойство строит самую красивую картину главы.
Начнём с «дробей» $\frac01$ и $\frac10$. Вторая — не число, а условная бесконечность: нужно только, чтобы было что складывать. Вставим между ними медианту $\frac11$. Потом между каждыми соседями снова вставим медианты: $\frac12$ и $\frac21$. Потом ещё раз: $\frac13, \frac23, \frac32, \frac31$ — и так бесконечно. Если записывать каждую новую дробь под той, от которой она ответвилась, получится двоичное дерево. Его независимо описали немецкий математик Мориц Штерн (1858) и французский часовщик Ашиль Броко (1861), которому оно помогало подбирать шестерёнки с нужным отношением числа зубцов.
Будем называть соседями две дроби, которые на каком-то этапе построения стоят рядом (как $\frac12$ и $\frac11$ на втором этапе). У соседей есть скрытое свойство.
Если $\frac ab < \frac cd$ — соседи, то $bc - ad = 1$.
Идея: свойство есть в самом начале, и вставка медианты его не портит.
В начале соседей двое, $\frac01$ и $\frac10$: $1 \cdot 1 - 0 \cdot 0 = 1$. Пусть для соседей $\frac ab$ и $\frac cd$ верно $bc - ad = 1$, и между ними вставили медианту. Теперь соседей две пары. Для левой пары: $(a + c)b - a(b + d) = bc - ad = 1$. Для правой: $c(b + d) - d(a + c) = bc - ad = 1$. Значит, свойство переходит с этапа на этап и верно для любых соседей.
Каждая положительная рациональная дробь встречается в дереве ровно один раз, причём в несократимом виде.
Идея: несократимость и единственность следуют из двух лемм, а то, что дерево не пропускает ни одной дроби, — из того, что поиск нужной дроби не может длиться бесконечно.
Несократимость. Каждая дробь дерева — медианта $\frac{a + c}{b + d}$ каких-то соседей, а для новой пары соседей $(a + c)b - a(b + d) = 1$. Если бы $a + c$ и $b + d$ делились на число $e > 1$, то на $e$ делилась бы и левая часть, то есть единица. Значит, у числителя и знаменателя нет общих делителей.
Не больше одного раза. На каждом этапе дроби стоят строго по возрастанию: вначале $\frac01 < \frac10$ (условно), а каждая новая медианта ложится строго между своими соседями по лемме о медианте. Поэтому среди выписанных дробей нет двух равных, а все дроби дерева рано или поздно оказываются в этом ряду.
Хотя бы один раз. Возьмём несократимую $\frac pq > 0$ и будем спускаться по дереву: сравниваем $\frac pq$ с текущей дробью и идём налево или направо. Пока мы не пришли в $\frac pq$, она лежит строго между двумя соседями $\frac ab < \frac cd$, между которыми стоит текущая дробь. По признаку сравнения $pb - qa$ и $qc - pd$ — натуральные числа, то есть каждое не меньше $1$. Умножим первое на $d$, второе на $b$ и сложим: $pbd - qad + qbc - pbd = q(bc - ad) = q$, так что $q \ge b + d$. Умножив на $c$ и на $a$, так же получим $p \ge a + c$. Значит, числитель и знаменатель текущей медианты не больше $p$ и $q$. Но с каждым шагом вниз сумма числителя и знаменателя медианты растёт хотя бы на единицу, а больше $p + q$ стать не может. Натуральное число, которое растёт на каждом шаге и не превосходит $p + q$, может расти не больше $p + q$ шагов, — значит, поиск остановится, а остановиться он может только на $\frac pq$.
Спуск к дроби записывается словом из букв Л и П. К $\frac5{13}$ ведёт путь ЛЛПЛП, к $\frac{355}{113}$ — три П, семь Л и пятнадцать П. Числа $3$, $7$ и $16 = 15 + 1$ здесь не случайны: это звенья так называемой цепной дроби, к которой мы вернёмся в следующей главе.
Какая дробь стоит в дереве в конце пути ЛПЛ?
Из $\frac11$ налево — медианта $\frac01$ и $\frac11$, то есть $\frac12$. Теперь соседи $\frac12$ и $\frac11$, направо — $\frac{1 + 1}{2 + 1} = \frac23$. Соседи $\frac12$ и $\frac23$, налево — $\frac{1 + 2}{2 + 3} = \frac35$.
Куда дальше
Нарисуйте квадрат со стороной $1$ и проведите диагональ. Постройте на ней новый квадрат: он складывается из четырёх половинок исходного, так что его площадь равна $2$. Значит, длина диагонали — число, квадрат которого равен $2$. Какая это дробь? Попросите дерево Штерна — Броко её найти. $\frac75$ — почти: $49$ против $50$. $\frac{17}{12}$ — ещё ближе: $289$ против $288$. Путь уходит вниз и не кончается.
Может быть, мы просто не дошли? Или такой дроби нет вовсе — и тогда у отрезка, который можно нарисовать карандашом, длина, которую нельзя записать дробью? Древние греки это доказали, и, по преданию, открытие дорого обошлось тому, кто его разгласил. Расследование — в главе 6.