vened Aug 13 at 17:13

Вычисление периода записи дробной части числа в позиционных системах счисления

Medium

7 min

1.2K

Mathematics * Algorithms * Programming *

FAQ

В статье о шумерских цифрах и их влиянии на арифметику я отметил, что запись рационального числа $\frac{1}{7^{11}}$ в шестнадцатеричной системе имеет период шестнадцатеричных цифр и предложил проверить это на калькуляторе. Речь про период цифр записи дробной части чисел вида $\frac{1}{q}$ . Всякое рациональное число в такой позиционной системе счисления имеет либо конечную запись (терминирующуюся, например, или ), либо бесконечную периодическую запись (например, $\frac{1}{13} \approx 0.076923(076923)\ldots$ ).

Однако числа $7^{11}$ и выглядят слишком большими, чтобы выписывать цифры в соответствующих количествах: сколько страниц потребуется для миллиона десятичных цифр мелким шрифтом? Реально ли такую проверку проделать на обычном калькуляторе за разумное время? Да, не сомневайтесь — реально.

Проверка «частичного» случая, как мы увидим ниже, вообще может быть проделана без калькулятора, «на салфетке», вручную. С общей проверкой, для данных конкретных чисел — не сильно-то сложнее. Ручных вычислений это не отменяет, но с калькулятором несколько удобнее. Ниже разберёмся, как тут калькулятор использовать и почему это вообще работает. Зачем? Дело в том, что знакомство с арифметикой в числах помогает понять некоторые важнейшие математические механизмы, которые, кстати, самым прямым образом применяются в современной криптографии – это можно сказать о всех описанных ниже соотношениях и теоретико-числовых алгоритмах.

Какой именно калькулятор подходит? Примем, что это любой современный качественный калькулятор. Даже приложение в смартфоне. Убедитесь, впрочем, что выбранное приложение-калькулятор работает правильно: например, выражение $-3^{2}$ («минус, три, в квадрате») должно на калькуляторе давать результат (минус девять), а то всякое случается.

Подходящий калькулятор должен иметь хотя бы десятичных разрядов, должен складывать и вычитать, умножать и делить (с какой-то точностью «после запятой»), а ещё, желательно, возводить в степень с целым показателем и показывать двоичное представление целого числа (двоичных разрядов должно быть, скажем, или более). И это, по нынешним временам, весьма скромные, — если не сказать типовые, — требования к калькулятору.

Естественно, вычисления опираются на некоторые арифметические свойства натуральных чисел. Поэтому потребуется арифметика остатков и пара привычных для данной области теорем: основная теорема арифметики и теорема Эйлера-Ферма (если совсем строго, то это теорема Лагранжа из теории групп, но пусть будет теорема Эйлера, так привычнее). Все арифметические теоремы используются здесь без доказательств.

Итак, мы изучаем запись $\frac{1}{q}$ . Например, $\frac{1}{7} \approx 0.142\ldots$ . Прежде всего, нужно разобраться, как вообще можно посчитать период записи дробной части. Исходная задача касается шестнадцатеричной системы счисления, но начнём с более привычной — с десятичной. Далее, для десятичного случая, рассматриваем только взаимно простые с знаменатели.

Пусть,

$\frac{1}{q} = 0.\underbrace{d_{1}{\cdots}d_{l}}_\text{n раз}d_{1}d_{2}d_{3}{\cdots}$

— то есть, $\frac{1}{q}$ имеет десятичную запись, в которой десятичные цифры ${d_{l}\ldots}$ повторяются с периодом .

Умножим обе части равенства на $10^{n}$ :

$\frac{10^{n}}{q} = \underbrace{d_{1}{\cdots}d_{l}}_\text{n}.d_{1}d_{2}d_{3}{\cdots}$

Теперь вычтем $\frac{1}{q}$ , вспомнив, что это как раз будет дробная часть в десятичной записи справа:

$\frac{10^{n}}{q} – \frac{1}{q} = \underbrace{d_{1}{\cdots}d_{l}}_\text{n раз}$

Умножим на :

$10^{n} – 1 = \underbrace{d_{1}{\cdots}d_{l}}_\text{n раз}*{q}\quad\quad(1)$

Откуда:

$\frac{1}{q} = \frac{\overbrace{d_{1}{\cdots}d_{l}}^\text{n раз}}{10^{n}-1}.$

Здесь искомый период записи — это показатель степени при основании системы счисления.

Пример. То же самое, но десятичными цифрами для $\frac{1}{13}$ , где :

$\frac{1}{13} = 0.076923(076923)\ldots$ $\frac{10^{6}}{13} = 076923.076923(076923)\ldots$ $\frac{10^{6}-1}{13} = 76923$ $\frac{1}{13} = \frac{76923}{10^{6}-1}.$

Сходится.

Чтобы определить период, нам нужно найти подходящее значение показателя степени . Что такое «подходящее» значение? Вернёмся к формуле (1) и перенесём единицу в правую часть:

$10^{n} = \underbrace{d_{1}{\cdots}d_{l}}_\text{n раз}*{q} + 1.$

