В материале рассмотрим тему из теории чисел: простые дроби и их свойства. Тема достаточно интересная, не до конца изученная и думаю, будет интересно взглянуть на неё еще раз.
О чем же идет речь?
Как известно любая дробь вида \(\cfrac{1}{N}\), где N - натуральное (целое и положительное) число, и не имеющая в множителях числа 2 и 5 - обладает таким свойством как период.
Например в числах
\(\cfrac{1}{13}=0.07692307692307692307692307692308\)
\(\cfrac{1}{41}=0.02439024390243902439024390243902\)
\(\cfrac{1}{101}=0.00990099009900990099009900990099\)
\(\cfrac{1}{91}=0.01098901098901098901098901098901\)
Несложно заметить, что в правой части числа повторяются
для числа \(13\) это \(076923\), для \(41\) это \(02439\), для \(101\) это \(0099\), для \(91\) это \(010989\)
Это и есть период числа. Основная задача, связанная с нахождением периода дробей - это то что они не подчинены какому то известному правилу.
То есть у дроби числа 17 период равен 16, а период числа 11 уже равен 2. У числа 7 период 6, а у \(7^2\) равен 42.
Как же можно определить период простой дроби?
Используем утверждение что для любого простого числа p, кроме 2 и 5, верно утверждение
\(10^{p-1}mod p=1\)
То есть, взяв остаток от десяти в 18 степени при делении его на 19 мы получим единицу (1)
Это работает всегда и на всех числах взаимно простых с десятью. В общем виде это называется - малая теорема Ферма, а мы лишь рассмотрели частный случай где основание равно 10.
Так вот период простой дроби всегда! кратен числу \({p-1}\)
Судите сами
Число 11 \(p-1=10\) а период равен 2
число 41 \(p-1=40\) а период равен 5
число 101 \(p-1=100\) а период равен 4
число 19 \(p-1=18\) а период равен 18
число 6 \(p-1=6\) а период равен 6
Кроме этого, обозначив период буквой \(T\) мы легко можем доказать что \(10^{T}mod p=1\)
Таким образом, возводя 10 в степень 1,2,3..... и деля его на заданное простое число мы получаем остатки.
Как только остаток равен 1 - всё, мы нашли период простой дроби.
Простой перебор хорошо работает на сравнительно небольших числах, а что делать когда когда простая дробь имеет в своем знаменателе число из десятков цифр?
Необходимо разложить \(p-1\) на множители и перебрать все сочетания множителей, для того что бы подставить значение в степень.
Мы остановимся на полном переборе, только лишь для того что бы рассчитать не только период, но и определить все цифры в этом периоде.
Как это делаю я?
Представим \(10^{p-1}mod p=1\) как \(10*M=1+p*K\), где \(K\) и \(M\) - какие то целые числа.
Получили линейное диофантово уравнение с двумя переменными
Давайте сразу на примере, Возьмем число 41.
Итак первый шаг
\(10M-41P=1\) Заменим \(P\) на \(-P\), да бы избавится от минуса.
Решая уравнение \(10M-41P=1\) мы получим что \(M=37+41R\)
Зная, что \(M\) - это степень десятки - мы можем представить как \(M=10W\)
то есть \(10W=37+41R\), где \(R\) и \(W\) - какие то целые числа.
То есть снова получили диофантово уравнение, которое так же решаем.
Не проходя каждый шаг, я Вам напишу какие же числа получаются 1,37,16,18,10,1,37....
Заметили что сделав 5 итераций, мы вернулись к исходной единице? Так вот - это количество и есть период простой дроби.
В принципе пока ничего сложного, более того читатель скажет: "и в чем же смысл, я также могу и десять возводить в степень и брать остаток, и получится даже быстрее"
Совершенно согласен, но речь идет в материале немного о другом - о более широком понимании простых дробей и их периодов.
Но раз уж захотели брать остатки...
Диофантово уравнение решать на каждом этапе конечно же не очень удобно, а как можно это упростить?
Вычислив первый раз значение остатка 37, нам в принципе решать диофантово уравнение нет необходимости. Мы просто берем остатки от числа 37 в степени,2,3,4.... при делении его на 41
\(37^{0}mod 41=1\)
\(37^{1}mod 41=37\)
\(37^{2}mod 41=16\)
\(37^{3}mod 41=18\)
\(37^{4}mod 41=10\)
Такая схема уже сравнима с простым перебором как предложил неизвестный читатель.
Что еще можно вытащить из алгоритма что использует диофантовы уравнения?
Например мы можем узнать все цифры в периоде.
\(10*M=1+p*K\) решая это уравнение мы нашли чему равно \(M\) но не нашли чему равно \(K\)
при \(p=41\)
\(K=9\)
Теперь умножая каждый остаток \(1, 37, 16, 18, 10\) на \(K\) и беря последнюю цифру, мы получим значение периода, который "перевернут" то есть читается не справа налево, а слева направо.
в нашем примере это будет \(9, 3, 4, 2, 0\)
то есть период дроби равен 0.(02439)
Теперь рассмотрим на примере дроби \(\cfrac{1}{117}\)
1. Решая диофантовое уравнение \(10*M+117*K=1\), получим пару значений \(M=82, K=7\). Последняя цифра в периоде будет 7
2. \(82^{2}mod 117=55\) , Значит \(M=55\) а предпоследняя цифра в периоде будет \(82*7mod 10=4\) 4(четыре)
3. \(82^{3}mod 117=64\) , Значит \(M=64\) а предыдущая цифра в периоде будет \(55*7mod 10=5\) 5(пять)
3. \(82^{4}mod 117=100\) , Значит \(M=100\) а предыдущая цифра в периоде будет \(64*7mod 10=8\) 8(восемь)
3. \(82^{4}mod 117=10\) , Значит \(M=10\) а предыдущая цифра в периоде будет \(100*7mod 10=0\) 0(ноль)
3. \(82^{5}mod 117=1\) , Значит \(M=1\) а и первая цифра в периоде будет \(10*7mod 10=0\) 0(ноль)
Раз мы достигли \(M=1\) на 5 шаге, следовательно наш период равен 6-ти.
И наш ответ \(\cfrac{1}{117}=0.008547008547005847008547.......\)
Предлагаем для ознакомления таблицу простых чисел до 1500, и их периодов