УДИВИТЕЛЬНЫЕ ПРИКЛЮЧЕНИЯ ПЕРИОДИЧЕСКИХ ДРОБЕЙ


От редакции. Удивительное дело. Наш журнал существует уже 20 лет и никто никогда ничего не писал нам на эту тему: о свойствах периодов десятичных дробей. И вдруг — сразу три статьи! Одну написал В. Г. Столяр, другую — Э. А. Кураев и З. К. Силогадзе и третью — Г. А. Гальперин и А. В. Корлюков. В конце концов мы решили слить эти статьи в одну, приняв за основу статью В. Г. Столяра. Вот что из этого вышло.



Рассмотрим примеры...

Вероятно, читатель знает (а если нет — ещё лучше: он узнает это из нашей статьи), что всякая обыкновенная дробь представляется периодической десятичной дробью (конечную десятичную дробь мы можем считать периодической с периодом 0 или 9). Но вряд ли многие представляют, сколько неожиданностей заключает в себе эта периодическая дробь. Рассмотрим три примера:

1

7

 = 0,142857142857...,
1

12

 = 0,083333333333...,
1

13

 = 0,076923076923...

Мы видим, что у чисел 1/7 и 1/13 период начинается сразу после запятой и состоит из шести цифр (142857 и 076923 соответственно), а у числа 1/12 он начинается с третьей позиции после запятой и состоит из единственной цифры: 3. Внимательное рассмотрение периодов чисел 1/7 и 1/13 позволяет заметить ещё одно обстоятельство. Именно, положим N = 142857 (период дроби 1/7) и будем последовательно умножать N на 2, 3, 4, ...:

2N = 285714,       3N = 428571,
4N = 571428, 5N = 714285,
6N = 857142, 7N = 999999.

Мы видим, что первые пять из этих чисел получаются из числа N «круговой перестановкой» цифр: сколько-то цифр из конца числа переезжает в начало; а число 7N состоит из одних девяток. Теперь проделаем то же с периодом дроби 1/13 (N = 076923):

2N = 153846, 3N = 230769,
4N = 307692, 5N = 384615,
6N = 461538, 7N = 538461,
8N = 615384, 9N = 692307,
10N = 769230, 11N = 846153,
12N = 923076,       13N = 999999.

Здесь дело обстоит несколько иначе, но всё равно интересно: пять из выписанных чисел (3N, 4N, 9N, 10N, 12N) получаются из числа N круговой перестановкой цифр, другие шесть чисел (2N, 5N, 6N, 7N, 8N, 11N) получаются круговой перестановкой цифр друг из друга и, наконец, число 13N состоит из одних девяток.

Можно заметить ещё вот что. Если взять любое из выписанных выше шестизначных чисел, кроме числа 999999, «разломить» его на два трёхзначных числа и вычислить сумму этих половинок, то получится 999; например, 142 + 857 = 999 и т.д.

Как видите, с периодическими десятичными дробями связано немало загадок. Некоторые из этих загадок остаются не разгаданными по сей день, несмотря на многочисленные попытки, предпринимавшиеся на протяжении нескольких веков математиками из разных стран, как великими, так и более «скромными». Всё же кое-что об этом мы можем рассказать.

Хобби Иоганна Бернулли

Оставим на время периоды и перенесёмся в Швейцарию конца XVIII века. Мы наблюдаем странную картину: маститый математик Иоганн III Бернулли, представитель знаменитой математической семьи Бернулли, удостоившейся, подобно королевским династиям, присоединения порядковых номеров к именам, занимается, можно сказать, детской игрой! Он разлагает на простые множители числа, записываемые одними единицами: 11 = 11, 111 = 3 · 37, 1111 = 11 · 101 и т.д. В 1773 году Бернулли помещает в трудах Берлинской академии таблицу простых делителей чисел, составленных из n единиц, — до n = 31 (см. рис. 1). Несмотря на то, что ему не удалось найти делители для некоторых чисел этого вида (n = 11, 17, 29), а для трёх чисел (n = 20, 25, 27) разложение не доведено до простых множителей, несмотря на допущенные им ошибки (для n = 22, 24, 26), мы сегодня можем только преклоняться перед гигантским трудом по вычислению простых множителей этих огромных чисел. Можно предположить, что автором таблицы двигала не только исследовательская жилка учёного, но и подлинная эстетическая страсть художника, вдохновлённого удивительным притягательным миром этой загадочной вереницы единиц. Свои сомнения в правильности разложения в отдельных случаях И. Бернулли отражает звёздочкой.


