Период дроби |
Цифры периода |
В этом материале рассмотрим тему из теории чисел: простые дроби и их свойства. Тема достаточно интересная, не до конца изученная и думаю, будет интересно взглянуть на неё еще раз.
О чем же идет речь?
Как известно любая дробь вида \(\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, и их периодов
Число |
Период |
Число |
Период |
Число |
Период |
3 |
1 |
421 |
140 |
947 |
473 |
7 |
6 |
431 |
215 |
953 |
952 |
11 |
2 |
433 |
432 |
967 |
322 |
13 |
6 |
439 |
219 |
971 |
970 |
17 |
16 |
443 |
221 |
977 |
976 |
19 |
18 |
449 |
32 |
983 |
982 |
23 |
22 |
457 |
152 |
991 |
495 |
29 |
28 |
461 |
460 |
997 |
166 |
31 |
15 |
463 |
154 |
1009 |
252 |
37 |
3 |
467 |
233 |
1013 |
253 |
41 |
5 |
479 |
239 |
1019 |
1018 |
43 |
21 |
487 |
486 |
1021 |
1020 |
47 |
46 |
491 |
490 |
1031 |
103 |
53 |
13 |
499 |
498 |
1033 |
1032 |
59 |
58 |
503 |
502 |
1039 |
519 |
61 |
60 |
509 |
508 |
1049 |
524 |
67 |
33 |
521 |
52 |
1051 |
1050 |
71 |
35 |
523 |
261 |
1061 |
212 |
73 |
8 |
541 |
540 |
1063 |
1062 |
79 |
13 |
547 |
91 |
1069 |
1068 |
83 |
41 |
557 |
278 |
1087 |
1086 |
89 |
44 |
563 |
281 |
1091 |
1090 |
97 |
96 |
569 |
284 |
1093 |
273 |
101 |
4 |
571 |
570 |
1097 |
1096 |
103 |
34 |
577 |
576 |
1103 |
1102 |
107 |
53 |
587 |
293 |
1109 |
1108 |
109 |
108 |
593 |
592 |
1117 |
558 |
113 |
112 |
599 |
299 |
1123 |
561 |
127 |
42 |
601 |
300 |
1129 |
564 |
131 |
130 |
607 |
202 |
1151 |
575 |
137 |
8 |
613 |
51 |
1153 |
1152 |
139 |
46 |
617 |
88 |
1163 |
581 |
149 |
148 |
619 |
618 |
1171 |
1170 |
151 |
75 |
631 |
315 |
1181 |
1180 |
157 |
78 |
641 |
32 |
1187 |
593 |
163 |
81 |
643 |
107 |
1193 |
1192 |
167 |
166 |
647 |
646 |
1201 |
200 |
173 |
43 |
653 |
326 |
1213 |
202 |
179 |
178 |
659 |
658 |
1217 |
1216 |
181 |
180 |
661 |
220 |
1223 |
1222 |
191 |
95 |
673 |
224 |
1229 |
1228 |
193 |
192 |
677 |
338 |
1231 |
41 |
197 |
98 |
683 |
341 |
1237 |
206 |
199 |
99 |
691 |
230 |
1249 |
208 |
211 |
30 |
701 |
700 |
1259 |
1258 |
223 |
222 |
709 |
708 |
1277 |
638 |
227 |
113 |
719 |
359 |
1279 |
639 |
229 |
228 |
727 |
726 |
1283 |
641 |
233 |
232 |
733 |
61 |
1289 |
92 |
239 |
7 |
739 |
246 |
1291 |
1290 |
241 |
30 |
743 |
742 |
1297 |
1296 |
251 |
50 |
751 |
125 |
1301 |
1300 |
257 |
256 |
757 |
27 |
1303 |
1302 |
263 |
262 |
761 |
380 |
1307 |
653 |
269 |
268 |
769 |
192 |
1319 |
659 |
271 |
5 |
773 |
193 |
1321 |
55 |
277 |
69 |
787 |
393 |
1327 |
1326 |
281 |
28 |
797 |
199 |
1361 |
680 |
283 |
141 |
809 |
202 |
1367 |
1366 |
293 |
146 |
811 |
810 |
1373 |
686 |
307 |
153 |
821 |
820 |
1381 |
1380 |
311 |
155 |
823 |
822 |
1399 |
699 |
313 |
312 |
827 |
413 |
1409 |
32 |
317 |
79 |
829 |
276 |
1423 |
158 |
331 |
110 |
839 |
419 |
1427 |
713 |
337 |
336 |
853 |
213 |
1429 |
1428 |
347 |
173 |
857 |
856 |
1433 |
1432 |
349 |
116 |
859 |
26 |
1439 |
719 |
353 |
32 |
863 |
862 |
1447 |
1446 |
359 |
179 |
877 |
438 |
1451 |
290 |
367 |
366 |
881 |
440 |
1453 |
726 |
373 |
186 |
883 |
441 |
1459 |
162 |
379 |
378 |
887 |
886 |
1471 |
735 |
383 |
382 |
907 |
151 |
1481 |
740 |
389 |
388 |
911 |
455 |
1483 |
247 |
397 |
99 |
919 |
459 |
1487 |
1486 |
401 |
200 |
929 |
464 |
1489 |
248 |
409 |
204 |
937 |
936 |
1493 |
373 |
419 |
418 |
941 |
940 |
1499 |
214 |