Обратите внимание, тут справа стоит число, кратное и к нему прибавляем единицу: то есть, здесь просто написано, что $10^{n}$ даёт остаток при делении на . Это ключевое наблюдение.

Нужно найти такое , что

$10^{n} \equiv 1\pmod{q}.$

В этой формуле намётанный глаз тут же видит теорему Эйлера (ну или, хотя бы, Ферма):

$a^{\varphi{(q)}} \equiv 1\pmod{q},$

$\varphi{(q)}$ — это функция Эйлера. Значение этой функции для — количество взаимно простых с целых положительных чисел, меньших или равных . Выше мы договорились, что — взаимно простое с , то есть, с основанием системы, c . Все значения здесь — натуральные числа, по построению. В случае исходной задачи, по основанию , всё это выполняется для $7^{11}$ , так что теорема Эйлера, для которой как раз и требуется, чтобы и были взаимно простыми натуральными числами, нам хорошо подходит. (Кстати, эта же теорема Эйлера прямо используется в криптосистеме RSA.)

Из формулы видно, что как минимум одно искомое значение равно $\varphi{(q)}$ . Это всегда так, но нужно учитывать, что могут подходить и показатели меньше, чем $\varphi{(q)}$ .

Мы пока что определили, как вычислить нужный период в принципе. Теперь вернёмся к исходной задаче. Мы хотим проверить, что период шестнадцатеричной записи для $\frac{1}{7^{11}}$ равен . Соответственно, здесь $q = 7^{11}$ , .

Сложно ли вычислить значение $\varphi{(q)}$ для $q = 7^{11}$ ? Нет, это элементарно делается на нашем калькуляторе. Возьмём формулу для $\varphi{(q)}$ :

$\varphi{(q)} = q\prod_{p\mid q}\left(1-{\frac{1}{p}}\right).$

Выглядит пугающе: произведение считается по всем простым числам, которые делят . Формула может показаться сложной, а нахождение простых при помощи калькулятора – нетривиальной задачей. Однако в нашем случае, для $7^{11}$ , такое простое только одно – это . Считаем на калькуляторе:

$\varphi{(7^{11})} = 7^{11}*(1-{\frac{1}{7}}) = 7^{11} – 7^{10} = 1694851494.$

Нашли нужный показатель степени: . Это означает, что

$16^{1694851494} \equiv 1\pmod{7^{11}}.$

Вывести значение $16^{1694851494}$ , пусть и в шестнадцатеричной системе, никакой калькулятор не сможет. Но это не страшно, так как мы будем проверять другим способом, работая только с показателями степени и с остатками. Нам могут подойти и другие значения, которые меньше $\varphi{(7^{11})} = 1694851494$ . Функция Эйлера мультипликативна, то есть, $\varphi{(a*b)} = \varphi{(a)}\varphi{(b)}$ (, – взаимно простые). Все подходящие нам числа должны быть делителями значения функции Эйлера (обратное — не верно). Соответственно, чтобы продолжить проверку на калькуляторе, нам нужно найти наименьшее подходящее только среди делителей $\varphi{(7^{11})} = 1694851494$ .

Как найти эти делители на калькуляторе? Сколько их? — довольно большое значение. Перебирать вручную числа, вводя их на калькуляторе, — долго. Поэтому смотрим ещё раз на формулу, по которой вычислили $\varphi{(7^{11})}$ , и переписываем доли единицы несколько иначе, чтобы получить все простые делители числа (пригодилась основная теорема арифметики):

$\varphi{(7^{11})} = 7^{11}*(1-{\frac{1}{7}}) = 7^{11}*\frac{6}{7} = \frac{7^{11}*6}{7} = 7^{10}*3*2 = 1694851494.$

Простые делители: , , (но в десятой степени). Это означает, что все собственные делители , — то есть, кроме самого числа и единицы, — представляют собой произведения этих простых в разных сочетаниях, но с учётом показателей степени вхождения и коммутативности умножения. У нас $7^{10}*3*2$ , то есть, показатели степеней: , , . Следовательно, количество делителей равно , а если взять только собственные, то получится ровно (кто бы сомневался!).

По условиям задачи, исходный показатель периода равен . (легко проверяем на калькуляторе). То есть, число входит в список делителей $\varphi{(7^{11})}$ . Из того, что это половина максимального значения, понятно, что и само максимальное значение тоже будет образовывать «период», раз периодом является его половина. Так что уже проверили частный случай.

Вспомним полную формулировку: утверждается, что запись рационального числа ${\frac{1}{7^{11}}}$ в шестнадцатеричной системе имеет период шестнадцатеричных цифр. Чтобы подтвердить это, нужно проверить, что

$16^{847425747} \equiv 1\pmod{7^{11}}$

или

$16^{847425747} – 1 = k*7^{11},\quad k \in \mathbb{N}.$

Как это сделать? Здесь мы имеем дело с возведением в степень по модулю. В криптографии это, например, та же RSA, где показатели степеней несравнимо больше нашего значения. Поэтому, для возведения в степень по модулю натурального числа используются быстрые алгоритмы: с удвоением экспоненты и так далее. Для относительно небольшого показателя такой алгоритм можно применить и на калькуляторе, но, всё же, возни будет слишком много. В нашем случае — есть гораздо более быстрый метод.