Рис. 1.

В течение первых ста лет, прошедших со времени опубликования таблицы И. Бернулли, в неё не было внесено особой ясности. В 1838 году Вестерберг разложил на простые множители число из 11 единиц — и это всё. В 1879 году французский математик Эдуард Люка находит простые делители для n = 17 и признаёт, что цепочка из 19 единиц не поддаётся разложению. В 1895 году в Париже выходит его книга «Занимательная арифметика», содержащая приведённую ниже таблицу.

Таблица 
111 = 3 · 37
1111 = 11 · 101
11111 = 41 · 271
111111 = 3 · 7 · 11 · 13 · 37
1111111 = 239 · 4649
11111111 = 11 · 73 · 101 · 137
111111111 = 3² · 37 · 333667
1111111111 = 11 · 41 · 271 · 9091
11111111111 = 1121649 · 513239
111111111111 = 3 · 7 · 11 · 13 · 37 · 101 · 9901
1111111111111 = 53 · 79 · 265371653
11111111111111 = 11 · 239 · 4649 · 909091
111111111111111 = 3 · 31 · 37 · 41 · 271 · 2906161
1111111111111111 = 11 · 17 · 73 · 101 · 137 · 5882353
11111111111111111 = 2071723 · 5363222357
111111111111111111 = 3² · 7 · 11 · 13 · 19 · 37 · 52579 · 333667

Угасший было интерес к числам, составленным из единиц, вновь возрос в последние годы, особенно в связи с развитием теории арифметических кодов, служащей основой для реализации методов помехоустойчивого кодирования в компьютерной технике (см., например, книгу Ю. Г. Дадаева «Теория арифметических кодов», изданную в Москве в 1981 г.). Наши загадочные числа, спустя почти двести лет после опубликования первой таблицы их делителей, приобретают, наконец, собственное имя. В «Занимательной теории чисел» (Нью-Йорк, 1964 г.) её автор А. Бейлер, посвятив этим числам целую главу под названием «111...1111», вводит для них термин «repunit» (сокращение английского repeated unit — повторенная единица). Русского слова «репьюнит» ещё не найти в словарях, но оно уже появляется в рефератах к зарубежным статьям, приобретая силу нового международного термина.

Математики продолжают штурмовать таблицу делителей репьюнитов, и к 1975 году n в таблице уже достигает 3000 (С. Ейтс), однако в ней ещё достаточно много пробелов. (К настоящему времени часть этих пробелов ликвидирована и найдены делители. репьюнитов до 162-го включительно). Отдельный интерес представляют простые репьюниты, поиск которых также продолжается. Уже доказано, что 19-й (1918 г.), 23-й (1929 г.), 317-й (1978 г.) и 1031-й (1985 г.) репьюниты простые.

Нас, однако, репьюниты интересуют не сами по себе, а в связи с периодами десятичных дробей. Существование связи между теми и другими предвидел и Бернулли, который одновременно с уже упоминавшейся таблицей делителей репьюнитов опубликовал обзор известных к тому времени результатов о периодах десятичных дробей, включавший в себя пространную таблицу этих периодов (см. рис. 2). В действительности, эта связь, как мы сейчас увидим, лежит на поверхности.


Рис. 2.

Делители репьюнитов и
представление обыкновенных дробей десятичными

Начнём с трёх простых наблюдений.

Наблюдение 1. Предположим, что число 999...999, составленное из n девяток, делится на данное натуральное число m. Запишем частное от деления в виде n-значного числа:

999...999

 m

 = 

a1a2a3...an


(где несколько первых цифр ai могут быть нулями). Тогда

1

 m

 = 0, a1a2a3...an a1a2a3...an ...

Доказательство.

m · 0, a1a2a3...an a1a2a3...an ... = 0, 999...999 999...999 ... = 1.

Наблюдение 2. Если число m не делится на 3, то делимость на m числа, составленного из n девяток, равносильна делимости на m числа, составленного из n единиц (т.е. репьюнита).

Это очевидно.

Наблюдение 3. Если число m не делится на 2 и на 5, то найдётся репьюнит, делящийся на m.

Доказательство. Будем последовательно находить остатки от деления на m чисел 1, 11, 111 и т.д. Последовательность этих остатков бесконечна, но в то же время для них имеется только m возможных значений (от О до m–1). Поэтому найдутся два разных репьюнита с одинаковыми остатками от деления на m («принцип Дирихле»!). Разность этих репьюнитов делится на m; в то же время она имеет вид 111...111 000...000, т.е. является произведением некоторого репьюнита на некоторую степень десятки 10k. Но число m взаимно просто с 10k; значит, последний репьюнит делится на m.

