| Integer, no more than 50,000. Having no multipliers of 2 and 5. |
|
|
| Fraction period |
| Period numbers |
In this article, we will consider a topic from number theory: simple fractions and their properties. The topic is quite interesting, not fully studied and I think it will be interesting to look at it again.
What is it about?
As you know, any fraction of the form \(\cfrac{1}{N}\), where N is a natural (integer and positive) number, and does not have the numbers 2 and 5 in the multipliers, has such a property as a period.
For example in numbers
\(\cfrac{1}{13}=0.07692307692307692307692307692308\)
\(\cfrac{1}{41}=0.02439024390243902439024390243902\)
\(\cfrac{1}{101}=0.00990099009900990099009900990099\)
\(\cfrac{1}{91}=0.01098901098901098901098901098901\)
it is easy to notice that the numbers are repeated on the right side
for the number \(13\) it is \(076923\), for \(41\) it is \(02439\), for \(101\) it is \(0099\), for \(91\) it is \(010989\)
This is the period of the number. The main task associated with finding the period of fractions is that they are not subject to some well-known rule.
That is, the fraction of the number 17 has a period equal to 16, and the period of the number 11 is already equal to 2. The number 7 has a period of 6, and \(7^2\) is 42.
How can you determine the period of a simple fraction?
We use the statement that for any prime number p, except 2 and 5, the statement
is true
\(10^{p-1}mod p=1\)
That is, taking the remainder of ten to the 18th power when dividing it by 19, we get one (1)
This works always and on all numbers mutually prime with ten. In general, this is called Fermat's small theorem, and we have only considered a special case where the base is 10.
So the period of a simple fraction is always! a multiple of \({p-1}\)
Judge for yourself
Number 11 \(p-1=10\) and the period is 2
the number is 41 \(p-1=40\) and the period is 5
number 101 \(p-1=100\) and the period is 4
number 19 \(p-1=18\) and the period is 18
the number is 6 \(p-1=6\) and the period is 6
In addition, by denoting the period with the letter \(T\), we can easily prove that \(10^{T}mod p=1\)
Thus, raising 10 to the power of 1,2,3..... and dividing it by a given prime number, we get the residuals.
As soon as the remainder is 1 - that's it, we found the period of a simple fraction.
Simple brute force works well on relatively small numbers, but what to do when a simple fraction has a number of tens of digits in its denominator?
It is necessary to decompose \(p-1\) into multipliers and sort through all combinations of multipliers in order to substitute the value to a power.
We will stop at a complete search, just in order to calculate not only the period, but also to determine all the numbers in this period.
How do I do it?
Imagine \(10^{p-1}mod p=1\) as \(10*M=1+p*K\), where \(K\) and \(M\) are some integers.
We obtained a linear diophantine equation with two variables
Let's take the number 41 as an example right away.
So the first step
\(10M-41P=1\) Replace \(P\) with \(-P\), so it would get rid of the minus sign.
Solving the equation \(10M-41P=1\) we get that \(M=37+41R\)
Knowing that \(M\) is a power of ten, we can represent it as \(M=10W\)
that is, \(10W=37+41R\), where \(R\) and \(W\) are some integers.
That is, we got the Diophantine equation again, which we also solve.
Without going through each step, I will write to you what numbers are obtained 1,37,16,18,10,1,37....
Have you noticed that after doing 5 iterations, we returned to the original unit? So - this quantity is the period of a simple fraction.
In principle, nothing complicated yet, moreover, the reader will say: "and what's the point, I can also raise ten to a power and take the remainder, and it will turn out even faster"
I completely agree, but the material is about something a little different - about a broader understanding of simple fractions and their periods.
But since they wanted to take the leftovers...
The Diophantine equation is certainly not very convenient to solve at each stage, but how can it be simplified?
Having calculated the value of the remainder 37 for the first time, we do not need to solve the Diophantine equation in principle. We just take the remainder of the number 37 to the power of,2,3,4.... when dividing it by 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\)
Such a scheme is already comparable to a simple search as suggested by an unknown reader.
What else can be extracted from the algorithm that uses Diophantine equations?
For example, we can find out all the numbers in a period.
\(10*M=1+p*K\) solving this equation, we found what is equal to \(M\) but did not find what is equal to \(K\)
at \(p=41\)
\(K=9\)
Now multiplying each remainder \(1, 37, 16, 18, 10\) by \(K\) and taking the last digit, we get the value of the period, which is "inverted", that is, it is not read from right to left, but from left to right.
in our example it will be \(9, 3, 4, 2, 0\)
that is, the period of the fraction is 0.(02439)
Now consider the example of the fraction \(\cfrac{1}{117}\)
1. Solving the diophantine equation \(10*M+117*K=1\), we get a pair of values \(M=82, K=7\). The last digit in the period will be 7
2. \(82^{2} mod 117=55\) , So \(M=55\) and the penultimate digit in the period will be \(82*7mod 10=4\) 4(four)
3. \(82^{3} mod 117=64\) , So \(M=64\) and the previous digit in the period will be \(55*7mod 10=5\) 5(five)
3. \(82^{4} mod 117=100\) , So \(M=100\) and the previous digit in the period will be \(64*7mod 10=8\) 8(eight)
3. \(82^{4} mod 117=10\) , So \(M=10\) and the previous digit in the period will be \(100*7mod 10=0\) 0(zero)
3. \(82^{5} mod 117=1\) , So \(M=1\) a and the first digit in the period will be \(10*7mod 10=0\) 0(zero)
Once we have reached \(M=1\) at step 5, therefore our period is 6.
And our answer is \(\cfrac{1}{117}=0.008547008547005847008547.......\)
We offer for acquaintance a table of fractions of prime numbers up to 1500, and their periods
| Number | Period | Number | Period | Number | Period |
| 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 |