Посмотрим ещё раз на используемые числа. $16 = 2^{4}$ . То есть, все наши огромные степени , если рассматривать их в двоичной записи, это всего лишь один бит, установленный на позиции с нужным весом, а остальные биты — нулевые. Например,

$N = 16^{3} = 2^{4*3} = 2^{12} = 1000000000000_{2}$

— единица и нулей в двоичной системе. Мы хотим, чтобы наше искомое число при делении на $7^{11}$ давало в остатке единицу, а это эквивалентно тому, что делится на $7^{11}$ , то есть, $N - 1 = k*7^{11}$ .

записывается в двоичной системе как единица с большим количеством нулей справа. Если из этого числа вычесть единицу, то, при записи в двоичной системе, мы получим уже последовательность единиц, длина которой равна количеству нулей в записи . Пример: $N = 1000000000000_{2}$ , тогда $N – 1 = 111111111111_{2}$ . Это, очевидно, всегда так в двоичной системе.

Теперь достаточно найти признак делимости на $7^{11}$ для чисел, которые записываются непрерывным потоком единиц в двоичной системе. Да, поскольку $16 = 2^{4}$ , нам нужно рассматривать $(2^{4})^N = 2^{4*N}$ . Так что дальше рассматриваем просто степени двойки, и $2^{m} - 1$ (биты-единицы). Заметьте, кстати, что ${111111111}_{2} = {777}_{8}$ : в восьмеричной системе каждая тройка двоичных битов-единиц записывается цифрой семь. Это всё удачное «совпадение». Воспользуемся этим совпадением вместо того, чтобы вспоминать быстрые алгоритмы возведения в степень по модулю и подсчитывать экспоненты на калькуляторе.

В двоичной системе это ${111}_{2}$ . А поэтому набор двоичных единиц, чтобы делиться на $7^{11}$ , должен иметь длину $7^{10}*3$ . Это проще всего понять следующим образом: ${111}_{2}$ делится на ; все нужные нам числа, из троек двоичных единиц, получаются умножением на $2^{3}$ и прибавлением . А чтобы число такого вида — то есть, представимое последовательностью только из двоичных единиц, — делилось на $7^{2}$ , оно должно записываться семью тройками единиц, а именно, двоичная единица. Проверяем: $2^{21} – 1 = 2097151; 2097151/7^{2} = 42799$ .

Для того, чтобы три раза разделить на , — то есть, на $7^{3}$ , — запись должна содержать $7^{2}*3$ единиц. И так далее. Например, мы только что выяснили, что число

${\overbrace{111111111111111111111}^\text{21 единица}}_{2}$

делится на $7^{2}$ . Обозначим это число j. Теперь, чтобы добавить ещё одну степень семёрки в делители, потребуется $7^{2}*3 = 147$ единиц. В двоичном виде такое число можно построить следующим образом: возьмём j и умножим на $2^{6*21}$ — таким образом мы сдвинули блок из 21 двоичной единицы на позиций влево, добавив справа нулей. Чтобы превратить нули в единицы, нужно к получившемуся числу прибавить $j*2^{5*21}$ и так далее: $j*2^{4*21}, j*2^{3*21}\ldots$ Но каждое слагаемое кратно j, а j делится на 7. Значит, вся сумма тоже делится на 7 и эту семёрку можно вынести «за скобки», получив дополнительную степень: $7^{n + 1}$ . Так же строятся и числа для следующих степеней 7. (Можно строго доказать по индукции.)

Итак, мы нашли нужный нам признак делимости: чтобы число, записанное последовательностью двоичных единиц, делилось на $7^{11}$ , количество единиц в записи должно делиться на $7^{10}*3$ (заметьте, что этот же признак можно вывести другим способом).

Казалось бы, чтобы проверить делимость для нашего значения функции Эйлера (), нужно смотреть на элементы списка делителей и выбирать те, что делятся на три. Это не так сложно, но, всё же, — там ведь сорок два числа! Однако не нужно их все перебирать. Вспомните, что мы перебираем делители числа, которое записывается как $7^{10}*3*2$ (по построению, см. выше). Нам подходят только те числа, которые делятся и на $7^{10}$ , и на . Ну, так тут таких только два: $7^{10}*3$ и $7^{10}*6$ . Выбираем наименьшее: $7^{10}*3 = 847425747$ – это и есть искомый ответ: да, поскольку наименьший из делителей значения функции Эйлера для $7^{11}$ , а $16^{847425747} – 1 \equiv 0 \pmod{7^{11}}$ , период шестнадцатеричных цифр записи дробной части $\frac{1}{7^{11}}$ равен . Это сразу и частный, и общий ответ, потому что мы выбрали наименьшее из двух возможных чисел.

Полученный ответ – ${7^{10}*3}$ , — конечно, кратен периоду , соответствующему записи $\frac{1}{7}$ (первая степень ) в шестнадцатеричной системе. Для $\frac{1}{7}$ период записи можно вычислить по той же формуле, которую мы вывели выше.