Теперь мы можем сформулировать Важный Результат.

Теорема 1. Если натуральное число m не делится на 2 и на 5, то период десятичной дроби, равной 1/m, начинается сразу после запятой. Его длина равна наименьшему n, при котором число, составленное из n девяток делится на m. Сам период равен частному от деления этого числа из девяток на m, записанному как n-значное число (возможно, с нулями в начале). Если m не делится и на 3, то можно также сказать, что длина периода равна номеру первого репьюнита, делящегося на m.

Всё это нами уже доказано. Между прочим, из этой теоремы вытекает следующий, довольно неожиданный результат.

Следствие. Если m не делится на 2, 3 и 5, то период десятичной дроби, равной 1/m, делится на 9.

Действительно, если m не делится на 3, то число 999...999/m делится на 9.

Утверждения о периодах в случаях, не охватываемых теоремой 1, мы приведём в качестве упражнений.

Упражнение 1. Пусть m = 2a5bm', где m' не делится ни на 2, ни на 5, и пусть c = max(ab). Тогда период десятичной дроби, равной 1/m, начинается с (c+1)-й позиции после запятой и имеет такую же длину, как период дроби 1/m'.

Доказательство этого утверждения опирается на лемму: если р и q взаимно просты, то найдутся целые положительные A и B такие, что Ap + Bq = 1.

Упражнение 2. Если р и q взаимно просты, то период десятичной дроби, равной p/q, имеет такую же длину, как период десятичной дроби 1/q.

Наконец, можно усилить наше следствие.

Упражнение 3. Если q не делится на 3, то при любом p период десятичной дроби, равной p/q, делится на 9.

Теперь мы приступаем к изучению зависимости длин периодов от знаменателей. В этом изучении нам поможет, наряду с теоремой 1,

Малая теорема Ферма

В отличие от своей «Великой теоремы» малую теорему Пьер Ферма снабдил доказательством: он изложил его в 1640 году в одном из писем. Теорема формулируется так:

Если p — простое число и a — произвольное натуральное число, не делящееся на p, то ap–1 – 1 делится на p.

Мы не приводим доказательства этой теоремы (хотя читатель, который проделает все упражнения к этой статье, вероятно сможет её доказать). Её доказательство имеется в популярной литературе (см., например, книгу Р. Куранта и Г. Роббинса «Что такое математика?», переизданную в Москве в 1976 г.). Нас эта теорема интересует, главным образом, как средство доказательства фундаментального свойства периодов.

Длина периода дроби с простым знаменателем

Теорема 2. Если p есть простое число, отличное от 2 и 5, то длина периода дроби 1/p является делителем числа p–1.

Доказательство. Согласно теореме 1, длина периода есть наименьшее число n такое, что число, составленное из n девяток делится на p. В то же время в силу малой теоремы Ферма число 10p–1 – 1, т.е. число, составленное из p–1 девяток, делится на p. Мы должны доказать, что p–1 делится на n. Если n = p–1, то доказывать нечего; предположим, что n < p–1. Числа, составленные из p–1 и n девяток, делятся на p; дополним второе из них нулями до (p–1)-значного числа и составим разность полученных чисел:

  999...999 999...999
999...999 000...000
999...999

Это число составлено из p–1–n девяток, и оно тоже делится на p. Проделав ещё одно подобное вычитание, мы находим, что на p делится число, составленное из p–1–2n девяток, потом — из p–1–3n девяток и т.д. В конце концов мы придём к числу, в котором девяток меньше, чем n, и тут есть две возможности. Либо это число вообще будет нулём, но это как раз и значит, что p–1 делится на n. Либо в этом числе девяток будет больше 0, но меньше n; а это противоречит тому, что n — наименьшая возможная длина числа из девяток, которое делится на p. Теорема доказана.

Обозначим для числа m через L(m) длину периода десятичной дроби, равной 1/m. Мы доказали, что если p — простое число, то L(p) есть делитель числа p–1. Но какой? Посмотрим на таблицу И. Бернулли (рис. 2). Мы видим, что L(3) = 1, L(7) = 6, L(13) = 6, L(17) = 16, L(31) = 15, L(41) = 5 и т.д. Ясности не много.

