В материале рассмотрим тему из теории чисел: простые дроби и их свойства. Тема достаточно интересная, не до конца изученная и думаю, будет интересно взглянуть на неё еще раз.
О чем же идет речь?
Как известно любая дробь вида \(\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 |