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