С точки зрения соотношения между длиной периода дроби 1/p и самим p все простые числа p подразделяются на три категории:

  1. «полнопериодные» простые, у которых длина периода на 1 меньше знаменателя: 7 (L = 6), 17 (L = 16), 19 (L = 18), 23 (L = 22), 29 (L = 28) и т.д.;
  2. «неполнопериодные» простые с нечётной длиной периода: 3 (L = 1), 31 (L = 15), 37 (L = 3), 41 (L = 5) и т.д.;
  3. «неполнопериодные» простые с чётной длиной периода: 11 (L = 2), 13 (L = 6), 73 (L = 8), 89 (L = 44), 101 (L = 4) и т.д.;

Кропотливая работа математиков по выявлению какой-нибудь закономерности в расположении этих групп среди всех простых чисел увенчалась неожиданным результатом. Было обнаружено достаточно устойчивое отношение численностей этих групп в пропорции 9:8:7; при этом были использованы таблицы длин периодов для простых знаменателей до 1 370 471 включительно (С. Ейтс, 1975 г.). Были получены и другие общие результаты, причём оказалось, что большое значение при определении длины периода дроби 1/p с простым p имеет остаток от деления числа p на ... 40. Например, если этот остаток равен 3, 27, 31, 39, то L(p) нечётно, а если p = 40k ± 7, ±11, ±17, ±19, то L(p) чётно. Всё же задача вычисления чисел L(p) для простых p, видимо, далека от решения.

Случай непростого знаменателя

Упражнение 4. Если p1 и p2 взаимно просты между собой и с 10, то L(p1p2) есть наименьшее общее кратное чисел L(p1) и L(p2).

Поскольку всякое натуральное число есть произведение степеней простых, которые между собой взаимно просты, последнее утверждение сводит задачу вычисления длины периода к случаю, когда знаменатель есть степень простого числа. А здесь снова нет ясности: например, L(3) = 1, L(9) = 1; L(7) = 6, L(49) = 42; и т.д.

Теперь нам пора оставить длины периодов и обратиться к объяснению феноменов, обнаруженных в начале статьи.

Эффект круговой перестановки

Напомним, в чём он состоит. Мы видели, что шестизначный период дроби 1/7 при умножении на 2, 3, 4, 5, 6 подвергается круговой перестановке: сколько-то цифр из конца числа переезжает в начало. Несколько иначе ведёт себя при умножении на различные числа шестизначный период дроби 1/13; а именно, ... Впрочем, что именно с ним происходит, читатель может вспомнить, заглянув в начало статьи, а мы сейчас докажем теорему, более или менее объясняющую это явление.

Теорема 3. Пусть N есть период дроби 1/m (записанный как число, возможно, начинающееся одним или несколькими нулями), где m взаимно просто с 10, и пусть l есть остаток от деления числа 10k на m. Тогда число lN получается из числа N перестановкой k цифр из начала числа в конец.

Доказательство. Пусть M есть целая часть числа 10k/m, т.е. 10k = Mm + l. Умножим десятичную дробь 1/m на 10k; при этом запятая переедет на k позиций влево. Целая часть получившегося числа — это M. Отбросим целую часть. Получится число

10k 1 

 m

 M 10kMm

 m

 =  l 

 m


Это периодическая десятичная дробь, период которой получается из периода дроби 1/m круговой перестановкой цифр: k цифр переезжает из начала в конец; но в то же время это число в l раз больше числа 1/m, а значит, и его период в l раз больше периода числа 1/m, т.е. N. Теорема доказана.

Если число 1/m имеет (m–1)-значный период, то доказанная теорема всё объясняет. Действительно, круговыми перестановками цифр из периода можно получить m–1 чисел (включая его самого), и все эти числа различны. С другой стороны, умножая период на 1, 2, ..., m–1, мы тоже получаем m–1 чисел; значит, это в точности те же числа. Если же период короче, то круговые перестановки цифр периода N не исчерпывают всех чисел вида lN с 1 ≤ l ≤ m–1. Всё, что можно сказать в этом случае — это что круговая перестановка цифр числа lN всегда приводит к числу вида l'N — это доказывается точно так же, как теорема 3.

Интересно, что теорема 3 в некотором смысле обращается:

Теорема 4. Пусть N есть целое число (запись которого, возможно, начинается нулём или несколькими нулями), и пусть A есть число, составляемое последними k цифрами числа N. Предположим, что при перенесении k знаков из конца числа N в начало оно превращается в число lN, где l целое. Тогда периодическая десятичная дробь 0,NNN... равна A/(10kl – 1). (Последняя дробь может оказаться сократимой.)

Доказательство. Пусть n — число знаков числа N. При перенесении k знаков из конца числа N в начало оно превращается в число

