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

О чем же идет речь?

Как известно любая дробь вида \(\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, и их периодов 

 

 

 

 

Copyright © 2021 AbakBot-online calculators. All Right Reserved. Author by Dmitry Varlamov