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.

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.

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
Copyright © 2021 AbakBot-online calculators. All Right Reserved. Author by Dmitry Varlamov