NA

10k

 + A·10nk.

Таким образом,

NA

10k

 + A·10nk = lN,
NA + A·10n = lN·10k,
N(10nk l – 1)

A

 = 10n – 1,

откуда

0,NNN...· 10nk l – 1

A

 = 0,999... = 1,

что нам и требуется.

Сами того не желая, мы научились решать один тип олимпиадных задач. Вот пример.

Задача. Найти все шестизначные числа, которые увеличиваются в целое число раз при перенесении последней цифры из конца в начало. (Мы будем считать, как это обычно делается, что число начинается не с нуля; решить-то задачу мы можем и без этого предположения, но ответ будет чересчур громоздок: он будет включать в себя числа 000001, 000002, ..., 000009, 000011, 000013, ... Мы будем также понимать слово «увеличивается» буквально, т.е. исключим случай, когда число остаётся при перенесении цифры неизменным; в противном случае в ответ вошли бы числа 111111, 222222, ..., 999999.)

Решение. Пусть A — последняя цифра нашего числа, и пусть при её перенесении в начало число увеличивается в l раз. Таким образом, 1≤A≤9, 2≤l≤9. В силу теоремы 4 наше число есть шестизначный период (возможно, сократимой) дроби A/(10l–1). Знаменатель этой дроби до сокращения может быть одним из чисел 19, 29, 39, ..., 89; после сокращения на однозначное число знаменатель может превратиться ещё в 39 : 3 = 13, 49 : 7 = 7, 69 : 3 = 23. Так как период дроби шестизначный, знаменатель должен быть делителем числа 999999 = 33·7·11·13·37 (см. теорему 1). Это оставляет для него только три возможности: 7, 13, 39. Таким образом, l равно 4 или 5. При l = 4 наша дробь равна A/39, где A = 4, 5, ..., 9 (дробь должна быть больше 0,1, поскольку период не должен начинаться с нуля). Период такой дроби есть A·25641 (период дроби 1/39 есть 025641). При l = 5 дробь равна A/49 и должна сокращаться на 7, что оставляет для неё единственную возможность: 1/7; период равен 142857. Итак,

Ответ: 102564, 128205, 142857, 153846, 179487, 205128, 230769.

Упражнение 5. Решите аналогичную задачу для 13-значных чисел.

Указание. Воспользуйтесь таблицей делителей репьюнитов.

Эффект девяток

Теорема 5. Пусть q — простое число, большее 5, и пусть 1 ≤ p ≤ q. Предположим, что период дроби p/q есть 2n-значное число N. Далее, обозначим через N1 число, образуемое первыми n цифрами периода, и через N2 число, образуемое его последними n цифрами. Тогда N1 + N2 = 999...999 (n девяток).

Доказательство. По условию,

 N = 10nN1 + N2,       p

 q

 =  N

102n – 1

,

и, следовательно,

 p(102n – 1) = Nq = (10n – 1)N1q + (N1 + N2)q,
(N1 + N2)q = (10n – 1)((10n + 1)pN1q).

Поскольку 2n есть наименьшее k, при котором 10k–1 делится на q, 10n–1 не делится на q, а так как q — простое число, то 10n–1 взаимно просто с q. Значит, N1 + N2 делится на 10n–1. Но в то же время N1 и N2 это n-значные числа, которые не оба состоят из одних девяток. Значит, N1 + N2 < 2(10n – 1), и, таким образом, N1 + N2 = 10n – 1, что и требовалось доказать.

Заметим, что простота q использовалась нами только в одном месте: мы вывели из неё, что 10n–1 взаимно просто с q. Разумеется, эта взаимная простота может наступить и при составном q, так что заключение нашей теоремы справедливо и при многих непростых знаменателях.

Ещё один эффект

Рассмотрим снова период дроби 1/7: N = 142857. Возведём его в квадрат (N 2 = 20 408 122 449), отделим последние шесть цифр и сложим с тем, что останется:

122449 + 20408 = 142857.

Получился снова наш период. Проделаем подобное с периодом числа 1/17:

05882352941176472 = 346020761245674671280276816609,
4671280276816609 + 34602076124567 = 4705882352941176.

Получился, правда, не наш исходный период, но число, отличающееся от него на круговую перестановку цифр. Аналогичное для периода дроби 1/19:

0526315789473684212 = 2770083102493074786703601108033241,
786703601108033241 + 2770083102493074 = 789473684210526315.

Упражнение 6. Дайте этому объяснение.


Hosted by uCoz